컴퓨터알고리즘 정리

-·2020년 10월 12일

컴퓨터알고리즘

목록 보기

1/1

컴퓨터알고리즘 정리

1장. 서론

알고리즘 이란?

문제를 해결하거나 함수를 계산하기 위해 좇아야할 모호함이 없는 간단한 명령들로 구성된 일련의 순서적 단계.
#알고리즘의 조건
1. 외부에서 0개 이상의 입력을 받아들여, 하나 이상의 출력을 생성한다.
2. 각 단계가 단순해야 하며 모호하지 않아야 한다.
3. 한정된 수의 작업 후에는 반드시 끝나야 한다.
4. 모즌 명령이 수행 가능해야 한다.
5. 효율적이여야 한다.
#알고리즘의 생성
1. 설계
2. 표현
3. 정확성 섬증
4. 효율분석

큐 (Queue)

한 쪽 끝에서 삽입이 행해지고, 다른 쪽 끝에서 삭제가 행해지는 리스트.

삽입이 일어나는 쪽을 rear, 삭제가 일어나는 쪽을 front라고 하며, 선입선출(FIFO) 구조를 가진다.

스택 (Stack)

리스트의 한 쪽 끝에서만 삽입과 삭제가 수행되는 리스트.

후입선출(LIFO) 구조를 가진다.

그래프 (Graph)

정점(Vertex), 간선(Edge)의 집합으로 구성되며 $G=(V,E)$ 로 표시된다.

방향그래프는 하나의 간선이 방향을 가지며 정점 u에서 정점 v로 가는 간선은 $<u,v>$ 로 표시한다.

무방향 그래프는 방향이 존재하지 않으며 정점 u에서 정점 v로 가는 간선은 $(u,v)$ 로 표시한다.

자기 자신을 잇는 간선을 루프라고 한다.

차수는 정점에 부수된(포함된) 간선의 개수. 방향그래프는 외향차수, 내향차수를 가진다.

경로는 정점 $v_1$ 에서 $v_n$ 까지 연결된 정점들의 순차열이다.

길이는 경로상에 존재하는 간선의 개수이다.

단순 경로는 경로상의 정점들이 모두 다른 것을 의미한다.

사이클은 시작 정점과 끝 정점이 같은 경로를 사이클이라 한다.

단순 사이클은 시작 정점과 끝 정점을 제외한 모든 정점이 다른 것을 의미한다.

신장 부분 그래프 (Spanning Subgraph)

정점의 개수가 같은 부분 그래프.

완정 그래프 (Complete Graph)

모든 정점끼리 간선으로 연결된 그래프.

트리 (Tree)

연결된 무사이클 무방향 그래프.

조상과 자손이 있으며, 부모가 같은 노드들을 동기라고 한다. 또한, 자식이 없으면 잎 노드하고 한다.

노드 $x$ 의 자식의 개수를 $x$ 의 차수라고 한다.

뿌리 $r$ 에서 노드 $x$ 까지의 경로의 길이를 깊이라고 하며, 가장 큰 길이를 높이라고 한다.

깊이가 같은 노드들을 동일한 수준에 있다고 한다. (수준은 0부터 시작)

순서 트리

각 자식에 순서가 부여된 트리.

오른쪽, 왼쪽 자식을 구별하지 않는다.

이진나무

각 노드의 자식이 2개 이하인 순서 트리.

전 이진 트리

모든 노드의 차수가 0이거나 2인 이진 트리.

포화 이진 트리

모든 잎의 깊이가 같은 이진 트리.

노드의 개수: $2^{h+1}-1$

잎 노드: $2^h$

잎이 아닌 노드: $2^h-1$

완전 이진 트리

포화 이진 트리의 잎 노드들을 오른쪽으로 부터 제거하여 얻어지는 트리.

노드의 범위: $2^h\le n\le2^{h+1}-1$

트리의 높이: $ \lfloor\ lgn \rfloor\ $

욕심쟁이 방법 (Greedy method)

어떤 문제에 대한 해를 구할려면 일련의 선택 과정을 거쳐야한다.

각 선택과정마다 그 단계에서 최선이라고 볼 수 있는 선택을 행해나가면 결과적으로 전체적인 최적 해를 구할 수 있을 것이라는 희망적 전략을 취하는 방법.

참고. p.28의 배낭 문제.

시간 복잡도

수행시간: 알고리즘이 수행하는 기본 연산의 수행 횟수를 세는 방법. ( $\text{각 명령문 수행 횟수} \times \text{각 명령문 수행 시간}$ )

점근 성능의 표기법

$f(n)$ : 실행 시간

$g(n)$ : $f(n)$ 의 최고 차수 일 때,

점근적 상향: $n\ge n_0$ 인 모든 $n$ 에 대하여 $f(n) \le c \cdot g(n)$ 을 만족하는 양의 상수 $c, n_0$ 이 존재하면 $f(n) = O(g(n))$ 이다.

점근적 하향: $n\ge n_0$ 인 모든 $n$ 에 대하여 $f(n) \ge c \cdot g(n)$ 을 만족하는 양의 상수 $c, n_0$ 이 존재하면 $f(n) = \Omega (g(n))$ 이다.

점근적 평균: $n\ge n_0$ 인 모든 $n$ 에 대하여 $c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$ 을 만족하는 양의 상수 $c_1, c_2 ,n_0$ 이 존재하면 $f(n) = \Theta(g(n))$ 이다.

점근 성능 표기의 성질

$f_1(n) = O(g_1(n)), f_2(n) = O(g_2(n))$ 이라 하자.

(1) $f_1(n) + f_2(n) = max(O(g_1(n)), O(g_2(n)))$ 이다.

(2) $f_1(n) \cdot f_2(n) = O(g_1(n))\cdot O(g_2(n))$ 이다. # for문에서 사용

순환과 점화 관계

$T(n)=T({n \over 2}) + O(1)$ 와 같이 안 값이 자신을 포함한 수식으로 표현되는 것을 점화 관계라고 한다.
$T(n) = C_2 + T\left({n \over 2}\right)\\ = C_2 + C_2 + T\left({n \over 4}\right)\\ = C_2 + C_2 + C_2 + T\left({n \over 8}\right)\\ = (k-1)c_2 + T\left({n \over 2^{k-1}}\right)\\ = kC_2 + T(1)\\ = C_1 + kC_2\\ = C_1 + log_2n\\$

점화식에 대한 폐쇄형
$T(n) = \begin{cases} \Theta(1),\ n = 1\\ T(n-1) + \Theta(1), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(n)$ $T(n) = \begin{cases} \Theta(1),\ n = 1\\ T(n-1) + \Theta(n), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(n^2)$ $T(n) = \begin{cases} \Theta(1),\ n = 1\\ T({n \over 2}) + \Theta(1), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(log\ n)$

T(n) = \begin{cases} \Theta(1),\ n = 1\\ T({n \over 2}) + \Theta(n), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(n)

T(n) = \begin{cases} \Theta(1),\ n = 1\\ 2T({n \over 2}) + \Theta(1), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(n)

T(n) = \begin{cases} \Theta(1),\ n = 1\\ 2T({n \over 2}) + \Theta(n), \ n \ge 2 \end{cases}\\ \text{폐쇄형:}T(n) = \Theta(nlog\ n)

2장. 정렬

정렬

자료가 저장되는 위치: 내부 정렬과 외부 정렬로 나누어진다.

정렬 방식: 비교 기반 정렬 알고리즘과 그렇지 않은 알고리즘으로 나누어진다.

안정적 알고리즘

동일한 키를 갖는 각 레코드쌍 A, B에 대하여, 정렬 전에 A가 B의 앞에 있었고 정렬 후에도 이 순서 그대로 유지되는 것이 보장된다.

선택 정렬

$n$ 개의 키 중에서 가장 작은 것을 찾아서 그 키와 첫째 키인 $A[0]$ 와 자리바꿈을 한다.

다음에는 남아있는 키들 중에서 가장 작은 키를 찾아서 그 원소와 $A[1]$ 의 자리를 바꾼다.
```
void SelectionSort (int A[], int n) {
	int i, j, MinINdex;
	for(i = 0; i < n-1; i++) {
		MinIndex = i;
		for(j = MinIndex+1; j < n; j++) {
			if(A[MinIndex] > A[j])
				MinIndex = j;
		}
		if(MinIndex != i)
			Swap(&A[i], &A[MinIndex]);
	}
}
```
레코드 수가 작을 경우에 효율적.

시간 복잡도는 $O(n^2)$ 으로 불안정한 알고리즘이다.

버블 정렬

먼저 $n$ 개의 키가 왼쪽으로부터 오른쪽으로 검색되면서 모든 인접한 두 개의 키가 서로 비교된다.

인접한 두 개의 키 중에서 왼쪽의 키가 더 크면 오른쪽의 키와 자리를 바꾼다.

$n - 1$ 회 거치면 배열 전체가 오름차순으로 정렬된다.
```
void BubbleSort(int A[], int n) {
	int i, Sorted; # 자리바꿈이 일어났는지 확인하기 위한 변수
	Sorted = FALSE; 
	while (!Sorted) {
		Sorted = TRUE;
		for(i = 1;i < n; i++) {
			if (A[i-1] > A[i]) {
				Swap(&A[i-1], &A[i]);
				Sorted = FALSE;
			}
		}
	}
}
```
시간 복잡도는 $O(n^2)$ 으로 안정한 알고리즘이다.

삽입 정렬

삽입 정렬의 $i$ 번째 단계가 시작될 때에 배열의 맨 처음 $i-1$ 개의 키인 $A[0:i-2]$ 는 이미 정렬되어 있다. 여기에 $A[i-1]$ 을 삽입하여 $A[0:i-1]$ 이 정렬되도록 하는 것이 $i$ 번째 단계의 목표이다.

$A[i-1]$ 자리에 있던 키가 제자리를 찾을 때까지 키를 오른쪽으로 한 자리씩 옮기고, 원래 $A[i-1]$ 을 빈 자리에 삽입한다.
```
void InsertionSort(int A[], int n) {
	int i, j, Value;
	for(i =2; i <= n; i++) {
		Value = A[i];
		j = i;
		while(A[j-1] > Value) {
			A[j] = A[j-1];
			j--;
		}
		A[j] = Value;
	}
}
```
A[0]는 알고리즘을 간결하게 하기 위한 더미(dummy) 키를 넣는다.

시간 복잡도는 $O(n^2)$ 으로 안정한 알고리즘이다.

쉘 정렬

배열을 부분배열로 나누어 그 각각에 삽입 정렬을 실행한다.
각 부분배열은 거리가 일정하게 떨어져 있는 원소들로 구성한다.

한 번의 비교 후에 키가 일정한 자리만큼 이동하게 되므로 키는 일반적으로 좀 더 빨리 제자리에 접근한다.

각 부분배열의 정렬이 끝나면 전체배열에 다시 삽입 정렬을 적용한다.
```
void ShellSort(int A[], int n) {
	int h, i, j, Value;
	h = 1;
	do h = 3 * h + 1; while (h < n);
	do {
		h = h / 3;
		for(i = h; i < n; i++) {
			Value = A[i];
			j = i;
			while(A[j-h] > Value) {
				A[j] = A[j-h];
				j -= h;
				if (j <= h-1)
					break;
			}
		}
		A[j] = Value;
	} while (h > 1)
}
```
시간 복잡도는 $O(n^{3 \over 2})$ 으로 불안정한 제자리 알고리즘이다.

순열 h는 $h_{i+1} = 3h_{i}+1$ 이다.

퀵 정렬
정렬한 기들을 배열 내에서 적당히 이동시키면서 다음의 두 조건이 만족되도록 배열을 오른쪽 부분배열과 왼쪽 부분배열로 나눈다.
1. 왼쪽 부분배열에 있는 모든 키들은 오른쪽 부분배열의 가장 작은 키보다 작다.
2. 오른쪽 부분배열에 있는 모든 키들은 왼쪽 부분배열의 가장 큰 값보다 크다.
정렬할 배열은 분할원소(pivot)을 기준으로 두 개의 부분배열로 나눈다. (보통 배열의 첫째 키를 pivot으로 사용한다.)

pivot을 기준으로 오른쪽은 pivot보다 큰 원소를 찾으며, 왼쪽은 pivot보다 작은 원소를 찾는다.

이 두키의 자리를 서로 바꾸고 검색을 계속한다.

엇갈리는 지점이 나타나면 검색을 중단하고 pivot을 넣는다.
```
void Partition (int A[], int Left, int Right ) { 
	int PartElem, Value;
	PartElem = Left;
	Value = A[PartElem];
	do {
    	do {  } while (A[ ++Left] < Value);
     	do {  } while (A[ --Right] > Value);
     	if (Left < Right) Swap (&A[Left], &A[Right]);
     	else break;
    } while (1);
	A[PartElem] = A[Right];
 	A[Right] = Value;
 	return Right;
}
```
```
void QuickSort (int A[], int Left, int Right ) { 
	int Middle;
 	if (Right > Left) {
 		Middle = Partition (A, Left, Right + 1);
 		QuickSort (A, Left, Middle – 1);
 		QuickSort (A, Middle + 1, Right);
 	}
 }
```
시간 복잡도는 $O(n\ logn))$ 으로 불안정한 정렬 알고리즘이다.

순열 h는 $h_{i+1} = 3h_{i}+1$ 이다.

-의 Velog

3개의 댓글

문호

2020년 10월 12일

좋은 글 잘 보고 갑니다 ..^^*
넘나 행복한 하루 보내시길 ..~

1개의 답글

GiveMetheCarrot

2020년 10월 12일

대박이에요 ^^^^^^ 평소 정리하시는 걸 잘하시나봐요 ㅎㅎㅎ 소름돋습니다 :) 좋은 정보 감사해용ㅎㅎㅎ

답글 달기