[IT/코딩테스트] 99클럽 코테 스터디21일차 TIL + BOJ1003

 

오늘의 문제

https://www.acmicpc.net/problem/1003

실버

 

이번주는 DP !! 다이나믹 프로그래밍, 동적 계획법 이다.

DP 쪽은 잘 몰라서 우선 정리된 글을 보며 대강 이해하려고 했다! 

 

그런데 백준 문제를 보니까 ㅋㅋㅋ 이미 내가 2년 전에 풀었던 문제였다. 

도대체 언제 풀었던 거지...? 그런데 오늘 푼 방법이 2년 전에 푼 문제 풀이 방식보다 40ms 더 빠르더라!!!

이런걸 보면 진짜 알고리즘이 중요한 것 같다는 것이 잘 느껴진다. ㅋㅋㅋ 😂😂😂

 

 

https://velog.io/@boyeon_jeong/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

동적계획법(Dynamic Programming)

 

 

---

풀이 ( 스터디 후 수정 )

top down 방식 :

큰 문제를 해결하려고 하다가 더 작은 문제들을 재귀적으로 호출하는 방식 (메모이제이션을 추가하면 DP)

memo = {}

def fib_top_down(n, memo) : # 피보나치의 n번째 항 찾기
	if n <= 1:
    	return n # 피보나치 특성에 의한 예외처리
    if n in memo :
    	return memo[n] # -> 이미 계산된 값
        
    memo[n] = fib_top_down(n-1) + fib_top_down(n-2)
    
    return target

 

bottom up 으로 풀기 어려운 상황 > top down 으로 사용

 

1)  메모리가 불충분 할 때

2) 탈출 조건이 복잡할 때

3) '트리' 나 '그래프' 기반 문제일 때

👉 트리나 그래프 기반은 노드가 순차적으로 되어 있지 않음 (비선형적 자료구조)

 

---

 

bottom up 방식

반복문을 이용하여 작은 값부터 차례대로 계산하는 방식

def fib_bottom_up(n):
	if n <= 1:
    	return n
    
    dp = [0] * (n+1)
    dp[1] = 1
    
    for i in range(2, n+1):
    	dp[i] = dp[i-1] + dp[i-2]
        
    return dp[n]

 

top down 으로 풀기 어려운 상황 > bottom up 으로 사용

 

1)  이진 값을 기반으로 새로운 값을 만들어야 하는 상황 👉 규칙이 존재한다면 당연히 가능

2) 재귀적으로 탐색을 하는데 이게 바텀업에 비해 너무 시간이 많이 걸리는 경우가 많음

 

🌸 그래서 바텀업은 배열 기반에서 많이 사용됨

 

 

---

 

작성 전체 코드

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    a, b = 1, 0
    for i in range(n):
        a, b = b, a+b
    print(a, b)

 

 

요즘 다른 일들을 하느라 알고리즘에 전혀 신경을 쓰지 못하고 있다... 

빨리 이걸 처리(?)해버리고 알고리즘/코테 다시 공부해야할 것 같다....... 🙃

 

항상 화이팅🔥🔥🔥