[sw 사관학교 정글] [WEEK04] WIL 04주차 개발일지

4주차: 동적프로그래밍, 그리디 알고리즘

어려운 개념 보다는 머리를 많이 써야하니 집중을 하고 생각하는 주간을 보내자

*4주차의 경우 별도의 알고리즘 정리를 추가적으로 진행해서, 추후 더 자세한 내용 별도 포스팅 예정

 

다이나믹 프로그래밍

필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 설계기법

큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 ‘분할 정복' 알고리즘이 있다.

이때 동일한 작은 문제들이 반복적으로 계산되는 경우가 생길 수 있다. 그 문제를 매번 재계산 하지 않고 값을 저장했다가 재사용하는 기법이 바로 다이나믹 프로그래밍이다.

메모리 공간을 약간 더 사용해서 시간을 획기적으로 줄일 수 있는 방법( 메모리 공간이 여유로운데 시간이 짧으면 사용(?))

다이나믹 프로그래밍의 다이나믹은 동적 할당의 다이나믹과 아무런 관계가 없다

 

조건

1. 최적 부분 구조
2. 큰 문제를 작은 문제로 나눌 수 있다. 이런 작은 문제의 답을 모아 큰 문제를 해결
3. 중복된 하위 문제
4. 동일한 작은 문제를 반복적으로 해결

Topdown

• 메모제이션
• 한번 구한 계산 결과를 메모리 공간에 메모, 같은 식을 다시 호출하면 메모 결과 그대로 가져오는 기법
• 하향식
• 재귀함수를 이용해 구현

Bottom-up

• 타블레이션
• 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법
• 작은 문제부터 큰 문제까지 하나하나 테이블을 채워나감
• 상향식
• 전형적인 형태는 bottomup 방식
• 반복문을 이용하여 구현

lru_cache

피보나치 수열 문제와 같은 다이나믹 프로그래밍(Dynamic Programming) 문제를 functools의 lru_cache를 이용해 해결할 수 있다. 사용 방법은 간단하다. 점화식을 이용해 재귀 함수를 작성하고, 파이썬의 lru_cache 데코레이터(decorator)를 이용하여 함수가 반환하는 값을 메모이제이션(memoization)할 수 있다. 일반적으로 메모이제이션은 캐싱(caching)과 유사한 의미를 갖는다.

흔히 다이나믹 프로그래밍 문제를 풀 때는 별도의 공간에 함수의 결과를 기록할 필요가 있는데, lru_cache를 사용하면 그럴 필요가 없어지는 것이다.

출처: https://ndb796.tistory.com/596

점화식을 찾기 어렵다면

어떻게 DP or Memoization 테이블을 만들면 좋을지 생각해보고

문제에서 주어진 예시 OR 테스트 케이스를 직접 그려본 다음

규칙성을 통해 점화식을 찾아야 한다.

대표유형

knapsack problem(배낭문제, 동전)

LIS(가장 긴 증가하는 부분 수열)

LCS(최장 공통 문자열) *LCS가 두개임

• 2차원 배열을 이용하여 두 문자열을 행,열에 매칭
  1. 문자열A, 문자열B의 한글자씩 비교해봅니다.
  2. 두 문자가 다르다면 LCS[i][j]에 0을 표시합니다.
  3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 합니다.
  4. 위 과정을 반복합니다.

 

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = 0

LCS(최장 공통 부분 수열)

• 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열중 가장 긴것을 찾는 문제
  1. LCS 배열의 가장 마지막 값에서 시작합니다. 결과값을 저장할 result 배열을 준비합니다.
  2. LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾습니다.2-1. 만약 같은 값이 있다면 해당 값으로 이동합니다.2-2. 만약 같은 값이 없다면 result배열에 해당 문자를 넣고 LCS[i -1][j - 1]로 이동합니다.
  3. 2번 과정을 반복하다가 0으로 이동하게 되면 종료합니다. result 배열의 역순이 LCS 입니다.

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence