티끌 모아 태산

동적 계획법 이란?

1. 조건

▶ 최적 부분 구조 : 기본 문제의 최적해가 부분 문제의 최적해를 포함하고 있는 구조 , 즉 전체 문제의 최적해가 부분 문제의 최적해들로써 구성이 되어있다는 것이다. 예를 들어 A 문제의 부분문제 a, b 가 있을 때 , a, b의 최적해가 a' , b' 라면 A의 최적해가 a' 와 b'로 구성되는 것을 증명한다면 이는 최적부분 구조를 가진다고 할 수 있다.

▶ 부분 문제 반복 : 재귀 알고리즘을 통해 문제를 해결할 때 같은 부분 문제를 계속 반복하여 해결해야 하는 경우 이를 부분 문제 반복 구조를 가진다 할 수 있다.

2. 방식

하나의 문제를 여러개의 하위 문제로 나누어 푼 다음 , 그것을 결합하여 최족적인 목적에 도달한다. 각 하위 문제에 대한 결과를 계산하여 , 이 결과들을 저장하고 같은 문제가 나왔을 경우 저장된 결과를 사용하여 해결한다. 이러한 방법을 통해 계산 횟수를 줄일 수 있다.

분할 정복(divide and conquer) 또한 큰 문제를 작은 문제로 나누어 해결하지만 동적 계획법은 작은 부분문제들이 반복되는 것을 이용하여 문제를 푸는 것이고 분할 정복은 작은 문제 내에서 반복이 일어나는 부분이 없다.

3. 이용

최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용한다.

동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중 최적의 풀이법을 찾아낼 수 있다.

문제에 대한 모든 방법을 충분히 빠른 속도로 처리할 수 있는 경우 최적의 해법이다.

4. memorization

memorizaion을 사용하면 이미 한번 결과를 계산한 부분 문제에 대해서는 반복하여 계산하지 않는다.

위 피보나치 수열을 예로 들면 이미 계산한 f2->f1 과 f3->f2,f1 은 저장되어 있는 결과를 사용한다.

그렇기 때문에 전체 문제에 대한 총 계산횟수를 줄여주며 동적프로그래밍의 시간복잡도를 줄일 수 있다.

5. 관련문제

포도주 시식 [2156]https://www.acmicpc.net/problem/2156

쉬운 계단 수 [10844] https://www.acmicpc.net/problem/10844

팰린드롬 [10942] https://www.acmicpc.net/problem/10942

외판원 순회 [2098] https://www.acmicpc.net/problem/2098

기본 개념

분할정복법이란 주어진 문제를 동일 유형의 하위 문제로 나눈뒤 각각의 작은 문제들을 해결하여 정복하는 방식이다.

분할 정복법은 다음과 같이 크게 3단계의 과정을 통해 진행된다. 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있다.

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다. _divide

• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다. _solve (conquer)

• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다. _combine (merge)

* 장점: 문제를 나누어 해결함으로써 복잡한 문제를 부분적으로 해결하여 병렬형식로 문제를 보다 쉽게 해결한다는 장점이 있다.

* 단점 : 재귀함수를 사용함으로 인해 함수 호출에 의한 오버헤드가 발생

관련문제

쿼드트리 1992번 https://www.acmicpc.net/problem/1992

Z 1074번 https://www.acmicpc.net/problem/1074

부분배열 고르기 2104번 https://www.acmicpc.net/problem/2104

히스토그램 1725번 https://www.acmicpc.net/problem/1725

Greedy Algorithm은 최적해를 구하는 상황에서 사용하는 방법이다.

- 여러 경우 중 최적의 경우의 수를 선택하여 문제를 해결해 나간다.

- 즉, 데이터 간의 관계를 고려하지 않고 수행 과정에서 'greedy(욕심내어)' 데이터를 선택한다.

- 이러한 선택을 '근시안적' 선택이라고도 한다.

- Greedy Algorithm은 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

- 방법이 통하는 문제들은 다음의 특징을 가진다

  1. 한번의 선택이 다른 선택에 전혀 무관한 값이다.

  2. 매 순간의 최적해가 문제에 대한 최적해이다.

- 순간순간마다 최적의 결정을 함을 통해 전체 문제해결에 대해서 가장 최적의 결과를 얻는 것이 보장되어 있지 않다.

- 어느정도 적합한 수준의 해답을 알려주는 알고리즘이다.

- 계산속도가 정확한 알고리즘에 비해서 실행속도가 빠른 경우가 많아 실용적인 사용이 가능하다.

 Greedy Algorithm을 통해 해결한 문제

[백준 13904] 과제

[백준 4796] 캠핑

[백준 1449] 수리공 항승

완전탐색( Exhaustive search )

'무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.

• 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.

완전 탐색 관련 개념

 다음과 같은 개념들이 완전탐색을 통한 문제풀이에 사용되며 문제의 조건과 방식에 따라 적절한 개념을 이용하여 문제 해결 시간을 향상 시킬 수 있다.

1. Brute Force : 가능한 모든 경우에 대해 모두 확인 하여 답을 찾는 방식

2. 비트마스크 : 컴퓨터의 언어인 이진수를 활용하여 정수를 이진수 형태로 표현하여 비트연산을 활용하는 방법

3. 순열 : 서로 다른 개의 원소 n개에서 r(r<=n)개를 뽑아 한 줄로 세우는 경우의 수 

4. DFS (Depth-First Search) : 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

   -관련 개념) 백트래킹 : 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 나아갈 수 없는 상황에서 그 이전 단계로 복귀하는 과정

5. BFS (Breadth-First Search) : 탐색트리의 루트노드부터 목표노드를 만날 때까지 단계별로 횡방향으로 탐색을 진행해 나가는 방식

6. 재귀함수 : 함수 내에서 자기 자신을 다시 호출하는 함수 // 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

완전 탐색과 관련된 백준 의 알고리즘 문제 해결을 통해 완전 탐색에 대해 탐구해보겠다.

1. 2309번 일곱 난쟁이

일곱 난쟁이

* 문제 풀이

https://hroad.tistory.com/27

2. 3085번 사탕 게임

사탕 게임

* 문제 풀이

https://hroad.tistory.com/29

3. 2503번 숫자 야구

숫자 야구

* 문제풀이

https://hroad.tistory.com/28

3. 1182번 부분수열의 합

부분수열의 합

* 문제풀이

https://hroad.tistory.com/31

기본 개념

• 버킷 정렬은 계수 정렬을 일반화 한 것으로 간주할 수 있다.

• 계수 정렬은 키 값이 작은 범위 안에 들어올 때 적용할 수 있는 방법이지만 버킷 정렬은 키 값의 범위뿐만이 아니라 그 범위 내에서 키값이 확률적으로 균등하게 분포된다고 가정할 수 있을 때 적용할 수 있는 방법이다.

1. 키 값의 범위가 0과 1사이라고 가정할 때 n개의 키가 있을 때  구간 [0,1]을 n등분하고 이들 각각을 하나의 버킷으로 한다.

2. 각 키를 크기에 따라 각 버킷에 분배하면, 키가 구간내에서 균등하게 분포한다고 가정했으므로, 하나의 버킷에는 하나의 키만 들어있을 확률이 높다.

3. 한 버킷에 여러 키가 들어가게 된다면 같은 버킷에 속하는 키끼리는 간단한 정렬(삽입 정렬, 퀵 정렬 등)로 정렬한다.

4. 이러한 버킷을 순서에 따라 출력하면 정렬된 결과를 얻을 수 있다.

버킷 정렬의 평균 실행시간은 O(n) 이다.

하지만 한 Bucket에 입력 키값들이 몰린 경우에는 버킷에 속하는 키들을 정렬하는 데 사용한 정렬의 시간복잡도 보다 오랜 실행시간이 소요된다.

그렇기 때문에 최악의 경우는 한 bucket에 키값들이 몰린 경우이며

최상의 경우는 각 bucket에 입력 키값들이 균등하게 분배된 경우이다.

과정

1. A배열에 10개의 데이터가 존재하므로 구간 크기가 0.1인 10개의 버킷 B를 만든다.

2. 각 리스트 B[i] 에 대하여 퀵 정렬을 진행한다.

3. 버킷에 저장되어있는 각 원소를 순서대로 출력하여 정렬을 완료한다.

코드

#define MAX 10 //배열의 개수 = 버킷을 등분할 개수
float A[MAX] = { 0.86,0.32,0.27,0.12,0.49,0.21,0.62,0.89,0.71,0.87 };
vector<float> B[MAX]; //버킷 

bool desc(float a, float b){
	return a > b;
}

void BucketSort()
{
	for (int i = 0; i < MAX; i++)
		B[(int)(A[i] * MAX)].push_back(A[i]); //A[i]를 B[n*A[i]]에 삽입
	for (int i = 0; i < MAX; i++)
		sort(B[i].begin(), B[i].end(),desc); 
        //STL Sort()를 이용하여 각 버킷 별로 정렬을 진행한다.
	
    //N개로 나누어진 버킷에 있는 값들을 하나의 배열에 출력
	int Idx = 0;
	for (int j = 0; j < MAX; j++) {
		while (B[j].empty() == 0) {
			A[Idx] = B[j].back();
			B[j].pop_back();
			Idx++;
		}
	}
}

결과

기본 개념

전체 키를 여러 자리로 나누어 각 자리마다 계수 정렬과 같은 안정적 정렬 알고리즘을 적용하여 정렬하는 방식이 기수 정렬이다. 

그렇기 때문에 기수 정렬을 적용하기 위해서는 다음과 같은 조건이 필요하다.

 - 입력 키들이 부동소숫점이 없는 정수여야 한다.

d 자리수 숫자들에 대하여 계수 정렬로 정렬한다면 각 자리에 대하여 O(n)이 걸리므로 전체로는 O(dn) 시간이 걸리고

d 를 상수로 처리한다면 기수 정렬은 O(n) 시간이 걸리는 알고리즘이다.

기수 정렬에는 LSD 와 MSD가 있다

1. LSD (Least Significant Digit) 방식 정렬

  - 가장 작은 자릿수 부터 정렬을 진행

  - 특징 : 가장 작은 자릿수부터 큰 자릿수까지 모두 비교해야 한다는 단점이 존재, 코드 구현이 MSD에 비해 간결하다.

2. MSD (Most Significant Digit) 방식의 정렬

 - 가장 큰 자릿수 부터 정렬을 진행

 - 특징 : 코드 구현은 LSD에 비해 복잡하지만(정렬 상태 확인 등) , 정렬 도중 중간에 정렬이 완료될 수 있다는 장점이 존재한다.

특징

모든 정렬 대상의 길이가 동일할 때 가장 효율적

입력 키들의 길이가 다를 경우 빈 공간을 메꾸는 추가 작업이 발생하여 성능이 저하된다.

 - 좋은 예 {567, 654, 124, 457, 830, 911, 555}  {dark, blue, high, best}   

 - 나쁜 예 {2154, 15, 54775, 1}  {white, shy, h, strawberry}

계수 정렬을 이용한 정렬과정에서 전체 정렬 데이터 개수만큼의 메모리와 진법 크기 만큼의 메모리가 추가로 필요한 비제자리 정렬이므로 메모리의 여유가 많지 않는 경우에는 적용하기 어려운 정렬 방법이다.

과정

코드

int maxValue; // 최대 자릿수를 계산하기 위해 최댓값 저장
queue<int> Q[10]; //0-9에 대한 버킷


void Radix_Sort()
{
	int radix = 1;
	while (1){ // 최댓값을 활용하여 최대자릿수를 구함
		if (radix >= maxValue) break;
		radix = radix * 10;
	}
    
    //1의 자리부터 최대자릿수까지 과정 반복
	for (int i = 1; i < radix; i = i * 10){
		for (int j = 0; j < sizeof(arr) / sizeof(arr[0]); j++){ //배열 전체 탐색
			int K;
			if (arr[j] < i) K = 0; //현재 탐색중인 자릿수보다 작으면 K는 0
			else K = (arr[j] / i) % 10; // 다른 경우에는 현재 자릿수에 해당하는 숫자 K를 구함
			Q[K].push(arr[j]); //해당하는 Queue에 push
		}
		int Idx = 0;
        //0부터 9 까지의 Queue에 저장된 값들을 순차적으로 배열에 저장
		for (int j = 0; j < 10; j++){
			while (Q[j].empty() == 0){
				arr[Idx] = Q[j].front();
				Q[j].pop();
				Idx++;
			}
		}
	}
    
}

결과

기본 개념

• 분포에 의한 정렬에는 계수 정렬, 기수 정렬, 버킷 정렬 등이 있으며 최악 또는 평균 실행시간이 O(n) 인 알고리즘이다.
• 계수 정렬은 입력 키가 어떤 범위(1~k) 사이의 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법이다.
• 어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있다.
• 계수 정렬에서는 입력 키들이 범위 k 내의 각 값에 대하여 입력 키가 실제로 입력에 나타나는 횟수를 계산한다.

과정

코드

void CountSort(int a[], int n, int b[], int k)
{
	int i, j;
	int* N = new int[k];

	//N 배열 초기화 (N[] = 범위내의 각 숫자가 나타나는 횟수를 위한 배열)
	for (i = 0; i < k; i++) N[i] = 0;  //O(k)

	//각 키의 개수 저장
	for (j = 0; j < n; j++)  N[a[j]-1] += 1;  //O(n)
	//각 키의 누적 합 저장
	for (i = 1; i < k; i++) N[i] += N[i - 1];  //O(k)
	//정렬 결과를 배열 B에 저장
	//뒤에서부터 정렬하여 안정성을 보장
	for (j = n-1; j >= 0; j--) { 
		b[N[a[j]-1]-1] = a[j];
		N[a[j]-1] -= 1;
	} // O(n)
	//-> O(k)+O(n)=O(max(k,n)
}

실행 시간

O(n+k)

기본 개념

- 히프 정렬은 히프 자료구조의 장점인 최대값을 삭제하거나 임의의 값을 삽입하는 연산을 수월하게 하는 점을 이용한 정렬이다.

히프

• 히프는 완전 이진 나무로 나무의 각 노드의 값은 그 노드가 자식 노드를 갖는 경우에 자식의 값보다 크거나 같아야 한다.
• 각 노드의 값이 자식 노드의 값보다 작거나 같도록 히프를 구성할 수 도 있는데 이를 최소값 히프라 한다.
• 각 노드의 값이 자식 노드의 값보다 크거나 같은 히프는 최대값 히프라고 한다.

히프 정렬은 두 단계로 구성된다.

• 첫째 단계에서 정렬하려는 1차원 배열을 히프로 변환한다.
• 두 번째 단계에서는 가장 큰 값, 두 번째로 큰 값 등을 차례로 히프에서 제거하면서 키를 정렬한다.

첫째 단계. 히프로의 변환 과정

• n개의 키로 구성된 1차원 배열을 히프로 변환하는 방법에는 두 가지 방법이 있다.

첫 번째 방법

• 삽입 정렬과 비슷한 방법을 사용하여 a[0:i-1] 이 이미 히프 구조를 하고 있는 상태에서 a[i]를 정당한 위치에 삽입하여 a[0:i] 역시 히프 구조를 갖도록 한다. 
• 즉. a[i] 의 제자리를 찾기 위해 a[i]는 자신의 부모노드와 그 크기가 비교되고, 부모노드보다 크면 부모노드와 자리바꿈을 한 후, 다시 그위의 노드와 비교를 하게 된다. 
• 이렇게 트리를 거슬러 올라가면서 자신의 조상 노드들과 자리바꿈을 계속해 가면서 제자리를 찾는다.

두 번째 방법

• 배열 전체를 하나의 완전 이진 트리로 간주하고 잎(leaf) 노드로부터 뿌리(root) 노드에 이르기까지 한 레벨씩 트리를 거슬러 올라가면서 트리의 아래 부분이 히프 구조를 가지도록 하는 것이다.
• n개의 노드를 갖는 완전 이진 나무는 [n/2] 개의 잎 노드를 가지며 이 잎 노드를 뿌리로 하는 [n/2] 개의 노드 한 개짜리 나무들은 이미 각각 작은 히프로 볼 수 있다.
• 이는 1차원 배열 전체를 하나의 트리로 보고 그 트리의 리프가 아니면서 가장 높은 레벨에 있는 노드, 즉 잎을 자식 노드로 갖는 노드부터 시작하여 그 트리의 뿌리에 이르기까지 각 노드를 이미 이루어진 작은 히프들의 뿌리에 삽입하는 것과 같다.

두 번째 단계. 최대값을 제거하며 정렬하고 남은 원소로 반복하여 히프를 구성하는 과정

-히프에서 최대값을 제거하고 남아 있는 원소들 만으로 다시 히프를 구성하는 과정을 n-1회 반복하여 히프 정렬을 진행한다.

코드

void HeapSort(int ary[], int n){
	int i;
	//1차원 배열을 히프로 변환
	// n/2 -> n/2-1 ->...-> 1
	//배열 전체를 완전 이진 나무로 간주하고 리프(잎) 노드부터 뿌리노드까지 한 레벨씩 거슬러 올라가면서
	//트리 하단 부분부터 히프 구조를 가지도록 함
	//n개의 노드를 갖는 완전 이진 노드는 n/2개의 잎 노드를 가짐
	printf("--------1차원 배열을 히프로 변환--------\n");
	for (i = n / 2; i > 0; i--) {
		MakeHeap(ary, i - 1, n - 1);
		pirntHeap(ary, 10);
	}
	printf("-----------남은 원소 히프 구성-----------\n");
	//히프에서 최대값을 제거하고
	//남은 원소들로 다시 히프 구성 (n-1)회 반복
	for (i = n-1 ; i > 0; i--) {
		swap(ary[0], ary[i]);
		MakeHeap(ary, 0, i - 1);
		pirntHeap(ary, 10);
	}
}

void MakeHeap(int a[], int root, int lastNode) {
	int parent, leftSon, rightSon, son, rootValue;
	parent = root; 
	rootValue = a[root];
	leftSon = 2 * parent + 1; 
	rightSon = leftSon + 1;
	while (leftSon <= lastNode) {
		if (rightSon <= lastNode && a[leftSon] < a[rightSon])
			son = rightSon;
		else
			son = leftSon;
		if (rootValue < a[son]) {
			a[parent] = a[son];
			parent = son;
			leftSon = parent * 2 + 1;
			rightSon = leftSon + 1;
		}
		else break;
	}
	a[parent] = rootValue;
}

실행 시간

초기 히프 구축 시간 = O(n)

Makeheap에 걸리는 시간 = 뿌리의 높이 = O(lgn)

전체 히프 정렬 시간 복잡도 = O(nlgn)

특징

제자리 정렬

불안정한 정렬