스파르타코딩클럽 알고리즘 강의
동적 계획법
원래 5주차에 포함된 강의지만 오늘 문제 중에 동적 계획법 주제 문제가 두 문제나 나와서 들었다.
동적 계획법: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법.
동적 계획법은 부분 문제 반복, 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
아이디어: 한 번 계산한 걸 다시 계산하지 말자. 반복되는 구조가 나오면 미리 적어두자.
메모이제이션(Memoization): 결과를 기록하는 것.
겹치는 부분 문제(Overlapping Subproblem): 문제를 쪼갤 수 있는 구조.
피보나치 수열
5에 대한 피보나치 수열을 구할 때 일반적인 방법으로 구현을 하게 되면 똑같은 연산을 여러번 반복하게 된다. (5: 1번, 4: 1번, 3: 2번, 2: 3번 등등)
따라서 이 문제는 쪼갤 수 있는 구조이다.
- 메모장에 1번째, 2번째 숫자를 저장해둔다.
- n이 메모장에 있으면 그 숫자를 반환한다.
- 그게 아니라면 새로운 memo[n]에 fibo(n-1)+fibo(n-2)를 저장한다.
- memo[n]을 반환한다.
딱 보면 '아 그렇구나' 하고 이해가 되지만 많은 연습을 하지 않는 한 절대 헤맬 것 같다. 매일 동적 계획법 문제를 한 문제 씩 풀어보는 것을 목표로 해야겠다.
memo = {1: 1, 2: 1}
def fibo(n):
if n in memo:
return memo[n]
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]페어 프로그래밍
문제풀이
1. 다리 놓기
이 문제는 지난 5일차 때 풀었던 '이항 계수 1' 문제와 똑같은 원리이다.
전체 코드
import sys
input = sys.stdin.readline
def factorial(n):
f = 1
for i in range(n):
f = f * (i+1)
return f
T = int(input())
for i in range(T):
N, M = map(int, input().split())
print(int(factorial(M) / (factorial(N) * factorial(M-N))))2. 피보나치 함수
이 문제는 사실 혼자서는 절대 못 풀었을 것 같다. 같이 한 페어가 알려준 방법대로 하니까 통과가 되었다.
풀이:
1. 두 개의 리스트(zero, one)에 각각 0이 나오는 횟수(1,2번째)와 1이 나오는 횟수(1,2번째) 저장. (예: N이 0일 때 0은 한 번, 1은 0번; N이 1일 때 0은 0번, 1은 1번)
2. 만약 N이 0이면 리스트의 마지막 숫자가 아닌 첫 번째 숫자 출력.
3. 그 외에는 0이 나오는 횟수와 1이 나오는 횟수를 2번째부터 N번째까지 반복
3-1. zero에는 그 다음 나오는 숫자인 one의 마지막 숫자 추가
3-2. one에는 마지막 숫자와 이전 숫자의 합 추가
4. 결국에는 각 리스트의 마지막 요소 출력
전체 코드
T = int(input())
for i in range(T):
N = int(input())
zero = [1, 0]
one = [0, 1]
if N == 0:
print(1, 0)
continue
for i in range(2, N+1):
zero.append(one[-1])
one.append(one[-2] + one[-1])
print(zero[-1], one[-1])3. 평범한 배낭
페어와 같이 2시간 정도 고민을 해도 감을 도저히 못 잡겠어서 검색을 해보았다. 사실 지금 정리를 하면서도 혼자 풀면 아예 못 풀거나 엄청 오래 걸리겠다는 생각이 든다.
i: 현재 물건
j: 현재 가방 무게
W: i번째 물건의 무게
V: i번째 물건의 가치
풀이:
1. knapsack 리스트를 (K+1)x(N+1) 만큼 만들고 0으로 초기화
2. items는 [0, 0]으로 초기화 후 N개의 아이템 저장(W와 V가 각 요소에 리스트로 추가됨)
3. knapsack 2차원 배열을 2중 for문 반복
3-1. j가 W보다 크거나 같은 경우: V를 knapsack[i-1][j-W](현재 가방 무게에서 현재 물건 무게를 뺀 나머지 무게를 가진 물건의 가치)에 더한 값과 이전 무게를 가진 물건의 가치와 비교했을 때 더 큰 값을 knapsack[i][j]에 저장
3-2. j가 W보다 작은 겨우: 이전 무게를 가진 물건의 가치를 저장
4. NxK에 있는 값이 최종적으로 원하는 값
위의 과정을 표로 만들면 이런 표가 나온다.
전체 코드
N, K = map(int, input().split())
knapsack = [[0 for _ in range(K+1)] for _ in range(N+1)]
items = [[0, 0]]
for i in range(N):
items.append(list(map(int, input().split())))
for i in range(1, N+1):
for j in range(1, K+1):
W = items[i][0]
V = items[i][1]
if j >= W:
knapsack[i][j] = max(V + knapsack[i - 1][j - W], knapsack[i - 1][j])
else:
knapsack[i][j] = knapsack[i - 1][j]
print(knapsack[N][K])내일 할 일
