알고리즘과 자료구조/Dynamic Programming 썸네일형 리스트형 Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 4. 3. 14:21 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 5: DP 배열 설정의 중요성 (백준 14238, 17404, 12969번 파이썬) 백준 14238번: 출근 기록 문제 설정은 간단하다. 각 알파벳 A, B, C에 대해서 아래 조건을 금방 파악할 수 있다. 그렇지만 문제 조건을 잘 파악했다 하더라도 다음이 문제다. 기존 문제처럼 dp 배열이 1차원 또는 2차원이라고 가정하고 접근해보자. DP 배열이 1차원이라면? dp[n] = V : 길이가 n인 문자열 중 올바른 출근 기록인 경우의 수(또는 문자열들의 배열?) 점화식을 세울 때 dp[n]과 dp[n-1] 사이 관계를 어떻게 정의할 수 있는가? 길이가 n-1인 문자열 오른쪽 끝에 A를 추가했을 때, B를 추가했을 때 그리고 C를 추가했을 때 매번 기존 문자열의 끝에 어떤 문자가 오느냐에 따라 추가할 수 있는지 없는지가 달라진다. 또는 dp[n]에 길이가 n인 가능한 모든 문자열들을 배열.. 2023. 3. 29. 17:29 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 4: 배낭 문제 (백준 7579, 2629번 파이썬) Dynamic programming 개념을 설명할 때 피보나치 수열 말고도 가장 흔하게 언급되는 예시가 배낭 문제(knapsack problem)이다. 어느 정도 난이도가 있는 배낭 문제는 DP로 푸는 게 대부분이다. 배낭 문제를 처음 접해본 사람은 올바른 풀이를 떠올리기 정말 어렵다. 그러나 배낭 문제는 결국 사소한 문제 설정에서 차이가 있을 뿐 비슷한 유형의 문제를 풀다보면 동일한 패턴을 발견하게 된다. 결국 배낭 문제는 풀이 방식이 비슷하기 때문에 아예 풀이를 외울 정도까지 익숙해지는 게 좋다고 생각한다. 배낭 문제에 속하는 예시 몇 가지를 아래에서 살펴보자. 백준 7579번: 앱 문제 설정은 앞서 살펴본 11066번(파일 합치기)와 11049번(행렬 곱셈 순서)와는 다르다. 이전 문제는 어떤 연속.. 2023. 3. 29. 15:35 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 3: 재귀(top-down)를 이용한 풀이 (백준 11049번 파이썬) 2번째 글에 이어서 재귀를 이용한 top-down 방식의 풀이를 소개하려고 한다. 백준 11049번: 행렬 곱셈 순서 언뜻 다른 것처럼 보이지만 백준 11066번(파일 합치기) 문제와 매우 비슷하다. 두 문제는 아래와 같은 공통점이 있다. 어떤 연속된 값들을 하나씩 더하거나 곱해간다. 두 개를 합쳐 하나로 만드는 과정을 반복한다. 최종 행렬 곱셈 결과를 이미 구했다고 가정했을 때 그 값은 결국 어떤 두 행렬을 곱한 결과고, 각 두 행렬을 더 작은 문제(행렬의 곱셈 결과)로 쪼개나간다는 컨셉은 11066번과 판박이다. 다만 11066번과 다른 점은 단순 합을 구하는 게 아니라 행렬의 곱을 구한다는 점이다. 여기서 dp 배열 말고도 메모이제이션을 통해 재활용해야 하는 값이 생긴다. 아래 코드를 살펴보자. 재.. 2023. 3. 29. 14:15 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 2: 재귀(top-down) vs. DP(bottom-up) (백준 11066, 1520, 1937번 파이썬) Dynamic Programming(DP) 개념을 처음 소개할 때 빠지지 않고 등장하는 게 피보나치 수열이다. 설명 글을 요악하면 다음과 같다. 1) 피보나치 수열을 재귀함수를 이용해 구한다. 2) 재귀함수로 구할 때 중복된 계산이 발생한다. 어차피 같은 답을 내놓는 연산을 여러 번 반복하니 불필요하고 비효율적이다. 3) 불필요한 연산을 방지하기 위해 memoization, 즉 DP 개념을 도입한다. 여기에 핵심이 있다. 우리는 같은 DP 문제에 대해 재귀로 풀 수도 있고, DP로도 풀 수 있다. 이유는 애초에 DP 문제가 다음 성질을 지니기 때문이다. 1) 큰 문제(마지막 항, f(n), 구하고자 하는 답, 현재 상태)를 작은 문제(초기값, 이전 상태, 직전 단계)에 의존하는 관계식으로 표현할 수 있다.. 2023. 3. 28. 15:42 ㆍ 알고리즘과 자료구조/Dynamic Programming Dynamic Programming 1: 기초 풀이 접근 (백준 10942, 17070번) Dynamic Programming 문제는 결국 점화식을 찾는 게 관건이다. 즉 현재 상태가 이전 상태에 어떻게 의존하는지, 어떤 관계 속에 놓여있는지 파악해야 한다. DP 문제 풀이 접근 방식은 다음과 같다. 1) 머리만 굴리지 말고 직접 손으로 써본다. 어차피 DP는 점화식을 찾는 문제고, 점화식은 곧 이전 항과 현재 항 사이 숨은 패턴을 찾는 일이다. 다행히 직접 반복해보면서 써보면 패턴을 발견하게 되는 경우가 대부분이다. 테스트 케이스나 (테스트 케이스가 적절하지 않다면) 직접 예시를 고안해서 4~5개 항 정도 추론해볼 것. 2) 문제 조건을 결정 짓는 핵심 정보는 무엇인가? 3) 현재 상태가 이전 상태에 어떻게 의존하는가? 4) DP 배열의 정보를 명확히 설정한다. 1차원인가? 2차원 또는 그 .. 2023. 3. 28. 13:43 ㆍ 알고리즘과 자료구조/Dynamic Programming 이전 1 다음
