다이나믹 프로그래밍

최장 증가 부분 수열 (LIS)

개념 어떤 임의의 수열이 주어졌을 때, 수열에서 앞에서부터 차례대로 몇 개의 숫자들을 뽑아서 부분수열을 만들 수 있다. 이렇게 만들 수 있는 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 한다. 예를 들어 [5, 2, 1, 4, 3, 5] 라는 수열이 있다고 가정해보자. 해당 수열에서 최장 증가 부분 수열에 해당하는 수열은 무엇일까? 세번째에 있는 숫자 1을 꺼낸다. 다섯번째에 있는 숫자 3을 꺼낸다. 여섯번째에 있는 숫자 5를 꺼낸다. 이렇게 만들어진 수열 [1, 3, 5]가 위 수열에서 만들 수 있는 최장 증가 부분 수열에 해당하고 길이는 3이 된다. 구할 수 있는 방법에는 크게 2가지가 있고 시간 복잡도에서..

[C++] Dynamic Programming (동적계획법) / Top-Down (탑다운)과 Bottom-Up (바텀업) 방식

I. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다는 것이 핵심이다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. (우리가 평소에 문제를 풀이할 때 효율적인 방법으로 고안할 필요가 있다.) 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운-하향식, 바텀업-상향식)으로 구성된다. 매우 비효율적인 문제더라도 다이나믹으로 획기적으로 시간을 줄일 수 있다. 다이나믹 프로그래밍은 조건을 만족해야 사용할 수 있다. 최적 부분 구조 - 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제를 모아서 큰 문제를 해결 중복 부분 문제 - 동일..