알고리즘9 동적 프로그래밍(Dynamic Programming)의 개념 DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다. Dynamic Programming 동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다. 위의 코드를 한 번 읽어보자. 1 = 1 2 = 2 + 1 3 = 3 + 2 + 1 ... 100 = 100 + 99 + 98 + ... + 3 + 2 + 1 이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므.. 2019. 10. 7. DP 문제가 잘 안 풀린다. 요즘 DP 문제가 고민인데, DP문제 카테고리의 문제를 봐도 왜 DP인지 잘 모르겠고 (왜 부분 문제가 겹치는지 잘 이해가 되지 않고), 계속 전에 풀었던 문제랑 비슷비슷한 문제만 풀린다. 생각해보니 알고리즘 강의 중에서 DP 강의가 길어서 중간에 하차를 했다. 내일부터는 강의 정주행으로 가자! 2019. 10. 7. [백준] 9251번 LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제를 풀기 전에 알아야 할 개념 : Dynamic Programming LCS란? LCS란 두 문자열 str1과 str2가 있다고 할 때, 공통된(Common) 부분 수열(Substring) 중, 가장 긴 것(Longest)을 의미한다. 여기서 Subsequence의 개념을 명확히 할 필요가 있는데, 원래 문자열의 글자를 몇 개 선택해서 원래 문자.. 2019. 10. 6. 이전 1 2 다음