본 내용은 해당 강의 토대로 작성
다이나믹 프로그래밍
1. 다이나믹 프로그래밍 개요
- 메모리를 적절히 사용하여 수행시간 효율을 비약적으로 향상 시키는 방법
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않는다.
- 두 가지 방식(탑다운, 보텀업)으로 구성
- 동적 계획법이라고도 불린다.
- 동적(Dynamic)의 의미
- 동적 할당(Dynamic Allocation) : 자료구조에서, 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법
- 여기서는 별다른 의미 없음
2. 다이나믹 프로그래밍의 조건
- 최적 부분 구조 (Optimal Substructure) : 큰 문제를 작은 문제로 나눌 수 있고 이를 모아서 큰 문제를 해결 가능
- 중복되는 부분 문제 (Overlapping Subproblem) : 동일한 작은 문제를 반복적으로 해결
3. 피보나치 수열
피보나치 수열은 아래와 같다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
- 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.
- 점화식 : 인접한 항들 사이의 관계식
- an = a n-1 + an-2 , a1 = 1, a2 = 1
- 프로그래밍에서, 수열은 배열이나 리스트로 표현
4. 피보나치 수열 : 단순 재귀 소스코드
# 피보나치 함수(Fibonacci Function)을 재귀함수로 표현
def fibo(x):
if x == 1 or x == 2: # 종료 조건 명시
return 1
return fibo(x - 1) + fibo(x - 2) # 재귀적 호출
print(fibo(4)) # 3 출력5. 피보나치 수열의 시간 복잡도 분석
- 피보나치 수열의 단순 재귀 함수는 지수 시간 복잡도(O(2N))를 가진다.
- 한 번 해결한 문제에 대해서 별도의 메모리 공간에 기록해놓지 않으면 중복되는 부분 문제를 계속해서 해결하기 때문에 수행 시간 측면에서 매우 비효율적이다.
- 다이나믹 프로그래밍을 통해서 시간 복잡도를 개선시킬 필요가 있다.
6. 피보나치 수열의 효율적인 해법 : 다이나믹 프로그래밍
- 피보나치 수열은 중복되는 부분 문제를 포함하므로 다이나믹 프로그래밍 사용 조건을 만족
7. 메모이제이션 (Memoization)
- 다이나믹 프로그래밍을 구현하는 방법 중 하나(탑다운)
- 한 번 계산한 결과를 메모리 공간에 메모
- 같은 문제를 호출 시, 메모 결과를 그대로 가져온다.
- 값을 기록 한다는 점에서 캐싱(Caching)이라고도 함
8. 탑다운 vs 보텀업
- 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업은 상향식이라고도 지칭
- 전형적으로는 보텀업 방식을 많이 사용
- DP 테이블 : 결과 저장용 리스트
- 메모이제이션 :이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미
9. 피보나치 수열 : 다이나믹 프로그래밍 소스코드
- 탑다운 : 재귀함수 사용
- 보텀업 : 반복문 사용
탑다운
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if d[x] != 0:
return d[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
d[x] = fibo(x - 1) + fibo(x - 2)
return d[x]
print(fibo(99))- 시간 복잡도는 O(N)이다.
보텀업
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
d[i] = d[i - 1] + d[i - 2]
print(d[n])10. 다이나믹 프로그래밍 VS 분할 정복
- 분할 정복의 대표적인 예시는 퀵 정렬이다.
- 다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용 가능
- 차이점은 부분 문제의 중복
- 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다.
11. 다이나믹 프로그래밍 문제에 접근하는 방법
- 유형을 파악하기
- 그리디, 구현, 완전 탐색 등의 아이디어로 풀 수 있는지 검토
- 풀이 방법이 떠오르지 않는다면 다이나믹 프로그래밍을 고려
- 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에(탑다운) 작은 문제에서 큰 문제로 그대로 사용 가능하면 코드를 개선한다.
- 일반적인 코딩 테스트에서는 기본 유형의 다이나믹 프로그래밍 문제 출제
다이나믹 프로그래밍 기초 문제 풀이
<문제> 개미 전사
문제 설명
개미 전사는 메뚜기 마을의 식량창고를 선택적으로 약탈한다. 이 때, 메뚜기 정찰병들은 인접한 식량창고가 공격받으면 바로 알아챌 수 있다. 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량 창고를 약탈해야 한다.
{1, 3, 1, 5}
위 와 같을 때, 개미 전사는 두 번째와 네 번째를 선택하여 최댓값인 8개의 식량을 빼았을 수 있다. N개에 대한 식량창고 정보가 있을 때 얻을 수 있는 최댓값을 구하여라.
문제 조건
- 풀이 시간 : 30분
- 시간제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 첫째 줄에 식량창고의 개수 N이 주어진다.
- 둘째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 K가 주어진다.
- 출력 조건
- 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력
문제 해결 아이디어
- ai = i 번째 식량창고까지의 최적의 해(얻을 수 있는 식량의 최댓값)
- 다이나믹 프로그래밍 적용
- i-1 의 해와 i-2 + 현재 식량 창고를 비교하여 많은 것을 선택
- 점화식
- ai = max(ai-1,ai-2+k)
답안 예시
# 정수 N을 입력 받기
n = int(input())
# 모든 식량 정보 입력 받기
array = list(map(int, input().split()))
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[0] = array[0] # 처음 위치까지의 얻을 수 있는 식량
d[1] = max(array[0], array[1]) # 두 번째 원소까지의 얻을 수 있는 식량
for i in range(2, n):
d[i] = max(d[i - 1], d[i - 2]+ array[i]) # 점화식
# 계산된 결과 출력
print(d[n - 1])<문제> 1로 만들기
문제 설명
정수 X가 주어졌을 때, 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다.
X가 5로 나누어 떨어지면, 5로 나눈다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
X에서 1을 뺍니다.
정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 값을 1로 만든다. 연산을 사용하는 횟수의 최솟값을 출력하여라.
문제 조건
- 풀이 시간 : 20분
- 시간제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 첫째 줄에 정수X가 주어진다.
- 출력 조건
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
문제 해결 아이디어
- 함수가 호출되는 과정을 트리구조로 그려보기
- 최적 부분 구조와 중복 되는 문제를 만족
- ai = i를 1로 만들기 위한 최소 연산 횟수
- 점화식
- ai =min(ai-1, ai/2, ai/3, ai/5) + 1
- 해당 수로 나누어질 때에 한해서 점화식 적용가능
답안 예시
# 정수 X를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001 # X의 최댓값이 30000
# 다이나믹 프로그램이(Dynamic Programming) 진행 (보텀업)
for i in range(2, x + 1):
# 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1
# 현재의 수가 2로 나누어 떨어지는 경우
if i % 2 == 0:
d[i] = min(d[i], d[i // 2] + 1)
# 현재의 수가 3으로 나누어 떨어지는 경우
if i % 3 == 0:
d[i] = min(d[i], d[i // 3] + 1)
# 현재의 수가 5로 나누어 떨어지는 경우
if i % 5 == 0:
d[i] = min(d[i], d[i // 5] + 1)
print(d[x])<문제> 효율적인 화폐 구성
문제 설명
N가지 종류의 화폐가 있을 때, 화폐의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 각 종류의 화폐는 몇 개라도 사용할 수 있다. M원을 만들기 위한 최소한의 화폐 개수를 출력하는 프로그램을 작성하여라.
문제 조건
- 풀이 시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 첫째 줄에 N, M이 주어진다. (1 <= N <= 100, 1 <= M <= 10,000)
- 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. (10,000보다 작거나 같은 자연수)
- 출력 조건
- 첫째 줄에 최소 화폐 개수를 출력
- 불가능할 때는 -1 출력
문제 해결 아이디어
- ai = 금액 i를 만들 수 있는 최소한의 화폐 개수
- k = 각 화폐의 단위
- 점화식
- 각 화폐의 단위인 k를 하나씩 확인
- ai-k를 만드는 방법이 존재하는 경우, ai = min(ai, ai-k + 1)
- ai-k를 만드는 방법이 존재하지 않는 경우, ai = INF
- 각 인덱스에 해당하는 값으로 INF(무한)의 값을 설정
- 10,001을 사용
답안 예시
# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
array.append(int(input()))
# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)
# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n): # 각각의 화폐 단위
for j in range(array[i], m + 1): # 각각의 금액
if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
print(-1)
else:
print(d[m])<문제> 금광
문제 설명
n x m 크기의 금광이 있다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작한다. 맨 처음에는 첫 번째 어느 행에서든 출발할 수 있다. 이후에 m - 1번 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 한다. 결과적으로 채굴자가 얻는 금의 최대 크기를 출력하여라.
문제 조건
- 풀이 시간 : 30분
- 시간 제한 : 1초
- 메모리 제한 : 128MB
- 입력 조건
- 첫째 줄에 테스트 케이스 T가 입력 (1 <= T <= 1000)
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력 (1 <= n, m <= 20)
- 둘째 줄에 n x m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력 (1 <= 각 위치에 매장된 금의 개수 <= 100)
- 출력 조건
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력
문제 해결 아이디어
- 금광의 모든 위치에 대해서 다음 세 가지만 고려
- 왼쪽 위에서 오는 경우
- 왼쪽 아래에서 오는 경우
- 왼쪽에서 오는 경우
- 세 가지 경우 중에서 가장 많은 금을 가지고 있는 경우를 테이블에 갱신하여 문제를 해결
- array[ i ] [ j ] = i행 j열에 존재하는 금의 양
- dp[ i ] [ j ] = i 행 j열까지의 최적의 해
- 점화식
- array[ i ] [ j ] = array[ i ] [ j ] + max(dp[ i - 1 ] [ j - 1 ], dp[ i ] [ j - 1 ], dp[ i + 1 ] [ j - 1 ] )
답안 예시
# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
# 금광 정보 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))
# 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
dp = []
index = 0
for i in range(n):
dp.append(array[index:index + m])
index += m
# 다이나믹 프로그래밍 진행
for j in range(1, m):
for i in range(n):
# 왼쪽 위에서 오는 경우
if i == 0: left_up = 0
else: left_up = dp[i - 1][j - 1]
# 왼쪽 아래에서 오는 경우
if i == n - 1: left_down = 0
else: left_down = dp[i + 1][j - 1]
# 왼쪽에서 오는 경우
left = dp[i][j - 1]
dp[i][j] = dp[i][j] + max(left_up, left_down, left)
result = 0
for i in range(n):
result = max(result, dp[i][m - 1])
print(result<문제> 병사 배치하기
문제 설명
N명의 병사가 무작위로 나열되어 있을 때, 각 병사는 특정한 값의 전투력을 보유한다. 전투력이 높은 병사가 앞에 오도록 내림차순으로 배치를 한다. 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서 남아있는 병사의 수가 최대가 되도록 한다. 병사의 번호가 주어졌을 때, 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외 시켜야 하는 병사의 수를 출력하여라.
문제 조건
- 풀이 시간 : 40분
- 시간 제한 : 1초
- 메모리 제한 : 256MB
- 입력 조건
- 첫째 줄에 N이 주어진다.(1 <= N <= 2,000)
- 둘째 줄에 각 병사의 전투력이 공백으로 구분되어 차례대로 입력(병사의 전투력은 10,000,000보다 작거나 같은 자연수)
- 출력 조건
- 첫째 줄에 남아 있는 병사의 수가 최대가 되도록 하기 위해서 열외 시켜야 하는 병사의 수 출력
문제 해결 아이디어
- 가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)
- 가장 긴 감소하는 부분 수열을 찾는 문제로 치환할 수 있다.
- 점화식
- 모든 0 <= j < i 에 대하여, D[ i ] = max(D[ i ], D[ j ] + 1 ) if array[ j ] < array[ i ]
답안 예시
n = int(input())
array = list(map(int, input().split()))
# 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환
array.reverse()
# 다이나믹 프로그래밍을 위한 1차원 DP 테이블 초기화
dp = [1] * n
# 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행
for i in range(1, n):
for j in range(0, i):
if array[j] < array[i]:
dp[i] = max(dp[i], dp[j] + 1)
# 열외해야 하는 병사의 최소 수를 출력
print(n - max(dp))'programming study > Algorithm' 카테고리의 다른 글
| [동빈나]이코테 2021 강의 몰아보기 (11)(2021.1.14) (0) | 2021.01.14 |
|---|---|
| [동빈나]이코테 2021 강의 몰아보기 (10)(2021.1.12) (0) | 2021.01.12 |
| [동빈나]이코테 2021 강의 몰아보기(8) (2021.1.6) (0) | 2021.01.06 |
| [동빈나]이코테 2021 강의 몰아보기(7)(2021.1.6) (0) | 2021.01.06 |
| [동빈나]이코테 2021 강의 몰아보기(6)(2021.1.4) (0) | 2021.01.04 |
