Loading

백호랑의 보금자리

검색
2013.08.14 01:09 – 빽호랑

전산학개론04. 알고리즘(Algorithm) 개념 및 용어정리










Algorithm

전산학개론04. 알고리즘(Algorithm) 개념 및 용어정리






이어서 아래에 정리 및 설명된 내용은 관련 전공(컴퓨터공학, 전산학 등) 공부를 하면서 

필수적으로 기억해야 할 내용들을 정리하면서 생각나는데로 순서없이 쓴 글입니다.

최대한 간단하고 필요한 내용만 간추려서 쓰다보니 부족하거나 실수한 내용이 있을 수 있습니다.

혹시 잘못된 내용이 있으면 댓글로 피드백 주시면 감사하겠습니다. 내용은 생각나는대로 계속 추가됩니다.







1. 수의 범위 크기 비교 - 자연수, 실수의 크기와 밀도 비교

(1) 자연수 = 정수 = 짝수 = 홀수 = 유리수

: 자연수와 1:1로 대응시킬 수 있다.(농도(밀도)가 같다)

(2) 자연수 < 실수 

- "칸토어의 대각선 논법"으로 증명이 가능하다.

- [0,1] 범위에 다음과 같이 자연수로 대응할 수 있는 유한개의 실수가 있다고 가정한다.

- 이렇게 1:1로 대응하는 실수들에서 각 에 해당하는 원소들을 뽑아서 1일경우 0으로, 1이 아닐 경우 1로 바꾸는 규칙에 의해 다음과 같은 bn을 만들면

(어떠한 규칙에 의해서 변형된 a의 소수점 아래 자리수를 '로 표현한다)

- 위에서 정의한 bn은 현재 a1부터 an까지 있는 모든 실수와 다른 새로운 실수가 등장하게 된다.

- [0,1]에서 자연수에 대응되는 유한개의 실수가 있다고 가정했으나, 위와 같은 과정을 반복하면 계속해서 새로운 실수를 찾을 수 있다.

- 고로 [0,1]에서 실수는 무한히 계속 증가하는 형태를 확인할 수 있으며, 이는 실수의 농도가 자연수의 농도보다 진함을 이야기한다.




2. Lower bound 

- 정의 : 알고리즘의 성능 검사시 시간복잡도가 가장 낮을 때가 있고(성능이 가장 좋을 때), 이 때를 lower-bound라고 한다.

- Big Oh(O) : 수행시간의 Upper bound 

- '최악의 경우(시간복잡도가 가장 클 경우)에도 이 시간 정도면 된다'라는 의미 내포

- 정의 : 임의의 상수 N0와 C가 있어서, N>=N0인 N에 대해, C*f(N)>=g(N)이 성립하면, g(N) = O(f(N))이다.

- Big Omega(Ω) : 수행 시간의 Lower bound

- '최소한 이만한 시간은 걸린다'라는 의미를 내포




3. Optimal

- Optimal(최적이다) : the average time it takes to locate a key is minimized




4. Graph, Tree

(1) Graph

- 정의 : 그래프 G는 공집합이 아닌 정점(vertex)들의 집합 V와 정점들을 잇는 간선(Edge)들의 집합

- 정보(정보의 단위)들을 vertex로 표현하고, 그 정보(객체)들 사이의 관계를 edge로 연결한 자료구조

- 표현 : G=(V,E) , 이 때 V와 E는 각각 정점과 간선을 포함하고 있는 집합

- 그래프의 종류

i) Directed Graph : 그래프의 Edge가 방향성을 가지는 그래프

ii) Undirected Graph : 그래프의 Edge가 방향성을 가지지 않는 그래프

iii) Complete Graph : 모든 Vertex(n개)간 연결하는 Edge가 존재하고, 각 정점이 n-1개의 Edge를 가지고 있는 그래프

- 그래프의 표현 방식

i) 인접 행렬 : 2차원 배열 등을 이용

ii) 인접 리스트 : 링크드 리스트(Linked-list)를 이용

- 그래프의 운행법

i) DFS(Depth-first Search) : stack을 이용한다.

ii) BFS(Breadth-first Search) : Queue를 이용한다.

- Degree : 한 vertex에 연결 된 edge의 수

(2) Tree 

- 정의 : Connected Acyclic Graph (모든 정점 간 path가 존재하고, 사이클이 없는 그래프)



5. P, NP, NP-Complete, NP-Hard

(1) NP

: Decision problem[각주:1]의 yes 여부를 polynomial time(빠른 시간) 내에 확인할 수 있는 문제(이미 답이 있는 경우)

- Decision problem을 NTM(Non-deterministic[각주:2] Turing Machine[각주:3])으로 polynomial time내에 풀 수 있는 문제

(2) P

: NP 문제중에서도 답을 polynomial time 내에 찾을 수 있는 문제

- Decision problem을 DTM(Deterministic[각주:4] Turing Machine)으로 polynomial time내에 풀 수 있는 문제

(3) NP-Hard

: Trial & Error 방법 말고는 해결 방법이 없는 문제 (매우 풀기 어려운 문제)

- Decision problem or Functional problem[각주:5]

- NP에서 가장 어려운 문제 만큼 어려운 문제

(4) NP-Complete

: NP이면서 NP-Hard에 속하는 문제

- 모든 NP문제들이 빠른 시간 안에 변환(Reduction) 될 수 있는 문제

* 도움이 될 만한 링크 : http://azza.tistory.com/126 (이분이 설명을 무척 잘해놓으셨으니, 참고하세요)




6. Decision problem, Functional problem

(1) Decision problem : 답이 '예/아니오' 둘 중 하나로 결정되는 문제

(2) Functional problem : 답이 셋 이상의 경우의 수가 있는 문제



7. Deterministic algorithm, Non-deterministic algorithm

(1) Deterministic algorithm(결정성 알고리즘) : 각 단계에서 그 다음단계가 유일하게 결정되는 알고리즘

(2) Non-deterministic algorithm(비결정성 알고리즘) : 그 다음 단계가 유일하게 결정되지 않는 알고리즘

- ex) 자연수 n이 합성수인지 소수인지 검출하는 알고리즘



8. Partially ordered set

- 정의 : 어떤 집합 S가 있을 때, relation R에서 임의의 원소 a, b, c에 대해 R에 각각 reflexive, transitive, antisymmetric할 경우 S는 partially ordered set이라 한다.

- 아래와 같은 관계 '크거나 같다' 부호는 partially ordered set을 이룬다.

* Totally ordered set : reflexive, transitive, symmetric



9. Dynamic Programming / Divide and Conquer

(1) Dynamic programming : 부문제의 해를 모아서 전체 문제의 해를 구하는 방법 (최적화 문제에 이용된다)

- 같은 문제를 또 풀지 않기 위해 sub problem을 한 번만 풀고 그 결과를 테이블에 저장

- 알고리즘의 각 실행 흐름이 독립적이지 않거나 재귀적인 경우 사용

   (독립적이지 않은 사건이 연속적으로 일어날 때, divide and conquer를 사용하게 되면 똑같은 문제를 반복해서 풀어야 하는 경우 발생)

(2) Divide and Conquer : 한 번에 해결하기 어려운 문제를 작은 단위의 부문제(subproblem)들로 쪼개어 해결하는 방법

- 과정

i) 문제를 작은 Sub problem들로 분할 - divide

ii) 각 Sub problem에서 구한 답을 분할하기 전의 원래 문제가 되도록 합병하는 과정 - merge

iii) 더 이상 쪼갤 필요가 없거나 쪼갤 수 없는 문제에 대해 답을 구하는 과정 - base case

(3) Dynamic programming vs. Divide and Conquer

- 둘 모두 주어진 문제를 작은 부문제들로 쪼개어 부문제의 해를 구해 조합하여 주어진 문제의 해답을 도출하는 방법

- 그 부분 문제들의 부분 문제들이 겹치지 않는다면(독립적이라면) Divide and Conquer방식을, 겹친다면(독립적이지 않다면) Dynamic programming을 사용한다.




10. Backtracking

- 어떤 조건이나 제약에 합당한 객체를 연속적으로 선택하는 과정을 통해 해를 구할 때 사용하는 방법

=> 해를 얻을 떄 까지 모든 가능성을 시도하는 방식

- 깊이 우선 탐색 : 모든 트리의 노드를 순회하여 solution을 취함

- 재귀적으로 구현 : N-Queens 문제, 외판원 문제(n!)




11. Boolean Satisfiability Problem (충족 가능성 문제)

* satisfiability : 전체 논리값을 참으로 만드는 대입이 존재할 때, 이 문제를 satisfiable이라고 말한다.

* SAT(충족 가능성 문제)

- 입력이 충족 가능하면 true (satisfiable)

- 입력이 충족 불가능하면 false (unsatisfiable)




12. Tree Traversal Method (DFS)

(1) Preorder traversal (전위순회) : root노드->왼쪽노드->오른쪽노드

(2) Inorder traversal (중위순회) : 왼쪽노드->root노드->오른쪽노드

(3) Postorder traversal (후위순회) : 왼쪽노드->오른쪽노드->root노드




13. Binary Tree

- 정의 : 한 노드가 자식(Child) 노드를 최대 2개까지 가질 수 있는 트리(Connected, Acyclic graph)

- Binary Tree(이진트리)의 종류

(1) Full binary tree : leaf를 제외한 모든 노드의 자식 노드는 2개

(2) Perfect binary tree : Full binary tree 중 leaf node의 레벨이 모두 같은 경우

(3) Complete binary tree : Leaf node들이 왼쪽부터 차곡차곡 채워진 이진트리

(4) Skewed(Degenerate) binary tree(사향 이진 트리) : 한쪽으로만 자라나는 이진트리




14. Ascending order / Descending order

(1) Ascending order : 오름차순

(2) Descending order : 내림차순




15. Sorting Algorithms


(1) Bubble sort(버블정렬)

- 인접한 두 원소를 검사하여 정렬

- 시간복잡도 : O(n^2)


(2) Selection sort(선택정렬)

- 주어진 리스트에서 최소값(최대값)을 하나씩 뽑아내서 맨 앞이나 맨 뒤에 배치하여 정렬하는 방법

- 시간복잡도 : O(n^2)


(3) Insertion sort(삽입정렬)

- 원소를 순서대로 하나씩 뽑아서 새로운 배열의 적절한 위치로 삽입/밀어내기 하여 정렬하는 방법

- 시간복잡도 : O(n^2) - n개의 원소 * n번 위치 변경


(4) Shell sort

- 삽입 정렬(Insertion sort)을 하기 전에 Array를 정렬해 놓기 위해 하는 정렬

- 어떤 간격에 있는 원소들(5칸 간격, 3칸 간격, 1칸 간격) 간 삽입정렬(간격수열은 서로소)

- 1칸 간격으로 Shell sort를 하는 작업 = 전체 배열에 대한 Insertion sort


(5) Merge sort

- 정렬되지 않은 리스트를 원소가 1개인 하위 리스트들로 나누고 분할된 하위 리스트들을 벼합하여 새로운 하위리스트를 생성하는 방법

- 시간복잡도 : O(nlogn)

- 안정성이 있지만, 메모리를 배열 크기만큼 확보해야 한다.

- Divide and Conquer 방식


(6) Heap sort(힙정렬)

* Heap : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 크거나 작은 노드를 찾기 위해 만든 자료구조

- Max Heap : 부모노드 키값 >= 자식노드 키값

- Min Heap : 부모노드 키값 <= 자식노드 키값

- 계속해서 Max Heap을 생성해 가면서 최대값을 빼내어 정렬

- 시간복잡도 : O(nlogn)

- n개의 노드로 max heap을 구성하는 평균 시간 : O(logn)

- n개의 노드에 대해 힙 재구성 반복 : O(n)


(7) Quick sort(퀵소트)

- 정렬할 전체 원소에 대해 정렬을 수행하지 않고 기준값을 중심으로 왼쪽 부분과 오른쪽 부분으로 나누어 정렬

- 기준값 : 피봇(Pivot) - 일반적으로 가운데 원소로 선정한다.

- 기준값을 기준으로 왼편은 작은 원소, 오른쪽은 큰 원소

- Divde & Conquer를 반복

- Divide : pivot을 중심으로 두 부분으로 분할

- Conquer : pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로

- 위치 교환 방법

- L은 pivot보다 크거나 같은 원소를 찾음, R은 pivot보다 작거나 같은 원소를 찾음

- L과 R이 만나는 지점에서 pivot원소와 맞교환

- L과 R이 찾은 원소끼리 교환

- 시간 복잡도

- 최악의 경우(잘못된 피봇 설정) : n^2

- 평균 시간 복잡도 : O(nlogn)


(8) Topological sort(위상정렬)

- 사이클이 있어서는 안되는 Tree구조의 정렬에 유용하다.

= 상대적으로 작업에 단계가 반드시 지켜져야 하는 경우(상대적 순서가 있을 시) 수행하는 정렬에 유용하다.

- 위상정렬의 방법

i) indegree가 0인 노드(화살표가 들어오는게 없는 노드)를 선택한다

ii) 모든 나가는 화살표(outdegree)를 지워준다





16. Union-find (집합의 원소를 찾는 과정)

- Union : 서로 다른 두 개의 집합을 하나의 집합으로 합병

- Find : 어떤 원소가 어떤 집합에 포함되는지 아닌지를 판별

- Union-find를 위한 자료구조 : 상향식 트리구조로 구현 - 정점의 배열에 부모원소를 표기한다.

i) find : 두 원소의 대표원소를 비교(부모 원소를 따라가다 보면 대표원소가 출력된다. 두 대표원소를 비교하면 된다.)

ii) union : 한 집합을 다른 하나 집합의 대표원소의 자식으로 둔다. (root의 자식)




17. Huffman code (허프만 코드)

- 가변길이의 코드로 문자의 발생 빈도를 검사해서, 발생 빈도가 높은 문자는 적은 bit, 낮은 문자는 높은 bit를 부여하는 방식

- 알고리즘

(1) 빈도수를 조사해 우선순위 큐에 삽입한다 : 빈도가 낮을 수록 우선순위가 높다.

(2) Queue에서 두 개의 노드 추출하여 binary tree로 구성한다. (root 노드는 두 노드의 빈도수 합을 취함)

(3) 생성된 root 노드를 우선순위 queue에 삽입

(4) 모든 노드들이 binary tree의 원소가 될 때까지 위의 과정을 반복한다.

(5) tree가 완성되면 root를 기준으로 왼쪽 0, 오른쪽 1을 부여한다.(이 순서는 바뀌어도 상관없다.)




18. Minimum Spanning Tree (최소 신장 트리)

- 최소 신장 트리(Minimum Spanning Tree) 정의 : Spanning tree(이하 S.T.) 중에서 가중치 합이 최소가 되는 S.T.

- Spanning Tree : 그래프의 모든 정점을 모두 포함하는 트리(Connected, Acyclic - 트리의 정의)

- N개의 vertex가 있으면 N-1개의 edge 존재


- Minimum Spanning Tree를 찾는 알고리즘

(1) Kruskal Algorithm (크루스칼 알고리즘)

- Greedy Algorithm : greedy choice property, optimal substructure - 부분 문제가 항상 최적의 해를 가진다고 가정

- Kruskal Algorithm 수행 방법

i) edge를 가중치(weight)에 의해 오름차순(내림차순)으로 정렬함

ii) 가중치가 작은 순서대로 선택한다. 단, 사이클은 만들지 않도록 선택한다. (union-find를 이용해서 집합에 원소가 있는지 확인)

iii) 모든 vertex가 연결되어 MST가 될 때까지 ii)를 반복한다.

- 시간 복잡도 : O(|E|log|E|)

(2) Prim's Algorithm (프림 알고리즘)

- Prim's Algorithm 수행 방법 : 그래프 G=(V,E)가 부분집합으로 주어졌을 경우

i) E의 부분집합 F={}, V의 부분집합 Y={v1(임의의 시작 정점)}으로 초기화

ii) V-Y에 속한 정점 중 Y에 가장 근접한(가중치가 가장 작은) 정점을 선택해서 Y에 추가한다.

iii) Y=V가 될 떄까지 ii)의 과정을 반복한다.

- 시간 복잡도 : O(|V|^2)





19. Hanoi Tower (하노이 타워)

- 하노이 타워는 재귀적인 호출을 이용해 해결함 

   (Divide & Conquer로 보기도 함 : n개의 원판 문제를 n-1개의 원판 sub problem으로 해결, 작은 문제를 해결해서 결국 n개의 원판 문제의 정답 구함)

- Hanoi tower 수행 방법

(1) Recursive way(재귀적인 방법)

     Hanoi_recursion(int depth, int n, int from, int by, int to){

          Hanoi_recursion(depth+1, n-1, from, to, by);   //N-1번째까지의 원판을 가운데로 옮김

          move(n, from, to);                             //N번째 원판을 세번째로 옮김

          Hanoi_recursion(depth+1, n-1, by, from, to);   // 가운데로 옮긴 N-1개의 원판을 세번째로 옮김

     }    


(2) Iterative way(순환적인 방법)

i) 홀수번째 스텝 : 1을 시계방향으로 이동

ii) 짝수번째 스텝 : 1이 없는 나머지 두 부분에서 legal move(규칙에 맞게 움직임, 반드시 하나의 가능한 이동은 존재)


[from]

=> Stack을 이용해서 구현 가능(Push, Pop)

[by]        [to]


- 시간 복잡도 : O(2^n)



20. 다음 점화식을 풀이하라.


       (무한 등비수열의 합 = a/(1-r))




21. Shortest Path Algorithm (최단 경로 알고리즘)

(1) Floyd Algorithm(플로이드 알고리즘)

: 인접행렬(Dist[][])을 사용하여 모든 정점 간 최단 경로를 찾을 때 사용한다.

 (Dijkstra algorithm 역시 두 정점 간 최단 경로를 모든 정점에 대해 확대하면 가능하지만, 모든 SP를 구할 때의 성능은 플로이드보다 나쁘다)


    for(k=0;k<=n;k++){

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){

                Dist[i][j] = min(Dist[i][j], Dist[i],[k] + Dist[k][j]);

            }

        }

    } 


(2) Dijkstra Algorithm(다익스트라 알고리즘)

- Greedy algorithm의 형태이며(각 sub problem이 모두 최적이라고 가정), Dynamic programming(이미 계산했던 값을 이용함)

- 인접행렬을 사용하여 구할 수 있다.

- 알고리즘

* w(u,v) : u->v의 가중치(weight)

i) 모든 노드의 dmin값을 v0부터 자신까지의 weight로 한다. (직접 연결된 edge가 없으면 무한대에 해당하는 값을 이용한다)

ii) v0를 T에 넣고, T에 없는 노드 중 dmin값이 가장 작은 노드(리스트 내의 정점들을 기준으로)를 u라고 하고, u를 T에 추가한다.

iii) T에 없는 모든 노드의 dmin값을 기존값과 dmin + g(u,w)중에서 더 작은 값으로 보정한다.

iv) T의 갯수가 n이 될 때까지 ii)와 iii)을 반복

- Dijkstra Algorithm의 증명 : 수학적 귀납법을 이용한 증명

i) u가 T에 포함되어 있으면 dmin(u)는 global Shortest path이다.

ii) u가 T에 포함되어 있지 않으면, dmin(u)는 dT(u) (T에 있는 노드만을 사용했을 때 Shortest path)





22. 유클리드 호제법(Euclidean algorithm) 증명

- 유클리드 호제법 : 두 개의 자연수 혹은 정식의 최대공약수를 구하는 알고리즘 (기존의 소인수분해 방식은 실제로 풀기 매우 어려운 방식이다)

- 유클리드 호제법 정의 : 아래와 같은 식이 있을 때 A, B의 최대공약수와 B, R의 최대공약수는 같다.


 


- 알고리즘

i) 입력으로 두 수 m, n(m>n)이 들어온다.

ii) n이 0이라면, m을 출력하고 알고리즘을 종료한다.

iii) n이 m을 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.

iv) 그렇지 않으면, n을 m에 대입하고, m을 n으로 나눈 나머지를 m에 대입하고 iii)으로 돌아간다.


- 알고리즘 증명

base) A와 B(A>B)의 최대 공약수(GCD=Greatest Common Divisor) = G

   다음과 같을 때 A = aG, B=bG이며 a와 b는 서로소이다.

step1) A와 B에는 다음과 같은 식이 성립한다고 가정하자. Q는 몫이고, R은 나머지다.

A = QB + R

   A에는 aG를, B에는 bG를 대입하면

aG = QbG + R이 되고

R = (a-Qb)G가 된다.

   따라서 R역시 G를 약수로 가지고 있다.

step2) 하지만 증명은 여기서 끝나서는 안된다. R역시 G를 약수로 가지고 있다고 해서 G가 최대공약수가 되는 것은 아니다.

    A와 B의 최대공약수(G)와 B와 R의 최대공약수가 같다는 것을 증명하기 위해

    B=bG이고 R=(a-Qb)G인 두 식에서, b와 a-Qb가 서로소임을 증명하면 된다.

    <귀류법 사용>

i) b와 a-Qb가 서로소가 아니라고 가정한다.

ii) 두 수가 서로소가 아니므로, 1이 아닌 공약수 d를 가지고 있다.

b = dn

a-Qb = dm

iii) 윗 식을 아래에 대입하면

a-Qdn = dm 이 되어

a = (Qn+m)d가 된다.

iv) 따라서 a 역시 d를 약수로 가지고 있다.

      => b=dn이고 a=(Qn+m)d가 되는데, 이 때 a와 b는 공약수를 d로 가진다.

=> 가정에서 a와 b는 서로소라고 한 사실과 모순이다.

v) 따라서, b와 a-Qb는 서로소이며, B=bG와 R=(a-Qb)G에서 두 수 B와 R 역시 최대공약수로 G를 가진다.








  1. (1) Decision problem : 답이 '예/아니오' 둘 중 하나로 결정되는 문제 [본문으로]
  2. Non-deterministic algorithm(비결정성 알고리즘) : 그 다음 단계가 유일하게 결정되지 않는 알고리즘 [본문으로]
  3. Turing machine이란 Deterministic한 알고리즘이나 Non-deterministic한 알고리즘을 풀이하는 가상의 기계를 의미하며, 이 세상의 모든 알고리즘은 튜링 머신의 계산으로 변환될 수 있다. [본문으로]
  4. Deterministic algorithm(결정성 알고리즘) : 각 단계에서 그 다음단계가 유일하게 결정되는 알고리즘 [본문으로]
  5. Functional problem : 답이 셋 이상의 경우의 수가 있는 문제 [본문으로]
  1. BlogIcon yh9003 2013.09.11 18:37 신고

    좋은 자료 감사합니다! 혹시 출처 남겨서 스크랩 해도 될지 여쩌봅니다.

    • BlogIcon 빽호랑 2013.09.17 02:18 신고

      죄송합니다만, 제가 공부하면서 끄적거리며 작성한 내용이다보니 개인적인 용도로 공부하시는데 이용하시고 공개글로 게시는 안하시는 편이 더 좋을 듯 합니다^^;

댓글을 입력하세요