백준
-
백준 1890 : 점프백준 2023. 11. 10. 01:03
1. 문제 : https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 2. 문제 접근 BFS : 다음 노드로 탐색할 수 있는 방법은 두 가지이므로 자식이 2개인 트리를 탐색하는 문제로 치환할 수 있다. 다만, 최악의 경우(모든 노드의 값이 1일 때), 시작점에서 사각형의 절반만 탐색하더라도 $2^N$개의 노드를 탐색해야 한다. 4 bytes * $2^N$만 해도 메모리가 터지는 것을 확인할 수 있다. DP : BFS에서 메모리 초과가 나는 ..
-
백준 1697 : 숨바꼭질백준 2023. 11. 7. 17:46
1. 문제 : https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 문제 접근 주어진 규칙에 따라 이동하므로 정해진 경우의 수가 존재. -> 탐색 각 위치를 노드로 표현했을 때 A라는 지점으로 다시 돌아올 수 있음. -> 순회가 존재 -> 그래프 그래프를 탐색할 때 가장 빠른 시간을 구해야하므로 Depth가 가장 짧은 경로를 구해야 함. -> BFS 이미 방문한 노드라면 BFS로 탐색하기 때문에 이전에 방문한 경로가 ..
-
백준 1389 : 케빈 베이컨의 6단계 법칙백준 2023. 11. 6. 19:04
1. 문제 : https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 2. 문제 접근 노드의 갯수와 간선의 정보가 주어짐. -> 그래프 탐색 한 노드에서 다른 모든 노드에 대하여 가장 짧은 경로를 원함. -> Transitive Closure 모든 노드에 대해 구해야 함. -> All-Pairs Shortest Paths -> Floyd-Warshall Transitive Closure 3. 문제 해결 ..
-
백준 1309 : 동물원백준 2023. 11. 5. 04:16
1. 문제 : https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 2. 문제 접근 백트레킹 $2N$개의 칸 중 $A$라는 지점에 사자를 배치. 다음 탐색 노드를 선정해야하지만 사자를 배치하는 순서가 없기에 $A$ 지점을 제외한 모든 지점을 탐색해야 함. 즉 자식 노드의 갯수가 $2N$개가 되는 괴랄한 트리를 탐색해야 하기에 사용할 수 없음. DP $N = K$일 때 사자를 배치한 경우의 수는 $N = K - 1$일 때 사자를 배치한 경우의 수에 왼쪽 혹은 오른쪽에 사자를 배치하거나 배치하지 않는 경우의 수를 추가하여 구할 수 있음. 이를 점화식으로 만들 수 있으므로 DP 사용 가능..
-
백준 1149 : RGB 거리백준 2023. 11. 3. 17:29
1. 문제 : https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 문제 접근 완전 탐색 최악의 경우에 $3^1000$ -> Time limit으로 사용할 수 없음. 백트레킹 입력되는 비용이 오름차순으로 정렬되지 않음. 즉, $N = K$일 때 전체 비용이 $N = K + 1$일 때 전체 비용보다 무조건 작다라고 확신할 수 없어 사용 불가능. DP 반복되는 규칙이 존재 : $N = K$에 최솟값은 $N = K - 1$일 때..
-
백준 1074 : Z백준 2023. 11. 3. 03:09
1. 문제 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 접근 완전 탐색 최악의 경우에 $2^{15} X 2^{15} = $약 $10$억 -> Time limit으로 사용 불가능 분할 정복 $N = K$ 정사각형은 $N = K - 1$ 정사각형 $4$개를 합친 모양 -> 큰 문제를 작은 문제로 분할 모든 노드의 자식 노드가 $4$개인 트리로 전환 가능 3. 문제 해결 $N = K$ 정사각형을 4개로 분할 $N = K -..