- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
다이나믹 프로그래밍
- 다이나믹 프로그래밍은 메모리를 적절히 사용하여, 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
- 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.
- 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다.
- 다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다.
- 최적 부분 구조(Optimal Substructure)
- 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서, 큰 문제를 해결할 수 있는 경우
- 중복되는 부분 문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
피보나치 수열
- 피보나치 수열은 다음과 같은 형태이며, 다이나믹 프로그래밍으로 효과적으로 계산할 수 있다.
- 점화식이란, 인접한 항들 사이의 관계식을 의미한다.
- 피보나치 수열을 점화식으로 표하면 다음과 같다.
# 피보나치 함수(Fibonacci Function)을 재귀함수로 구현
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
print(fibo(4))
피보나치 수열의 시간 복잡도 분석
- 단순 재귀 함수로 피보나치 수열을 해결하면, 지수 시간 복잡도를 가지게 된다.
- 다음과 같이 f(2)가 여러 번 호출된다.
피보나치 수열의 효율적인 해법: 다이나믹 프로그래밍
- 다이나믹 프로그래밍의 사용 조건을 만족하는지 확인한다.
- 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있는지
- 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결할 수 있는지
메모이제이션
- 다이나믹 프로그래밍을 구현하는 방법 중 하나
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법
탑다운 vs 보텀업
- 탑다운 방식은 하향식이라고도 하며, 보텀업 방식은 상향식이라고도 한다.
탑다운 방식
- 피보나치 수열: 탑다운 다이나믹 프록그래밍 소스코드는 다음과 같다.
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
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))
보텀업 방식
- 피보나치 수열: 보텀업 다이나믹 프록그래밍 소스코드는 다음과 같다.
# 앞서 계산된 결과를 저장하기 위한, 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])
피보나치 수열: 메모이제이션 동작 분석
- 이미 계산된 결과를 메모리에 저장하면, 다음과 같이 색칠된 노드만 처리할 것을 기대할 수 있다.
다이나믹 프로그래밍 문제에 접근하는 방법
- 가장 먼저 그리디, 구현, 완전 탐색등의 아이디어로 문제를 해결할 수 있는지 검토한다.
- 다른 알고리즘으로 풀이 방법이 떠오르지 않으면, 다이나믹 프로그래밍을 고려해 본다. - 일단 재귀 함수로 비효율적인 완전 탐색 프로그램을 작성한 뒤에, (탑다운) 다이나믹 프로그래밍 방식으로 코드를 개선할 수 있다.
<문제 1> 개미 전사
입력 예시
4
1 3 1 5
- 첫째 줄에 식량창고의 개수 N이 주어진다. (0 ~ 99)
- 둘째 줄에 공백을 기준으로 각 시량창고에 저장된 식량의 개수 K가 주어진다.
출력 예시
8
- 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력한다.
<풀이 1> 개미 전사
문제 해결 아이디어
# 정수 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])
<문제 2> 1로 만들기
입력 예시
26
- 첫째 줄에 정수 X가 주어진다. (1 ~ 30,000)
출력 예시
3
- 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
<풀이 2> 1로 만들기
문제 해결 아이디어
# 정수 X를 입력 받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한, DP 테이블 초기화
d = [0] * 30001
# 다이나믹 프로그래밍(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])
<문제 3> 효율적인 화폐 구성
입력 예시
2 15
2
3
- 첫째 줄에 N, M이 주어진다.
- 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.
출력 예시
5
- 첫째 줄에 최소 화폐 개수를 출력한다.
- 불가능할 때는 -1을 출력한다.
<풀이 3> 효율적인 화폐 구성
문제 해결 아이디어
# 정수 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):
# (i - k)원을 만드는 방법이 존재하는 경우
if d[j - array[i]] != 10001:
d[j] = min(d[j], d[j - array[i]] + 1)
# 계산된 결과 출력
if d[m] == 10001:
print(-1)
else:
print(d[m])
<문제 4> 금광
입력 예시
2
3 4
1 3 3 2 2 1 4 1 0 6 4 7
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2
- 첫째 줄에 테스트 케이스 T가 입력된다.
- 매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력된다.
- 둘째 줄에 n*m개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력된다.
출력 예시
19
16
- 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다.
<풀이 4> 금광
문제 해결 아이디어
- 금광의 모든 위치에 대하여, 다음의 3가지만 고려하면 된다.
# 테스트 케이스(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)
<문제 5> 병사 배치하기
입력 예시
7
15 11 4 8 5 2 4
- 첫째 줄에 N이 주어진다.
- 둘째 줄에 병사의 전투력이 공백으로 구분되어 차례대로 주어진다.
출력 예시
2
- 첫째 줄에 남아있는 병사의 수가 최대가 되도록 하기 위해서 열외시켜야 하는 병사의 수를 출력한다.
<풀이 5> 병사 배치하기
- 이 문제의 기본 아이디어는 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)이다.
- 해당 문제의 경우, 가장 긴 감소하는 부분 수열을 구하는 문제이다.
- 가장 먼저 입력 받은 병사 정보의 순서를 뒤집는다.
- 가장 긴 증가하는 부분 수열 알고리즘을 수행하여 정답을 도출한다.
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))
안녕하세요.