티스토리 뷰
728x90
반응형
코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.
Dynamic Programming
- 한 번 계산한 결과를 재활용하는 방식
- 최적 부분 구조가 있고, 중복되는 부분 문제들이 있다면 이 방식으로 해결
방식 1. Memoization
- 한 번 계산한 결과를 저장해 놓았다가 사용하는 방식
- 하향식 접근
- 재귀 사용
방식 2. Tabulation
- 테이블(표)을 채워나가는 식으로 사용하는 방식
-상향식 접근
- 반복문 사용
1. 피보나치 (Memoization)
조건
- 함수명 : fib_memo
- 매개변수명 : n(구하고 싶은 수), cache(저장 값)
- n번째 피보나치 반환
풀이
def fib_memo(n, cache):
# base case
if n < 3:
return 1
# 이미 n번째 피보나치를 계산했으면:
# 저장된 값을 바로 리턴한다
if n in cache:
return cache[n]
# 아직 n번째 피보나치 수를 계산하지 않았으면:
# 계산을 한 후 cache에 저장
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
# 계산한 값을 리턴한다
return cache[n]
def fib(n):
# n번째 피보나치 수를 담는 사전
fib_cache = {}
return fib_memo(n, fib_cache)
# 테스트
print(fib(10))
print(fib(50))
print(fib(100))
2. 피보나치 (Tabulation)
조건
- 함수명 : fib_tab
- 매개변수명 : n(구하고 싶은 수), cache(저장 값)
- n번째 피보나치 반환
풀이1 (공간최적화 X)
def fib_tab(n):
# 이미 계산된 피보나치 수를 담는 리스트
fib_table = [0, 1, 1]
# n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
for i in range(3, n + 1):
fib_table.append(fib_table[i - 1] + fib_table[i - 2])
# 피보나치 n번째 수를 리턴한다
return fib_table[n]
# 테스트
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))
풀이2 (공간최적화 O)
def fib_optimized(n):
current = 1
previous = 0
for i in range(1, n):
current, previous = current + previous, current
return current
# 테스트
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))
728x90
반응형
'[코드잇] > ㄴ알고리즘' 카테고리의 다른 글
[알고리즘] 문제6 - Greedy Algorithm (1) | 2021.07.26 |
---|---|
[알고리즘] 정렬2 - 합볍 정렬, 퀵 정렬 구현해보기 (0) | 2021.07.26 |
[알고리즘] 문제5 - Divide and Conquer (분할 정복) (0) | 2021.07.25 |
[알고리즘] 문제4 - Brute Force (0) | 2021.06.14 |
[알고리즘] 문제3 - 재귀 함수 (0) | 2021.06.14 |
댓글
250x250
반응형
TAG
- 알고리즘
- 피보나치
- 월간 코드 챌린지 시즌1
- SWiFT
- 프로그래머스코딩테스트
- 코드잇
- 재귀함수
- 월간 코드 챌린지 시즌2
- 백준
- level2
- 문법
- 정렬
- 설치
- 프로그래머스
- Summer/Winter Coding(~2018)
- level1
- 프로그래머스 프로그래머스문제
- x만큼간격이있는n개의숫자
- 프로그래머스문제
- 코딩테스트
- 이진탐색
- 컴퓨터개론
- GIT
- 파이썬
- 유닉스커맨드
- 조합
- 알고리즘문제
- KAKAO
- 프로그래밍언어
- 파이썬문법
최근에 달린 댓글
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 |
링크
- Total
- Today
- Yesterday