DP2 [BOJ] 18353: 병사 배치하기 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net LIS (Longest Increasing Subsequence) : 가장 긴 증가하는 부분 수열 (다이나믹 프로그래밍) dp[i] : array[i] 를 마지막 원소로 갖는 부분 수열의 최대 길이 => 모든 0 array[i]로 판단한다. index / array 15 11 4 8 5 2 4 i = 0 1 1 1 1 1 1 1 i = 1 1 2 1 1 1 1 1 i = 2 1 2 3 .. 2023. 7. 16. [AL] 다이나믹 프로그래밍 (Dynamic Programming) 다이나믹 프로그래밍 (Dynamic Programminig) 1. 조건 1) 최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 2) 중복되는 부분 문제 (Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 함 2. 문제 풀이 방식 1) Top-down - 재귀 함수로 dp를 해결 큰 문제를 해결하기 위해 작은 문제 호출 - 메모이제이션이 활용됨 한 번 구현한 결과를 메모해 두고, 같은 식을 다시 호출할 경우 메모한 기록을 가져와서 불필요한 계산을 줄임 피보나치 top-down 예시 #include using namespace std; long long *dp; long .. 2023. 7. 11. 이전 1 다음
