dp5 [BOJ]2193: 이친수 - Swift/DP 문제https://www.acmicpc.net/problem/2193풀이문제에서 명시적으로 두 가지 조건을 제공해준다.0으로 시작하지 않는다.1이 연속되지 않는다.이진수라는 조건도 있으므로, 3가지 조건이 있다고 볼 수 있다.케이스를 몇개 써보면 쉽게 DP로 풀 수 있는걸 알 수 있다.dp[1] = 1 // 1dp[2] = 1 // 10dp[3] = 2 // 100, 101dp[4] = 3 // 1000, 1001, 1010 2번째 조건 때문에, 0으로 끝나는 경우에는 1을 붙일 수 있지만, 1로 끝나는 경우에는 0으로 붙일 수 없는 것을 알 수 있다.DP 테이블을 다음과 같이 정의하자.dp[i][j]: 자리수가 i인 이진수 중 마지막 자리수가 j인 이친수의 개수따라서 점화식은 다음과 같이 된다.dp[i.. 2025. 4. 30. [BOJ]12852: 1로 만들기 2 - Swift/DP 문제https://www.acmicpc.net/problem/12852풀이DP를 사용해서 해결했다.문제를 거꾸로 뒤집어보자. n에서 1을 가는 최단거리가 아니라, 1에서 n으로 가는 최단거리로 바꾸는 편이 편하다.이렇게 뒤집으면 개별 숫자에서 다른 숫자로 갈 수 있는 방법은 3가지가 주어진다.1 더하기2 곱하기3 곱하기쉽게 점화식을 만들 수 있다.`dp[i] = max(dp[i - 1], dp[i / 2], dp[i / 3]) + 1` 하지만 경로도 트래킹 해야 하는데, 이건 각 개별 숫자에 도달하기 전에 어떤 수에서 왔는지를 저장하는 배열 하나를 만들고, 최종적으로 이 배열을 루프로 순회하거나, 재귀를 통해서 경로를 얻어낼 수 있다.코드func trackPath(_ startNode: Int) { .. 2025. 4. 30. [백준]BOJ 2293 - 동전 1 - Swift/DP https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 DP를 사용하는 문제이다. dp 테이블의 각 인덱스가 해당 인덱스 만큼의 가치를 만들 수 있는 경우의 수 라고 하면 쉽게 풀 수 있다. 동전의 가치를 value라고 하면 그 동전을 하나 추가해서 i만큼의 가치를 만들 수 있는 경우의 수는 dp[i] += dp[i - value] 라고 할 수 있다. 따라서 하나의 가치에 대해서 동전의 종류의 수 만큼 반복문을 돌려야 한다. 문제에서 주어진 .. 2023. 7. 10. [백준]BOJ 1520 - 내리막 길 - Swift/DP & DFS https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 풀이 dfs를 이용하면 쉽게 풀 수 있는 문제일 것 같지만, 주어지는 그래프의 크기가 커서 시간초과가 나오는 문제이다. 하지만 이러한 문제들은 중첩되는 연산이 많으므로 DP를 이용하면 시간초과 없이 해결할 수 있는 경우가 흔하다. DP의 컨셉은 다음과 같다. 1. 그래프의 특정 칸에서 목적지로 도착하는 경우의 수는 앞선 경로에 상관없이 항상 같다. 2. 따라서 각 칸에서 목적지로 가는 경로의 수를.. 2023. 7. 6. [백준]BOJ 11053 - 가장 긴 증가하는 부분 수열 5 - C++/DP https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)www.acmicpc.net LIS(Longest Increasing Subsequence)라고 하는 유명한 DP 문제이다. 이 문제 외에도 연계된 문제들이 많으니 1번(BOJ 11722)부터 차례대로 풀면 어느새 여기까지 풀게 된다.이 문제들은 총 2가지 기준으로 분류된다. 첫 번째 기준은 O(n²), O(nlogn) 두 번째는 LIS 출력 여부이다. 이 중에 O(nlogn) 알고리즘을 사용하고 .. 2023. 3. 1. 이전 1 다음
