dynamic
-
[BOJ] 1509 팰린드롬 분할PS/BOJ 2020. 7. 15. 18:42
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하�� www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2) 접근: 1. 팰린드롬 문자열 -> 팰린드롬 문자는 부분 문제의 속성을 지녔기 때문에 Dynamic 으로 접근하기가 용이함. 2. (특정 규칙을 가지고) 분할 및 개수 구하기 -> 이 부분도 Dynamic 속성을 응용하기 쉽다. 예를 들어, D[i]: 0~i까지 분할(그룹)의 개수 라고 ..
-
[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..