[알고리즘] 최장 증가하는 부분 수열 알고리즘(완전 탐색, DP, 이분 탐색, 세그먼트 트리)
BE_개발자
[알고리즘] 최장 증가하는 부분 수열 알고리즘(완전 탐색, DP, 이분 탐색, 세그먼트 트리)자료구조 | 알고리즘/동적 계획법2023. 11. 29. 17:38@BE_개발자
Table of Contents
728x90
반응형

[목차]

  1. LIS란?
  2. LIS를 구하는 알고리즘
    1. 완전 탐색 알고리즘
      1. 분할 정복
      2. 백트래킹
      3. 두 완전 탐색 알고리즘의 비교
    2. 동적 계획법 알고리즘
      1. O(N²) 풀이
      2. 이분 탐색을 이용한 풀이
      3. 두 동적 계획법 알고리즘 비교
    3. 세그먼트 트리 알고리즘
  3. LIS의 대표 예제
    1. 전깃줄 문제
    2. 줄세우기 문제
    3. 합친 LIS

1. 가장 긴 증가하는 부분 수열(LIS)이란?

증가하는 부분 수열을 중에서 길이가 가장 긴 수열을 말한다. 영어로는 줄여서  LIS(Longest Increasing Subsequence)라고 한다.

여기서 잠깐 LIS의 S가 subarray가 아니라 subsequence의 이유를 보면 다음과 같다.

부분 수열의 종류는 크게 subarray와 subsequence가 있다. subarray는 연속적으로 이어져있는 부분 수열을 말하고 subsequence는 원소들이 원래의 배열처럼 연속적으로 이어져 있지 않아도 되는 부분 수열이다.

 

예를 들어 다음과같은 수열 S(n)을 보자.

S(n) = {10,   20,   10,   30,   20,   50}

 

수열 S(n)에 대하여 다음과 같이 총 5개의 증가하는 부분 수열을 만들 수 있다.

{10,   20,   30,   50}
{20,   30,   50}
{10,   30,   50}
{30,   50}
{20,   50}

 

이 중에서 LIS는  {10,   20,   30,   50}이 되는 것이다.

 

부분 수열 문제는 배낭 문제(knapsack problem)의 특수한 경우이다.

또한 컴퓨터 과학과 수학의 분야에서 많이 연구되는 주제이기도 하다.

이 페이지에서는 LIS를 구하는 세 가지 알고리즘에 대해 아주 자세히 알아보고 각각의 알고리즘을 분석해보며 예제를 소개한다.

특히 백트래킹의 진행 과정을 아주 자세히 다룰 예정이다. 따라서 배경지식이나 이해도가 있는 사람은 구체적인 부분은 넘기며 읽기를 바란다. 또한 바로 동적 계획법의 풀이를 보고 싶은 사람은 완전 탐색의 풀이를 넘기길 바란다.

2. LIS를 구하는 알고리즘

원래 주어진 수열을 S라고 하자.

S(n) = {10,   20,   10,   30,   20,   50}

 

LIS를 구하는 방법에는 크게 세 가지가 존재한다. 완전 탐색, 동적 계획법, 세그먼트 트리

1) 완전 탐색(Brute Force) 알고리즘

완전 탐색 알고리즘은 분할 정복과 백트래킹 두 가지 방법으로 구현할 수 있다.

(1) 완전 탐색1: 분할 정복

아이디어

단순히 모든 경우의 수를 탐색한다. 모든 부분 집합 문제라고 볼 수 있으므로 배낭 문제처럼 모든 조합의 경우를 탐색한다.

앞의 예시에서 LIS가 만들어지는 과정을 보면 규칙이 보인다.

 

pivot을 정하고 나면 pivot보다 크고 오른쪽에 있는 원소만 원래의 배열에 붙일 수 있다.

따라서 위의 규칙에 따라 모든 조합의 경우를 탐색하면 다음과 같이 두 가지를 고려해야 한다.

  1. 현재 원소를 넣는 경우 → pivot보다 큰 경우
  2. 원소를 넣지 않는 경우 → pivot보다 작거나 같은 경우

 

알고리즘 순서

분할 정복은 가장 쉽게 구현할 수 있는 알고리즘이다. 알고리즘의 순서는 다음과 같다.

  1. 현재 원소를 넣고 탐색하는 경우와 넣지 않고 탐색하는 경우를 모두 고려한다.
  2. 재귀 함수로 전의 과정을 반복한다.
  3. 기저 사례(base condition)는 모두 탐색했을 때(재귀의 깊이 = N)이다.

 

알고리즘 구현

위의 예시에서 볼 수 있듯이 더 이상 붙일 부분수열이 없거나 마지막까지 탐색한 경우가 기저사례이다.

첫 번째 코드는 간단한 완전 탐색으로 구현하였다. 모든 원소들이 양수라고 가정하고 시작 함수의 last 인자를 -1로 하였다.

#include <iostream>

using namespace std;
int N;
int S[1000];

int LIS(int cur, int last){
    if(cur == N) return 0;
    
    if(S[cur] <= last) return LIS(cur+1, last);
    return  max(LIS(cur+1, last), 1 + LIS(cur+1, S[cur]));

    
}
int main()
{
   cin >> N;
   for(int i=0; i<N; i++) cin >> S[i];
   cout << LIS(0, -1);
   return 0;
}

 

알고리즘 분석

최악의 경우를 가정해 보자.

N이 너무 커지면 공간이 부족해지므로 N = 3이라고 하고 S = {1, 2, 3}이라고 가정하자.

[알고리즘의 진행 과정] 

위의 알고리즘을 적용하면 각각의 재귀 호출마다 얻을 수 있는 수열은 두 가지이다.

  1. last보다 큰 경우 → 자기 자신의 수열에 다음의 호출에서 구해진 LIS가 붙은 수열
  2. last보다 작거나 기저 모두 탐색한 경우 → 자기 자신의 수열

따라서 각각의 재귀 호출마다 두 분기로 갈라진다.

첫 번째 코드의 상태 공간 트리: 1(넣는 경우)와 0(넣지 않는 경우)로 나누어진다.

[알고리즘의 시간 복잡도]

넣는 경우와 안넣는 경우로 분기가 나누어지므로 시간 복잡도는 O(2ⁿ)이 자명하다.

최악의 경우 전체 경로를 탐색 하므로 이를 상태 공간 트리로 나타내면 다음과 같다.

N = 3이었으므로 전체 총 8(2³)가지 경우를 탐색 한다.

기본적인 분할 정복으로 구현한 코드의 상태 공간 트리

 

(2) 완전 탐색2: 백트래킹

아이디어

분할 정복은 아무리 모든 경우를 탐색한다 하더라도 불필요한 경우까지 다 탐색한다.

예를 들어 다음과 같이 중간에 길이가 n인 감소하는 부분 수열이 생길 경우 탐색할 필요가 없다.

S(n) = {10,   20,   18,   17,   16,   . . . , 10,   10,   30,   20,   50}

하지만 분할 정복은 이를 무조건 탐색하므로 현재까지 모든 경우에 대해 불필요한 2ⁿ의 경우가 더 생기게 된다.

그러므로 불필요한 경우를 미리 제거하여 필요한 수열만 탐색하도록 백트래킹을 이용한다.

따라서 백트래킹을 이용하여 가지치기하면 완전 탐색이라도 최악의 완전 탐색은 피할 수 있다.

백트래킹의 가장 중요한 아이디어는 필요한 탐색만 하기 위해 미리 pivot의 뒤에 붙일 수 있는 부분수열을 만들고 만들어진 부분 수열만 탐색하도록 한다.

알고리즘 순서

  1. 하나의 원소를 pivot으로 정하고 pivot의 오른쪽에 있는 원소들 중 pivot보다 큰 원소로만 이루어진 부분 수열(A)을 만든다.
  2. 앞에서 만든 부분수열을 재귀 함수로 전달하여 앞의 과정을 반복하고 LIS를 구하고 가장 큰 LIS를 원래 수열에 붙인다.
  3. 백트래킹을 이용하여 pivot을 순차적으로 증가시키며 조합의 경로를 탐색한다.
  4. 기저 사례는 더이상 추가할 수열이 없는 경우이다.

이 알고리즘에서는 부분 문제를 정의하고 backtracking으로 1~2의 과정을 적용하는 것이 핵심이다. 

 

알고리즘 구현

먼저 알고리즘을 구현하기 위하여 백트래킹으로 완전 탐색을 하기 부분 문제를 정의하고 LIS() 함수를 정의한다.

  1. 부분 문제: pivot보다 오른쪽에 있고 큰 원소로 이루어진 부분 수열을 만들고 붙인 수열들 중 길이가 가장 큰 것이 구하고자 하는 LIS이다.
  2. LIS()함수: 주어진 수열을 반복문으로 탐색하며 각각의 탐색마다 현재의 오른쪽에 있고 큰 원소로 이루어진 부분 수열을 만들고 재귀 함수로 전달하여 가장 긴 부분 수열의 길이를 반환하는 함수

다음은 위의 부분 문제로 LIS()함수를 정의하고 구현한 코드이다.

//백트래킹
#include<iostream>
#include<vector>

using namespace std;

vector<int> S;
int N;

//i번째에 대해 i+1 ~ N-1까지 순회하며 각각의 LIS를 반환하는 함수:
int LIS(const vector<int>& A) {
	//base condition
	if (A.empty()) return 0;
	int ret = 0;
	for (int i = 0; i < A.size(); i++) {
		vector<int> B;
		for (int j = i + 1; j < A.size(); j++) {
			if (A[j] > A[i]) B.push_back(A[j]);
		}
		ret = max(ret, 1 + LIS(B));
	}
	return ret;
}

int main(void) {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		S.push_back(num);
	}
	cout << LIS(S);

	return 0;
}

알고리즘 분석

[알고리즘의 진행 과정] 

위의 알고리즘을 적용하면 각각의 pivot마다 얻을 수 있는 수열은 두 가지이다.

  1. 자기 자신의 수열에 다음의 호출에서 구해진 LIS가 붙은 경우
  2. 자기 자신의 수열(더 이상 붙일 부분 수열이 존재하지 않는 경우)

 

도입부의 예시처럼 원래 주어진 수열을 S를 S(n) = {10,   20,   10,   30,   20,   50}라 하고 탐색 과정을 자세히 살펴 보자.

S(n) = {10,   20,   10,   30,   20,   50}

 

다음은 이 알고리즘을 수열 S에 적용했을 때 탐색하는 과정이다. 글이 길어지므로 접은글로 작성하였다.
(보고 싶은 사람은 클릭)

더보기

예를 들어 S(1)을 pivot으로 설정하고 탐색한 경우를 살펴 보자.

S(n) = {10,   {20,   10,   30,   20,   50} }

 

S(1)보다 크고 오른쪽에 있는 수들을 탐색하여 뒤에 붙일 수 있는 최대의 증가하는 부분 수열을 구한다.

 

이때 부분 수열을 만들 때 가장 중요한 두 조건은 두 가지이다.

  • pivot보다 오른쪽에 있어야 한다.
  • pivot보다 커야 한다.

따라서  j 는 i + 1 부터 n - 1까지 탐색한다.

 

위의 S(1)의 호출은 기본 호출이고 다음 호출부터가 재귀 호출이다.

다음은 기본 호출 이후 백트래킹을 이용해 조합의 경로를 재귀 호출로 탐색하는 과정이다.

중첩된 괄호의 수만큼 함수가 호출된다. 

 

[첫 번째 재귀 호출 결과]

S(n) = {10,   {20,   10,   30,   20,   50} }
j = 3, 5 

 

pivot은 20이고 pivot의 오른쪽에 있는 수 중 pivot보다 큰 수만으로 이루어진 부분수열 A를 만든다.

만들어진 부분 수열은 {30, 50}이다.

 

[두 번째 재귀 호출 결과]

S(n) = {10,   {20,   {10,   30,   20,   50} } }
j = 3, 4, 5 

 

pivot은 10이고 pivot의 오른쪽에 있는 수 중 pivot보다 큰 수만으로 이루어진 부분수열 A를 만든다.

만들어진 부분 수열은 {30, 20, 50}이다.

 

[세 번째 재귀 호출 결과]

S(n) = {10,   {20,   {10,   {30,   20,   50} } } }
j = 5  

 

pivot은 30이고 pivot의 오른쪽에 있는 수 중 pivot보다 큰 수만으로 이루어진 부분수열 A를 만든다.

만들어진 부분 수열은 {50}이다.

. . .

(같은 방법으로 다섯 번째 호출까지 호출된다)

. . .

[다섯 번째 재귀 호출 결과]

S(n) = {10,   {20,   {10,   {30,   {20,   {50} } } } } 

 

pivot은 50이고 pivot의 오른쪽에 있는 수 중 pivot보다 큰 수만으로 이루어진 부분수열 A를 만든다.

그런데 만들 수 있는 부분수열은 존재하지 않는다. 이는 코드로 구현할 때 base condition으로 이용한다.

이후 다섯 번째 호출을 종료하고 네 번째 호출로 돌아간다.

. . .

 

이렇게 백트래킹으로 재귀 호출을 반복하면서 마지막까지 탐색을 끝내고 나면 스택의 구조에 따라 역순으로 전의 호출로 돌아온다!

. . .

세 번째 호출로 돌아온 경우를 보자.

 

[세 번째 호출]에서 얻어진 LIS는 다음과 같이 두 가지이다.

30 + {50} : pivot이 30일 때 {50}이 붙은 값
20 + {50} : pivot이 20일 때 {50}이 붙은 값
50 + { } : pivot이 50일 때 아무 것도 붙지 않은 값

 

세 번째 호출의 LIS의 길이는 2로 같으므로 2를 반환한다. 이후 세 번째 호출을 종료하고 두 번째 호출로 돌아간다.

 

[두 번째 호출]에서 구해지는 LIS는 다음과 같다.

10 + {30, 50} : pivot이 10일 때 {30, 50}이 붙은 값
30 + {50} : pivot이 20일 때 {50}이 붙은 값
20 + {50} : pivot이 20일 때 {50}이 붙은 값
50 + { } : pivot이 50일 때 아무 것도 붙지 않은 값

 

두 번째 호출의 LIS의 길이는 3이 최대이므로 3을 반환한다. 이후 두 번째 호출을 종료하고 첫 번째 호출로 돌아간다.

 

[첫 번째 호출]에서 구해지는 LIS는 다음과 같다.

20 + {30, 50} : pivot이 20일 때 {30, 50}이 붙은 값
10 + {30, 50} : pivot이 10일 때 {30, 50}이 붙은 값
10 + {20, 50} : pivot이 10일 때 {20, 50}이 붙은 값
30 + {50} : pivot이 30일 때 {50}이 붙은 값
20 + {50} pivot이 20일 때 {50}이 붙은 값
50 : pivot이 50일 때 아무 것도 붙지 않은 값

 

첫 번째 호출의 LIS의 길이는 3이 최대이므로 3을 반환한다.

 

위의 예시를 보면 첫 pivot을 S(1)로 설정했기 때문에 S(1)에서 시작했을 때 얻을 수 있는 최대 LIS의 길이를 구한 것이다.

 

따라서 첫 pivot을 S(0)으로 설정하면 S(0)에서 시작했을 때 LIS의 최대 길이를 얻게된다.

여기서 볼 수 있듯이 LIS(n)은 S(n)으로 시작했을 때 얻을 수 있는 LIS의 길이를 반환한다.

 

[알고리즘의 시간 복잡도]

이 알고리즘의 시간 복잡도는 반복분과 재귀 함수가 섞여 있어 O(N³) 또는 O(N x 2ⁿ)처럼 보인다. 나는 이 알고리즘의 상태 공간트리를 분석하기 전까지 O(N x 2²)이라고 생각하고 있었다.

알고리즘의 시간 복잡도를 분석하기 위해 최악의 경우를 가정해 보자.

N이 너무 커지면 공간이 부족해지므로 N = 3이라고 하고 S = {1, 2, 3}이라고 가정하자.

LIS()함수를 주어진 배열을 탐색하며 만들 수 있는 증가하는 부분 수열의 최댓값을 반환하는 함수라고 정의하였다.

전체 탐색 결과 상태 공간 트리로 나타내면 다음과 같다.

백트래킹 알고리즘의 상태 공간 트리

N = 3일 때 8번 탐색한다. 2³이 된다는 소리이다.

다음 접은글은 백트래킹 알고리즘의 진행 구조를 아주 자세하게 나타낸 글이다. 글이 길어지므로 접은글로 표현하였다. (위의 그림만으로 이해가 안되거나 더 깊은 이해가 필요한 사람들은 클릭!)

더보기

반복문을 순회하며 각각 재귀를 호출하는 상태 공간 트리의 구조를 자세히 살펴 보자.

함수 내에서 반복문이 섞여 있더라도 선형 탐색이 우선이 아니라 재귀 호출이 우선이 된다.

반복문을 돌며 재귀를 호출하는 알고리즘의 진행 과정

 위의 구조의 진행 순서를 보자! DFS의 탐색이 끝난 후 마지막 깊이까지 간 후에 선형탐색을 하는 것을 알 수 있다.

따라서 선형 탐색이 우선이 아니라 재귀 호출이 우선이다. 선형으로 계속 순회하지 않고 N번 재귀 호출이 일어난다.

결국 겉으로 보기엔 선형으로 순회하는 것 같지만 사실 재귀 호출이 최우선적으로 일어난다!

  1. S(n) 넣고 탐색하는 경우 - 1
  2. S(n)을 넣지 않고 탐색하는 경우 - 0

이를 일반화해서 나타내보자.

[첫 번째 재귀 호출]

S(0)을 넣고 탐색하는 경우와 S(0)을 넣지 않고 탐색하는 경우로 분기가 나뉘어 탐색한다.

재귀가 한 번 호출되었는데 2개의 반복되는 S(1)이 생겻다. 

한번 더 확장해 보자.

[두 번째 재귀 호출]

두 번째 호출에서는 S(1)을 넣고 탐색하는 경우와 S(1)을 넣지 않고 탐색하는 경우로 분기가 나뉘어 탐색한다.

그런데 앞에서 이미 S(0)이 두 번 탐색이 일어나므로 각각에 대해서도 2번씩이다. 따라서 S(2)는 총 4번 호출된다.

재귀가 두 번 호출되었는데 4개의 반복되는 S(2)이 생겻다. 

이로부터 귀납적으로 다음과 같은 사실을 도출할 수 있다.

재귀가 n번 호출되면 2ⁿ개의 반복되는 부분 문제가 생긴다. 

백트래킹 알고리즘의 진행 순서를 간략히 상태 공간 트리로 나타내면 다음과 같다.

반복문을 돌며 재귀를 호출하는 알고리즘의 진행 과정
일반화하여 확장되는 구조
귀납적으로 얻은 결론

백트래킹도 결국 반복문을 순회하며 반복 횟수(n)만큼 지수적(2ⁿ)으로 반복되는 것이다.

따라서 시간복잡도는 O(2ⁿ)이 된다.

 

(3) 정리: 두 완전 탐색 알고리즘 비교

기본적인 분할 정복으로 구현한 코드의 상태 공간 트리

백트래킹으로 구현하면 그나마 불필요한 탐색을 줄일 수 있지만 어쨋든 시간복잡도가 O(2ⁿ)이 되는 것을 막을 수 없다.

따라서 완전 탐색 알고리즘은 분할 정복을 이용하던, 백트래킹을 이용하던 무조건 O(2ⁿ)이 된다.

 

2) 동적 계획법(Dynamic Programming) 알고리즘

동적 계획법을 이용하면 더 빠른 시간 복잡로 LIS를 해결할 수 있다.

 

(1) 동적 계획법

아이디어

동적 계획법은 항상 완전 탐색으로부터 다음 두 가지의 특징을 발견하는 것으로 시작한다.

  1. Optimal Substructure (최적 부분 구조)
  2. Overlapping Subproblems (반복되는 부분 문제들)

전의 완전 탐색 알고리즘으로부터 동적 계획법의 아이디어를 도출해 보자.

분할 정복과 백트래킹을 이용한 완전 탐색 알고리즘의 탐색 경로

[1. Optimal Substructure]

파란색 부분 문제와 빨간색 부분 문제들은 서로 영향을 미치지 않는다.

 

상태 공간 트리를 보면,

현재 원소 S(n)을 넣고 탐색하는 경우에서는 이 전의 입력이나 다음의 입력이 무엇인지 알 필요가 전혀 없다.

현재의 재귀 호출은 다른 재귀의 부분 문제들에 영향을 주지 않기 때문이다.

즉 각각의 부분 문제들이 독립적이다.

따라서 Optimal Substrcture이 보장되는 것을 알 수 있다.

[2. Overlapping Subproblems]

분할 정복을 이용한 완전 탐색에서 반복되는 부분 문제들
백트래킹을 이용한 완전 탐색에서 반복되는 부분 문제들

위의 상태 공간 트리를 보면,

S(1)을 넣고 탐색하는 부분 문제 1과 S(1)을 넣지 않고 탐색하는 부분 문제 1이 반복된다.

이후 나누어지는 각각의 탐색에 대해서도 ,

S(2)을 넣고 탐색하는 부분 문제 2와 S(2)을 넣지 않고 탐색하는 부분 문제 2가 반복된다.

하위 부분 문제들은 지수적(2ⁿ)으로 반복 된다.

실제로 위의 완전 탐색 알고리즘의 수행과정에서도,

두 번째 재귀 호출의 부분 문제가 세 번째 재귀 호출의 부분 문제와 겹치는 것을 알 수 있다.

자세한 예시는 접은글로 작성하였다. (궁금한 사람은 클릭)

더보기

세 번째 호출에서 LIS를 구하는 부분 문제

30 + {50} : pivot이 30일 때 {50}이 붙은 값
20 + {50} : pivot이 20일 때 {50}이 붙은 값
50 + { } : pivot이 50일 때 아무 것도 붙지 않은 값

 

세 번째 호출의 LIS의 길이는 2로 같으므로 2를 반환한다. 이후 세 번째 호출을 종료하고 두 번째 호출로 돌아간다.

 

두 번째 호출에서 LIS를 구하는 부분 문제

10 + {30, 50} : pivot이 10일 때 {30, 50}이 붙은 값
30 + {50} : pivot이 20일 때 {50}이 붙은 값
20 + {50} : pivot이 20일 때 {50}이 붙은 값
50 + { } : pivot이 50일 때 아무 것도 붙지 않은 값

 

두 번째 호출에서 순차탐색하며 pivot에 LIS를 붙이는 부분 문제는

세 번째 호출에서 pivot을 증가시키며 LIS를 붙이는 부분 문제와 겹친다. 

즉, pivot을 바탕으로 넣는 경우와 넣지 않는 경우의 분기점이 생기는데 분기점마다 반복되는 부분 문제들이 기하급수적으로 생긴다.

따라서 동적 계획법의 두 가지를 충족하므로 solution을 바탕으로 memoization할 수 있다.

 

알고리즘 순서

Top - Down과 Bottom - Up 두 가지로 구현할 수 있다.

[Bottom - Up 방식]

Bottom - Up 방식은 시작 값을 고정하여 현재 원소로 시작했을 때 LIS를 memoization하였다.

  1. 처음의 탐색에서 현재 원소로 시작했을 때 구할 수 있는 LIS의 최대 길이를 D[i]에 저장한다.
  2. 다음의 탐색에서 D[i]가 memoization되어있으면 앞의 값을 이용하고 비어있는 경우 앞의 과정을 반복한다.
  3. 탐색할 때마다 최댓값을 갱신한다.

[Top - Down 방식]

Top - Down 방식은 마지막 값을 고정하여 현재 원소를 추가했을 때 LIS를 memoization하였다.

  1. 전의 원소를 순회하며 현재 원소를 추가했을 때 구할 수 있는 LIS의 최대 길이를 D[i]에 저장한다.
  2. 앞의 과정을 반복한다.
  3. 주어진 수열 S에 대해 모든 원소들의 LIS를 구하고 최댓값 갱신한다.

 

알고리즘 구현

[Bottom - Up 방식]

D[i]를 i번째 원소를 마지막으로 넣었을 때 얻을 수 있는 LIS의 길이로 정의하였다.

[Top - Down 방식]

D[i]를 i번째 원소로 시작했을 때 얻을 수 있는 LIS의 길이로 정의하였다.

#include<iostream>
#include<cstring>

using namespace std;

int N, ans;
int arr[1000];
int D[10000];

int LIS(int start) {
	int& ret = D[start];

	if (ret != -1) return ret;
	ret = 1;
	for (int i = start + 1; i < N; i++) {
		if (arr[i] > arr[start]) ret = max(ret, 1 + LIS(i));
	}
	return ret;
}


int main(void) {
	cin >> N;
	memset(D, -1, sizeof(D));  
	for (int i = 0; i < N; i++) cin >> arr[i];
	for (int i = 0; i < N; i++) ans = max(ans, LIS(i));
	cout << ans;
	
	return 0;
}

 

알고리즘 분석

[Bottom - Up방식]

S = {1, 2, 3}인 경우 Bottom - Up 방식의 상태 공간 트리

반복문을 순회할 때마다 N의 깊이까지 재귀를 호출하며 memoization한다. → N+1번 탐색

main()함수에서 반복문을 순회하며 0부터 N까지 memoization한 값을 이용하여 비교한다. → N번 탐색

따라서 Top -Down방식의 시간복잡도는 O(N²)이다.

[Top - Down방식]

S = {1, 2, 3}인 경우 Top - Down 방식의 상태 공간 트리

처음의 탐색의 경우마다 N의 깊이까지 재귀를 호출하며 memoization한다. → N+1번 탐색

main()함수에서 반복문을 순회하며 0부터 N까지 memoization한 값을 이용하여 비교한다. → N번 탐색

따라서 Top -Down방식의 시간복잡도는 O(N²)이다.

[Bottom - Up 방식과 Top - Down방식 비교]

결론적으로 두 방식 모두 O(N²)이 된다.

iterator을 이용한 Bottom - Up 방식이 recursion을 이용한 Top - Down 방식보다 메모리와 속도면에서 조금 더 빠르다. 

알고리즘 최적화

Top - Down 방식은 최적화가 가능하다.

for (int i = 0; i < N; i++) ans = max(ans, LIS(i));

위의 코드를 보면 main()함수에서 매번 LIS 함수를 호출할 때마다 메모리와 시간이 소요된다.

하지만 이미 LIS(0)을 실행하고 나면 순차적 재귀 호출에 의해 사실상 배열 D(n)에는 S(n)으로 시작했을 때 얻을 수 있는 LIS의 최대 길이가 채워져 있다. 따라서 이후에 함수를 호출하지 않고 바로 D[n]의 값을 가져오는 것이다.

for (int i = 0; i < N; i++) ans = max(ans, D[i]);

 

(2) 동적 계획법2: 이분 탐색을 이용한 트리

아이디어

위의 Bottom - Up  방식을 살펴보면 현재 원소를 넣을 때 최대를 찾기 위해 전의 원소를 선형 탐색했다. 이 부분에서 선형 탐색을 하나씩 순회하는 것이 아니라 이분 탐색으로 진행하면 O(log N)이 되므로 전체 시간 복잡도는 O(N log N)이 된다.

알고리즘 순서

 

 

알고리즘 분석

 

 

 

(3) 동적 계획법의 두 알고리즘 비교

3. LIS 대표 예제

728x90
반응형
저작자표시 비영리

'자료구조 | 알고리즘 > 동적 계획법' 카테고리의 다른 글

[알고리즘] 위상정렬 DP  (0) 2024.04.30
[알고리즘] (수학, 동적 계획법) N/M수 분할 알고리즘 (자연수 분할)  (0) 2023.11.30
[알고리즘] (동적 계획법, DP) 가장 긴 증가하는 부분 수열, LIS(최종본)  (0) 2023.11.25
[알고리즘] 최대 연속 부분수열 합(Miximum subarray) 구하기  (0) 2023.11.24
[알고리즘] 동적 계획법을 이용하여 구간합 구하기(Prefix Sum)  (0) 2023.10.31
BE_개발자
@BE_개발자 :: 경이로운 개발일기

경이로운 BE 개발자가 되기 위한 프로그래밍 공부 기록장

도움이 되었다면 "❤️" 또는 "👍🏻" 해주세요! 문의는 아래 이메일로 보내주세요.

자료구조 | 알고리즘/동적 계획법 추천 글
more
image

티스토리툴바