Data Structure & Algorithm
3주차 - DP는 재귀가 반복하는 일을 기억해두는 것, 피보나치와 계단 오르기로 확인
재귀가 같은 하위 문제를 계속 반복 계산할 때 memo로 기억해두는 하향식(탑다운) DP와, 밑바닥 값부터 채워 올라가는 상향식(바텀업) DP를 피보나치 수열과 계단 오르기 문제로 각각 구현.
dp
하나의 주제로 이어지는 배움의 기록.
2개의 기록 최신순
Data Structure & Algorithm
3주차 - LCS(최장 공통 부분수열)를 DP 테이블로 구하기
두 문자열을 각각 행과 열에 두고, 같으면 대각선 위에 1을 더하고 다르면 위/왼쪽 중 최댓값을 가져오는 방식으로 LCS 길이를 채워나가는 DP 테이블 구현.