👻 다이나믹 프로그래밍
다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 연산 속도와 메모리를 최대한으로 활용하기 위한 기법. 특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해서 수행한다면 문제를 효율적으로 해결할 수 없다. 이럴 때 사용하는 것이 dp이며 2가지 조건을 만족해야해.
다이나믹 프로그래밍은 대부분 바텀업 방식으로 해결한다고 생각하면 된다.
- 다이나믹 프로그래밍(dp)는 문제를 많이 풀다보면 그 스타일이 느껴질꺼야.
- dp 문제는 보통 주어진 문제를 작은 단위로 만들어 그 해가 다음 조금 큰 단위 문제의 해와 연관성을 파악해야 한다.
⚽ 즉 점화식을 구할 수 있다면 쉽게 해결 가능해진다.
🏈 다이나믹 프로그래밍을 사용할 수 있는 두 가지 조건
최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있다.중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다. (점화식)
⚽ 위 두 조건을 만족한다면 dp를 통해 문제를 해결할 수 있다.
⚽ 메모이제이션
🏈 한번 계산한 결과를 메모리 공간에 메모하는 기법
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
- 값을 기록해 놓는다는 점에서 캐싱이라고도 한다.
😀 기본적으로 바텀업 방식으로 문제를 해결한다.
- 피보나치 수열을 바텀업 dp 방식으로 문제를 풀어본다면
#피보나치 수열 : 바텀업 다이나믹 프로그래밍 소스코드
#한번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
dp = [0] * 100
#첫 번째 피보나치 수와 두 번째 피보나치 수는 1
dp[1] = 1
dp[2] = 1
n = 99 #원하는 피보나치 수
#피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])- 이렇게 간단하게 풀 수 있다.
- 바텀업 다이나믹 프로그래밍은 작은 문제부터 먼저 해결해 놓은 다음에 먼저 해결에 놓았던 그 작은 문제들을 조합해서 앞으로의 큰 문제들을 차례대로 구해나가는 것을 확인할 수 있다.
💦 dp 접근
⚽ 어떠한 문제를 해결하기 위한 아이디어로 어떤 알고리즘을 활용할 수 있는지 먼저 고민해보는 습관을 들이자 !
- 가장 먼저 그리디, 구현, 완전 탐색(가능한 경우를 일일이 하나씩 나열하면서 확인하는 방법) 등의 아이디어로 문제를 해결할 수 있는지 검토하자.
⚽ 다른 알고리즘으로 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 고려하자!
👻 일반적인 코딩테스트 수준에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많다 ! 겁먹지 말자
⚽ 문제 유형 풀어보면서 익히기
💨 동적계획법이란? 네트워크 선 자르기(Bottom-Up)
현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면
의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?
▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
7
▣ 출력예제 1
21
바텀업
import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
n = int(input())
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])탑다운
(탑다운 : 재귀, 메모이제이션으로 풀기)
- 메모이제이션이란, 이미 구해진 값을 다시 사용할 때는 메모리에 따로 저장해놓고 사용한다.
import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
n = int(input())
dp = [0] * (n+1)
def DFS(len):
if dp[len] > 0:
return dp[len]
if len == 1 or len == 2: #종료조건
return len
else:
dp[len] = DFS(len-1) + DFS(len-2)
return dp[len]
print(DFS(n))해당 문제 코멘트
문제에서 선을 1m,2m의 길이를 갖는 선으로 자르다고 한다.
- 자르는 위치에 따라서 방법이 다르다. 1 + 1 + 2 와 2 + 1 + 1은 다른 경우이다.
이 문제를 어떻게 접근해야 하나면... 예시처럼 7m를 한번에 계산할 수 없다는 생각은 할 수 있다.
문제에서 1m,2m의 길이를 갖는 선으로 자른다고 했으니 가장 작은 단위부터 생각해봐야 한다.
⚽ 1m의 경우 직관적으로 1m 1개로 1가지만 존재한다. 2m의 경우 역시 직관적으로 1m 2개, 2m 1개 경우만 존재한다. 즉 2가지가 존재한다.
- 이제 직관적인 부분은 dp에 채워놓고 시작할 수 있다. (dp로 풀 때 직관적으로 알 수 있는 것은 미리 초기화를 시켜놔야 한다.)
이제 3m부터는 더 작은 문제로부터 답을 도출할 수 있는지 확인해야 한다.
- 3m가 있다면.. 가장 마지막 토막이 1m or 2m로 나눠볼 수 있다.
- 즉 이 문제 점화식 세울 때 가장 마지막 토막이 1m or 2m인 경우로 나눠서 생각할 수 있다.
⚽ 점화식 접근할 때 마지막 부분을 통해 생각하는 습관을 기르자.
- 이 문제를 생각하면 마지막 부분을 2로 자를 때 1m 2개짜리로 자르는 것은 생각할 필요가 없다. 이유는 이미 앞에서 마지막 토막이 1인 경우를 생각했다 ! 그렇기에 생각 안해줘도 되는거지.
❤️ dp 다시 정리
큰 문제에 대한 답을 구해야 할 때 작은 문제를 알 수 있다면... 위의 문제를 예시로 1m 1개, 2m 1개 이게 전체라고 생각해봐. 그럼 1가지, 2가지 .. 이런 식으로 생각할 수 있잖아. 거기서 다시 키워나가 3번째 계단까지는 ? 4번째 계단까지는 ? 이런 식으로 키워보면서 생각해야해.
- dp 문제를 풀 때는 작은 문제로 큰 문제를 해결한다는 마인드로 접근해야 해 !
👻 dp로 풀지 DFS/BFS로 풀지 고민 !
DFS는 트리 형태의 깊이 탐색을 하는데 그 깊이 즉 레벨값이 보통 20~25를 넘지 않아야 1초 타임 리밋을 피한다고 생각할 수 있다. 하지만 레벨(인덱스)이 50~100 이런 경우... 다이나믹이라고 생각해야 한다!!
- 다이나믹 프로그래밍 문제의 접근 방법
다이나믹 점화식을 만들어내는 능력을 기르는 팁은 없다. 백준에서 다이나믹 문제를 많이 풀어보는 방법밖에 없다. 처음 배울 때는 다이나믹 내 주제 중 기초인
1) LIS(최대부분증가수열 스타일)
2) 냅색알고리즘(가방문제 스타일)
3) LCS(최대공통부분문자열 스타일)
위 3주제로 시작하자.
백준 추천문제
1. 11053(가장 긴 증가하는 부분수열)
-
1965(상자넣기)
-
18353(병사배치하기)
-
2579(계단오르기)
-
2655(가장 높은 탑 쌓기)
-
14430(자원캐기)
-
1890(점프)
-
2293(동전1)
-
2294(동전2)
-
12865(평범한 배낭)
-
12920(평법한 배낭2)
-
5582(공통부분문자열)
-
9252(LCS2)
-
15483(최소편집)
-
1915(가장 큰 정사각형)
