DP에는 크게 두 가지 문제풀이 방법이 있다.1) 재귀함수2) for문 1번의 경우 앞서 다른 포스팅에서 다뤘던 Memoization을 사용한다면,2번의 경우 순서대로 배열에 값을 채워가는 방식인 Tabulation을 사용한다. (이전에 작성한 Memozation, 재귀함수 방식) [알고리즘] DP 풀이에서의 메모이제이션 MemoizationDP 외에도 DFS/BFS 등등 여러 유형의 알고리즘에서 재귀함수를 사용할 때면 종종 마주쳤던 효율성 이슈,,그럴 수밖에 없는 것이, 재귀를 사용하면 하나의 해답을 얻기 위해 정말 많은 반복적인 연jimyu-s-record.tistory.com set dp = [0, 0, 0, ...]dp[1] = 1dp[2] = 1for i = 3 ... i 이런 Tabulat..
dp
이전에 스터디에서 작성한 DP 개념글을 업로드했지만, 이번 알고리즘 스터디에서 코드트리로 개념을 다시 보다 보니 문제풀이 부분이 더 깔끔한 것 같아서 풀이 방식 위주로 다시 정리해 본다. 1. for loop 이용(점화식)초기값 설정해 주고, 그 이후에 대해서는 점화식으로 표현하면 된다.F[1] = 1for i = 2 ... i 2. 재귀함수 이용종료조건으로 초기 조건 넣어주기, 이외에는 점화식 이용function f(n) if n == 1 return 1 else return f(n - 1) * nprint(f(n)) 결국 DP는 점화식 기반의 풀이 방법이라고 할 수 있다. 다만 그것을 for loop / 재귀 중 무엇으로 표현하느냐 차이. 유의사항DP 구현에 있..
예전 공부 자료 뒤적이다 찾은 작년 스터디 자료!ㅎㅎ 노션에 숨겨져 있다 보니 찾기 힘들어서 여기에도 옮겨놓는다. 1. DP(Dynamic Programming, 동적 계획법)란?? 큰 문제를 작은 문제로 나누어서 푸는 방법 💡 분할 정복(Divide and Conquer) vs DP 둘 다 큰 문제를 작은 문제로 나누는 거 아닌가요? ⇒ 분할정복은 작은 문제 중복 불가, DP는 가능! 이름에는 아~무 의미가 없다!ㅎ Richard Bellman이 1950년대에 그냥 멋있어서 이름을 이렇게 붙였다고,, 쉽게 말해서 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 2. DP 사용 조건 겹치는 부분 문제가 있을 때(Overlapping Subproblem) 큰 문제를 작은 문제로 나눌 수 있는 경우..
