Greedy와 DP = 동적계획법 : 최적해를 찾기 위한 방법

그리디 = 매 선택에서 지금 가장 최적인 답을 선택하여 결과 도출

ex) 난 동전부자임... 980원을 어떻게 지불해야 좋을까?

-> 500원 1개, 100원 4개, 50원 1개, 10원 3개

구현은 어렵지 않으나 이 문제를 그리디로 풀 수 있다!가 쉽게 안 나올 것임. 연습해라!

다이나믹 프로그래밍 = 복잡한 문제를 간단한 여러 개의 문제로 나누어 풀기

- 피보나치 수열

: 재귀함수로 풀 수 있다.

그러나 이는 에러를 부르기 쉽다! 너무 많이 호출되기 때문.

-> 메모이제이션 memoization = 값을 저장해두고 사용

 

- 탑다운 : 답을 찾기 위해 그 아래 것을 계산

f(5)를 찾기 위해 f(4)와 f(3)을 찾자!

- 바텀 업 : 아래 것 부터 찾으며 올라가면 답이 찾아짐

f(1), f(2), ... 찾자

 

코드는 여기... 과거의 나는 웃겼구나

2. 다이나믹 프로그래밍 (DP) :: OEOEO (tistory.com)

DP를 활용하는 문제 유형

최장 증가 부분 수열 = LIS

어떤 뒤죽박죽 배열에서 가장 긴 증가하는 수열의 크기을 찾아내보자!

arr = list(map(int,input().split()))
dp = [1 for i in range(len(arr))] # 자신과 그 앞의 수들로 LIS를 구하기

for i in range(1, len(arr)): # 모든 수를 돌며
    for j in range(i): # i보다 앞의 모든 수를 돌며
        if arr[i] > arr[j]: # 오름차순 수열이 보이면
            dp[i] = max(dp[i], dp[j]+1) # i의 dp값은 j의 dp값보다 1 큼

print(max(dp))

 

최장 공통 부분 수열 = LCS

공통 부분 문자열 중 가장 길이가 긴 문자열을 찾아보자!

ex) asdfgh  / siufeg 에서 LCS는 sfg 임

 

=> 알고리즘 수업 때 내가 정말정말 좋아하던 파트니까

알고리즘 수업 자료까지 빡빡 긁어서 정식으로 소개하겠음!

후에 문자열에 대한 알고리즘 정리하기✨