dp3 [백준]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 다음
