그래도 겁이 나던 코딩테스트가 하나씩 풀려가니까 기분이 좋기도 하다. 더 열심히 해야겠다.
아래 자료는 [이코테] 6.다이나믹 그래핑 강의를 참고했습니다.
https://www.youtube.com/watch?v=5Lu34WIx2Us
다이나믹 프로그래밍 ⇒ 동적 계획법
- 이미 계산된 결과(작은 문제)는 별도의 메모리에 저장하여 다시 계산하지 않도록 한다
- 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
- 탑다운과 보텀업으로 구성
대표적인 문제 : 피보나치 수열
1,1,2,3,5,8,13,21,34,55,89,...
#피보나치 함수를 재귀함수로 구현
def fibo(x) :
if x == 1 or x ==2 :
return
return fibo(x-1) + fibo(x-2)
print(fibo(4))
#실행결과
3
메모이제이션
: 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다 (이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 의미)
■ 피보나치 수열 : 탑다운 dp 코드
#한 번 계산된 결과를 메모이제이션 하기 위해 리스트 초기화
dp = [0] * 100
#피보나치 함수를 재귀함수로 구현
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(fibo(6))
#실행결과
8
■ 피보나치 수열 : 보텀업 dp 코드
#앞서 계산된 결과를 저장하기 위한 dp 테이블 초기화
d = [0] * 100
#첫번째 피보나치 수 와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
#반복문으로 구현
for i in range(3,n+1) :
d[i] = d[i-1] + d[i-2]
print(d[6])
< 문제1 > 개미전사
내가 풀던 방식 (완전탐색)
n = int(input())
arr = list(map(int,input().split()))
answer = 0
def recur(idx, k) :
global answer
if idx > n+1 :
return
if idx >= n :
answer = max(answer , k )
return answer
#만일 선택을 했을 경우
recur(idx+2 , k + arr[idx])
#만일 선택을 안했을 경우
recur(idx+1 , k)
recur(0,0)
print(answer)
보텀업 DP
창고가 존재함에 따른 최적의 해 계산
창고 0 만 존재 할 때: 1
창고 0,1 만 존재할 때 : 3
창고 0,1,2만 존재할 때 : 3
창고 0,1,2,3까지 존재할 때 : 8
왼쪽부터 식량찬고를 턴다고 했을 때, 특정한 i번째 식량창고에 대해서 털지 안털지의 여부를 결정
n = int(input())
arr = list(map(int,input().split()))
#앞서 계산된 결과를 저장하기 위해 dp 테이블 초기화
d = [0]*100
d[0] = arr[0]
d[1] = max(arr[0],arr[1])
#다이나믹 프로그래밍 진행
for i in range(2,n) :
d[i] = max(d[i-1], d[i-2] + arr[i])
print(d[n-1])
'코딩테스트 (Coding Test)' 카테고리의 다른 글
[백준] 2805번 나무자르기 - 파이썬 (1) | 2023.10.06 |
---|---|
[백준] 2606번 바이러스 - 파이썬 (2) | 2023.10.05 |
[백준] 14501번 퇴사 - 파이썬 (0) | 2023.10.04 |
[백준] 2961번 도영이가 만든 맛있는 음식 - 파이썬 (1) | 2023.10.04 |
[백준] 2503번 숫자야구 - 파이썬 (0) | 2023.10.03 |