매일 조금씩

문제 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 구현 문제 큐를 이용해 뱀의 궤적을 저장 사과가 없으면 뱀의 꼬리 좌표 정보를 큐에서 제거한다. 소스코드 from collections import deque n = int(input()) k = int(input()) dummy_map = [[0]*(n+1) for _ in range(n+1)] # 사과 셋팅 for _ in range(k): a, b = map(int, input().spl..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하는 공식을 알면 쉽게 풀 수 있다. 트리 내 임의 정점을 선택하여 해당 노드에서 거리가 가장 먼 노드를 구한다. 해당 노드에서 DFS 알고리즘을 수행하여 가장 먼 거리를 구하면 그 값이 트리의 지름이 된다. 아래 블로그 내용을 참고하였다. https://blog.myungwoo.kr/112 트리의 지름 구하기 트리에서 지름이란, 가장 먼 두 정점 사이의..

문제 https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 와샬 알고리즘을 사용하여 풀 수 있다. ex) 1 > 2 , 2 > 3 ===> 1 > 3 소스코드 package floyd; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWrit..

문제 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 풀이 다익스트라 알고리즘 문제이다. 특이점은 최소 비용 뿐만 아니라 최소 비용으로 가는 경로 또한 출력해야 한다는 점이다. cost 배열을 2차 배열로 만들어서 최소 비용과 함께 갱신할 때의 이전 노드값을 같이 저장하였다. 다익스트라 알고리즘 수행 후, 도착지 노드부터 이전 노드 값을 거꾸로 탐색하여 시작 노드까지의 경로를 구하였다. 소스코드 package d..

문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 풀이 완전탐색 문제로 재귀 함수를 사용하여 가능한 조합을 구한다. k개 수에서 순서 상관 없이, 중복 없이 6개의 수를 뽑는다. 소스코드 package bruteforce; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.Output..

문제 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 다익스트라 알고리즘 사용 최소 벽 파괴 횟수를 갱신하면서 탐색 소스코드 package dijkstra; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class BOJ..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 좌표 영역을 칠하고, DFS로 빈 공간의 개수와 넓이를 구한다. 영역 칸의 개수를 구해야 하기 때문에, 입력된 좌표를 그대로 사용하면 정확한 답을 구할 수 없다.- 이를 해결하기 위해, 칠할 영역 시작 좌표의 x, y 좌표는 +1을 해주어서 좌표의 기준을 우측 대각선 위로 동일하게 맞춰주었다. ex) 칠해야 할 영역의 시작 좌표가 0, 0 일 경우 1, 1로 변경해서..

문제 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이 분할정복 문제이다. 유사 문제 2021.11.16 - [Problem Solving/BOJ] - [BOJ 2630] 색종이 만들기 (Java) 2021.11.23 - [Problem Solving/Programmers] - [프로그래머스] 쿼드 압축 후 개수 세기 (Java) 2021.11.17 - [Problem Solving/BOJ] - [BOJ 1992] 쿼드트리 (Jav..

문제 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 연합을 모두 찾은 후에 인구이동이 되어야 하므로, 찾은 연합을 저장해 둘 자료 구조를 생성한다. 1. 맵을 순회하면서 DFS로 연합을 찾아서 저장한다. 2. 연합을 모두 찾은 후에, 연합 내 총 인구/나라 개수를 계산하여 각 나라의 인구를 갱신한다. 이 두 과정을 반복 한다. 연합을 찾았는데 연합의 개수가 0개인 경우 Loop를 종료한다. 반복 횟수를 출력한다. 소스코드 ..

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 가로수 사이의 간격을 계산하여 저장한 후 , 간격들의 최대 공약수를 구한다. 가로수의 최대 거리와 가로수의 최소 거리의 차이를 구한 후 최대 공약수로 나눠준다. (유클리드 호제법 사용) 양 끝이 모두 포함되므로, 나눈 값에 1을 더한 값이 가로수의 개수가 된다. 이 개수에서 이미 심어져 있는 가로수 개수를 뺀 값이 정답이 된다. 소스코드 package math; import ja..