본문 바로가기

알고리즘/동적 계획법(DynamicProgramming)

 (2)
[알고리즘] 최장 공통 부분 수열(LCS) - 코딩밥상 최장 공통 부분 수열(Longest Common Subsequence)이란? '공통 부분 수열'은 말 그대로 두개 이상의 수열 사이에 공통으로 존재하는 부분 수열을 말합니다. 따라서 '최장 공통 부분 수열(LCS)'은 여러개의 공통 부분 수열 중 가장 긴 부분 수열을 말합니다. 이 LCS 알고리즘은 두 데이터를 비교할 때 아주 유용합니다. LCS 문제를 동적 계획법으로 풀기 전에 이 문제가 최적 부분 구조로 이루어져 있는지 먼저 확인해야겠네요. X = {x1,x2,x3,...,xi} 와 Y = {y1,y2,y3,...,yj}인 두 문자열이 있다고 하고, 이 두 문자열을 매개 변수로 받아 이들 사이에서 나올 수 있는 LCS의 '길이'를 구하는 함수를 LCS( )라고 하면, 다음과 같은 점화식을 세울 수 있..
[알고리즘] 동적 계획법(DP) - 코딩밥상 동적 계획법(Dynamic Planning)이란?  동적 계획법이란 어떤 문제가 여러 단계의 반복되는 부분 문제로 이루어졌을 때, 각 단계에 있는 부분 문제의 답을 기반으로 전체 문제의 답을 구하는 방법을 말합니다. 앞서 배운 분할 정복은 문제를 위에서부터 아래로 쪼개지만(Top-Down), 동적 계획법은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어 올라갑니다(Bottom-Up). 또한 분할 정복 기법으로 쪼갠 각 부분 문제는 완전히 독립적인 문제로 다룰 수 있지만, 동적 계획법에서 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존합니다. 무엇보다 동적 계획법은 분할 정복과 달리 한 번 푼 적 있는 부분 문제의 답을 다시 푸는 일이 없도록 테이블 등에 저장합니다. 저장하는 부..

티스토리툴바