오늘의 학습 키워드

동적계획법

• DP(다이나믹 프로그래밍) 은 복잡한 문제를 더 작은 단위의 하위 문제로 나누어 해결하는 알고리즘 설계 기법

알고리즘 설계 기법

• 문제 해결을 위해 알고리즘을 설계하는 방법, 접근 방식

알고리즘 기법

• 문제를 해결하기 위해 사용되는 절차적인 방법 또는 계획

DP vs 재귀적 호출의 차이점

하향식 vs 상향식 접근

• 재귀적 호출은 하향식 접근을 사용 : 큰 문제를 작은 하위 문제로 나누어 해결하는 방식
• 동적 게획법은 상향식 접근을 사용 : 작은 하위 문제로부터 시작해 결과 저장하고, 점진적으로 큰 문제의 해를 구하는 방식

메모이제이션

• 중복되는 계산 결과를 저장하는 메모리 기법

DP 기법을 적용시킬 수 있는 조건

1. 중복되는 부분 문제

2. 최적 부분 구조

• 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우 사용

DP 로 문제를 푸는 방법

Bottom-Up : 반복문 사용

• 작은 부분 문제로부터 차례대로 해결하여, 전체 문제를 해결하는 방식
• 반복문을 사용해 부분 문제를 해결하고, 결과를 배열 등에 저장

• 장점 : 모든 작은 문제를 해결하므로 최적 부분 구조를 보장

Top-Down : 재귀 사용

• 큰 문제를 작은 부분 문제로 나누어 해결하는 방식

• 재귀 함수를 사용해 문제를 작게 쪼개고, Memoization 을 활용

• 장점 : 필요한 부분 문제만 해결하므로 시간 절약 가능하며, 구현이 더 간단

• 출처 블로그

공부한 내용 본인의 언어로 정리하기

프로그래머스 피보나치 수

• 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수 완성하기!

어떤 문제가 있었고, 나는 어떤 시도를 했는지

def solution(n):

    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] =1
    
    for i in range(2,n+1):
        dp[i]= (dp[i-1] + dp[i-2])
        
    return (dp[n]%1234567)
    

• 작은 문제부터 시작해서 계산 결과를 dp 라는 리스트에 저장하고 , 이를 이용해 큰 문제의 해를 구하는 방식으로 해결하였다

무엇을 새롭게 알았는지

• 다이나믹 프로그래밍

학습할 것은 무엇인지

• 다양한 문재를 풀어 다이나믹 프로그래밍의 다양한 풀이방법을 적용해보는 연습이 필요할 듯