1. 동적 계획법이란?동적 계획법이란 해결하고자 하는 문제를 작은 문제로 나누어 해결하고, 작은 문제들의 해들로부터 큰 문제의 답을 구하는 방식입니다. 여기서 중요한 점은 "분할과 정복"과 달리 DP는 분할된 작은 문제들이 상호 독립적이지 않고, 일정 부분을 공유한다는 점입니다. 본인은 편의점 알바를 하고있습니다. 그리고 저는 항상 출근하면 가장 먼저 담배 재고를 조사합니다. 담배를 꺼내 세다보면 맨 오른쪽처럼 10개가 넘어가는 재고들이 종종 있는데, 이런 경우에는 한눈에 몇개인지 들어오지도 않고 이런 것들을 하나하나 다 세다보면 재고 조사에 쓰는 시간이 꽤 길어집니다. 그렇다고 대충 눈대중으로 세고 넘어가기에는 여간 찝찝한게 아니죠.사진 속 모든 담배의 개수를 세야한다고 가정해볼까요?  세줄로 나누어 ..

이번 포스팅에서는 LCS 알고리즘에 대해 아래의 백준 문제를 예제로 소개해보겠습니다.https://www.acmicpc.net/problem/9251 Longest Common Subsequence / Longest Common Substring LCS란 최장 공통 부분 수열(Longest Common Subsequence) 혹은 최장 공통 부분 문자열(Longest Common Substring)을 뜻합니다. LCS를 구하는 알고리즘은 다이나믹 프로그래밍(DP) 알고리즘의 대표적인 유형으로, 어째서 DP인지는 글의 마지막 부분에서 설명하겠습니다.   먼저 최장 공통 부분 수열( Longest Common Subsequence ) 란 두 개 이상의 시퀸스[ACAYKP, CAPCAK]가  주어졌을 때, 가..