220316_TIL

알고리즘 강의 - 동적 계획법과 분할 정복

• 동적 계획법

: 작은 문제를 계산하고 그 문제의 해답을 저장해놓고 큰 문제의 해결하는 방법

특이점은 memoization기법을 사용하는 것으로 이전에 계산한 값을 저장해놓아 다시 계산하지 않도록 하여 실행 속도를 빠르게 하는 기술이다..

ex) 피보나치 수열

• 분할 정복

: 동적 계획법과 반대로 문제를 나눌 수 없을 때까지 나누어서 각가 풀고 다시 합병하여 문제의 답을 얻는 알고리즘이다.

ex) 병합 정렬, 퀵 정렬

⇒ 둘 다 작은 문제로 쪼개서 푸는 방식. 차이점이라면 memoization 기법이다.

< 피보나치 수열 동적 계획법 알고리즘 >

def fibo(num):
	if num <= 1:
			return num
	return fibo(n-1)+fibo(n-2)

fibo(4) 를 넣는다고 하면 fibo(4)는 fibo(3)+fibo(2), fibo(3)은 fibo(2)+fibo(1), fibo(2)=fibo(2)+fibo(1)이다. 그런데 이렇게 하면 재귀함수를 계속 사용하기 때문에 시간이 오래걸린다. 그러므로 동적계획법을 사용한다.

---

Dynamic programming 활용

def fibo_dp(num):
    cache = [ 0 for index in range(num+1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num+1):
        cache[index] = cache[index-1]+cache[index-2]
    return cache[num]

print(fibo_dp(10))

한번 캐시에 저장된 값은 다시 계산하지 않아도 된다.

이해가 안되면 코드진행이 어떻게 되는지 보자 ! 오늘 공부할 당시는 이해가 되었다 ㅎㅎ

---

알고리즘을 공부할 때 팁은 한 분야별로 연이어 관련된 문제를 계속 풀어보는 것이 도움이 된다.

그래야 처음 문제를 보았을 때 어떤 알고리즘을 이용해서 풀어야 하는지 알 수 있다.

---

백준 문제 풀이

동적 계획법에 대한 문제 2가지를 풀었다. 점화식을 찾는게 중요하다고 한다. 쉬운 문제인데도 그림을 그려서 풀어야 이해가 되었다. 한동안은 모든 손으로 써서 문제의 해답을 찾아가야 할 것 같다.

((코드 작성 패턴))

1. 빈리스트 만들기
2. 초기값 설정
3. 점화식 기반으로 계산값 적용하기
4. 특정 입력값에 따른 계산값을 리스트에서 추출하기

• 2 * n 타일링 - 11726번

    n = int(input())
    dp = [0] * 1001
    dp[1] = 1
    dp[2] = 2
      
    for index in range(3, 1001):
    	dp[index] = dp[index-1] + dp[index-2]
      
    print(dp[n]%10007)
  

• 파도반 수열

    T = int(input())
  
    dp = [0] * 101
    dp[1], dp[2], dp[3] = 1,1,1
    for index in range(1,98):
        dp[index+3] = dp[index] + dp[index+1]
  
    for i in range(T):
        N = int(input())
        print(dp[N])