DFS
-
[BOJ] 1987 알파벳PS/BOJ 2020. 7. 17. 17:00
https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 알고리즘: DFS, Backtracking 접근: 1. 경로 탐색 문제 2. 같은 알파뱃이 적힌 칸은 두 번 지날 수 없다 3. 최대한 몇 칸을 지날 수 있는가 -> 1, 3번 조건을 보면 이 문제가 DFS 문제라는 것을 알 수 있다. (경로를 탐색해가면서 최장경로 찾기) 이제 2번 조건만 해결해주면 된다. 2번은 조건은 알파뱃과 숫자를 하나씩 대응시켜 (A-0, B-1, C-2, ...,..
-
[BOJ] 12852 1로 만들기 2PS/BOJ 2020. 7. 15. 15:18
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 알고리즘: DP, DFS 시간복잡도: O(logN) 1463 1로 만들기에서 경로 추적을 추가한 문제. https://moon323.tistory.com/5 접근: Dp 경로 추적 문제들이 늘 그렇듯 점화식에서 참고한 부분문제의 성분을 저장해주면 됨. ex) v[] : 경로 추적 배열 D[X] = Min(D[X/2] + X%2 + 1, D[X/3] + X%3 +1) 에서 D[X/2] 부분을 가져왔으면 v[X] = 2로 표시, D[X/3] 부분을 가져왔으면 v[X] = 3 으로 표시 v를 참고하여 역추적..
-
[BOJ] 1463 1로 만들기PS/BOJ 2020. 7. 15. 15:06
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘: DP, DFS 시간복잡도: O(logN) 문제는 Dynamic 이긴 한데... N 조건이 작기도(10^6) 하고, 취하는 연산이 계속 나누는거여서 DFS로도 충분히 빠르게 풀리긴 함. Dynamic 접근: 1. 연산을 사용하는 횟수의 최솟값을 출력 2. 답이 이전 부분 문제들에 영향을 받음. -> ex) N = X*2 라고 하자. N의 최소 연산 횟수를 알려면 그 전에 X의 최소 연산 횟수를 알아야한다. 정수 X에 대한 3가지 연산을 잘 관찰하면 점화식을 아래와 같이 정리할 수 있다. D[X] = M..