집밖은 위험해

최단 경로 shortest path

최단 경로 조건

- 간선 가중치가 있는 유향 그래프

- 무향 그래프는 각 간선에 대해 유향 간선이 있는 유향 그래프로 생각할 수 있음

 -> 무향 간선 [u, v]는 유향 간선 [u,v]와 [v, u]가 존재한다고 가정하면 됨

두 정점 사이의 최단 경로

- 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로

- 간선 가중치의 합이 음인 싸이클이 있으면 문제가 정의되지 않음

단일 시작점 최단 경로

- 단일 시작점으로부터 각 정점에 이르는 최단 경로를 구함

- 다익스트라 알고리즘 : 음의 가중치를 허용하지 않는 최단경로

- 벨만 포드 알고리즘 : 음의 가중치를 허용하는 최단 경로

- 싸이클이 없는 그래프의 최단 경로

모든 쌍 최단 경로

- 모든 정점쌍 사이의 최단 경로를 모두 구함

- 플로이드-워샬 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘 개요

- 음의 가중치가 없는 그래프에서 한 노드에서 다른 모든노드까지의 최단 거리를 구하는 알고리즘

- 에츠허르 데이크스타라 라는 네덜란드 출신의 컴퓨터 과학자에 의해 고안됨

다익스트라 알고리즘 예제

1. 시작정점 r만 최단거리 0으로 초기화하고 다른 정점들의 최단거리는 모두 무한대로 초기화함

2. 정점 r을 집합 S의 첫 번째 워소로 포함 시킴

3. 정점 r에 연결된 집합 S 바깥의 정점들을 살핌

4. 정점 r에서 바깥 정점들에 이르는 거리를 각 정점에 기록함

- 집합 S는 정점 r만으로 구성되어있음

- r에서 정점에 이르는 거리는 각 '8', ''9', '11'임

- 정점에서 기록돈 값은 시작 정점 r에서 해당 정점에 이르는 현재까지의 최단 거리임

- 연결된 세 정점 각각 '8', '9', '11'의 최단 거리값을 가짐

- 나머지 정점들은 모두 무한대의 최단거리 값을 가짐

5. 계산되어 있는 최단거리가 가장 짧은 정점을 집합 S에 포함시킴

- 집합 S의 바깥 정점들 중 최단 거리값이 가장 낮은 것은 '8'임

- 가장 짧은 정점 '8'을 집합 S에 포함시키고 나니 한 정점의 최단 거리 값이 무한대에서 '18'로 바뀜

- 집합 S 바깥 정점들 중 최단거리 값이 가장 낮은 것은 '9'임

6. 연결 비용이 '9'인 정점을 집합 S에 포함시킴

- 최단거리 '18'이던 정점의 최단거리가 '10'으로 바뀜

 -> 정점의 최단 거리가 무한대가 아닌 수에서 바뀌는 이유 : 기존 경로보다 더 짧은 경로가 발견된 경우

 -> 정점의 최단 거리는 여러번 바뀔 수 있음

- 나머지 정점들 중 최단 거리 값이 가장 낮은 것은 '10'임

7. 연결 비용이 '10'인 정점을 집합 S에 포함시킴

- 가장 짧은 정점 '10'을 집합 S에 포함시키고 나니 한 정점의 최단거리값이 무한대에서 '12'로 바뀜

8. 최단거리 '11'인 정점이 집합 S에 추가됨

- 두 정점의 최단 거리 값이 무한대에서 '19'로 바뀜

9. 최단 거리 '12'인 정점이 집합 S에 추가됨

- 한 정점의 최단 거리 값이 '19'에서 '16'으로 바뀜

10. 최단거리 '16'인 정점이 집합 S에 추가됨

11. 마지막 정점이 '19'의 최단거리로 집합 S에 추가되면서 알고리즘이 끝남

다익스트라 알고리즘이 작동하지 않는 예제

ex1. 음의 가중치가 문제를 일으키는 경우

- 간선 하나를 6에서 -15로 바꿈

-> (b)처럼 최단거리 -6으로 바뀌어야 함.

벨만 포드 알고리즘

벨만 포드 알고리즘 개요

- 입력 그래프 G(V, E)에서 간선의 가중치가 음의 값을 허용햐는 임의의 실수인 경우 최단 경로 알고리즘

- 간선을 최대 1개를 사용하는 최단 경로, 간선을 최대 2개 사용하는 최단경로, ... 이러한 식으로 간선을 최대 n - 1개 사용하는 최단 경로까지 구함

벨만 포드 알고리즘 예제

1. 시작 정점 r의 최단거리만 0으로 세팅하고 나머지는 모두 무한대로 초기화

2. 모든 간선을 한번씩 살피면서 해당 간선으로 인해 앞으로 설정한 최단 거리가 더 짧아질 수 있는지 살펴봄

- 시작 정점에 연결된 세 정점만 변동이 생김

- 이들 최단 거리가 무한대에서 8, 9, 11로 각각 바뀜

3. 모든 간선을 다시 한번씩 살피면서 해당 간선으로 인해 앞에서 설정된 최단 거리가 더 짧아질 수 있는지 봄

- 앞에서 세 개의 정점에 변동이 생겼으므로 이번에는 이들로부터 연결된 정점들에 변동이 생길 수 있음

- 이들의 최단거리가 8, 무한대, 무한대, 무한대에서 -6, 10, 19, 19로 각각바뀜

- 이중 -6으로 바뀐 정점은 바로 전단계인 (b)에서도 바뀌었는데 최단 거리 9인 정점으로부터 연결되어 있어 다시 -6으로 바뀜

4. for 루프마다 모든 간선을 한 번씩 살피면서 해당 간선으로 인한 최단거리 변동 여부를 살펴봄

6. 마지막 for 루프 (i=7)에서는 아무런 변동이 일어나지 않음

- 시작 정점에서 7개의 간선을 사용하는 최단경로는 없다는 뜻

최소 신장 트리

1. 최소 신장 트리 개요

2. 프림 알고리즘

3. 크루스칼 알고리즘

최소 신장트리 minimum spanning tree

조건

- 무향 연결 그래프 -> 연결 그래프 : 모든 정점간에 경로가 존재하는 그래프

트리

- 싸이클이 없는 연결 그래프

- n개의 정점을 가진 트리는 항상 n-1개의 간선을 가짐

그래프 G(V, E)의 신장 트리

- 정점 집합 V를 그대로 두고, 간선을 |V| - 1개만 남겨 트리로 구성한것

 -> 아래의 좌측 그림에서 정점 개수는 9개로 사이클을 제거 -> 우측 그림은 9-1 = 8개의 간선을 가진 신장 트리

G의 최소 신장 트리

- G의 신장트리들 중 간선의 합이 최소인 신장 트리

-> 좌측 그래프의 간선을 지우는것에 따라 여러 개의 신장 트리가 만들어 질 수 있음. 

최소 비용 신장 트리를 만드는 알고리즘

1. 프림 알고리즘

2. 크루스칼 알고리즘

프림 알고리즘

- 집합 S를 공집합에서 시작하여 모든 정점을 포함할 떄 까지( 즉, S = V가 될 떄 까지) 키워나감

 -> 맨 처음 정점을 제외하고 정점을 하나 더할 떄 마다 간선이 하나씩 확정 됨

프림 알고리즘 동작 방법

1. 그래프에서 하나의 정점을 선택하여 트리를 만듬

2. 그래프의 모든 간선이 들어있는 집합을 만듬

3. 모든 정점이 트리에 포함되어 있지 않는 동안 트리와 연결된 간선 가운데 트리 속의 두 정점을 연결하지 않는 가장 가중치가 작은 간선을 트리에 추가함

프림 알고리즘 유사 코드

- 프림 알고리즘은 그리디 알고리즘의 일종 -> 그리디 알고리즘으로 최적해를 보장하는 드문 예

Prime (G, r)
{
    S <- 공집합;     // 정점 r을 방문되었다고 표시하고, 집합 S에 포함시킴
    while (S != V){
       S에서 V-S를 연결하는 간선들 중에 최소 길이의 간선 (x, y)을 찾는다. x \in S,  y \in V-S
       정점 y를 방문되었다고 표시하고, 집합 S에 포함시킨다.
    }

}

프림 알고리즘 동작과정

크루스칼 알고리즘

- 싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소 신장 트리를 만듦

 -> n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요함

 -> 최소에는 간선이 하나도 없는 상태에서 시작하여 n-1개의 산언을 더하면 더함

 * 프림 알고리즘은 정점을 기준으로 동작한다면, 크루수칼 알고리즘은 간선을 중심으로 동작

크루스칼 알고리즘 작동 예

위상 정렬 개요

- 완수해야할 여러가지 일이 있고 이들 간에 상호 선후 관계가 있는 경우

 -> 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것

ex 1. 특정 수강 과목에 선수 과목이 있는 예

 - 선수 과목 부터 수강해야 함

 - 수강 시 위상 정렬을 통해 올바른 수강 순서를 찾아 낼 수 있음

ex 2. 라면 끓이는 순서 예

위상 정렬의 조건

- 싸이클이 없는 유향 그래프

위상 정렬 topological sorting

1. 모든 정점을 일렬로 나열함

2. 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야함

3. 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재함

진입 간선

- u에 연결된 간선들 중 u로 향하는 간선

진출 간선

- u에 연결된 간선들 중 u로부터 나가는 가선

위상 정렬의 예시

- 아래의 좌측 그래프에 대한 위상 정렬의 예 2개

위상 정렬 유사 코드

topologicalSort1(G)
{
   for i <- 1 to n {
      진입 간선이 없는 정점 u를 선택함;
      A[i] <- u;
      정점 u와, u의 진출 간선을 모두 제거함;
   }
   이 시점에 배열 A[1 ... n]에는 정점들이 위상 정렬 되어 있음.
}

위상 정렬 알고리즘 작동 예

일상 생활에서 사용하는 많은 부분을 그래프로 나타낼 수 있음

- 지하철에서 역과 역사이의 관계, 사람간의 관계, 네비게이션 길찾기, 한붓 그리기 등

-> 그래프, 그래프 표현방법

그래프

- 현상이나 사물을 정점 vertex와 간선 edge로 표현한 것

- Graph G = (V, E) - V : 정점 집합, E : 간선 집합

- 두 정점이 간선으로 연결되어 있으면 인접하다고 함

 -> 인접 = adjacent

 -> 간선은 두 정점의 관계를 나타냄

그래프 예시

- 사람들간 친분 관계를 나타낸 그래프

- 각 사람을 하나씩의 정점으로 표시

- 서로 친밀한 사람 간에는 간선을 연결함

- 다른 예시

 1. 두 도시를 연결하는 도로의 존재 여부

 2. 두 집안간의 혼인 여부

친분 관계 그래프

- 친밀도를 가중치로 나타냄

- 간선에 가중치를 주어 친밀감의 정도를 보여줌

방향을 고려한 친분관계 그래프

- 간선이 방향을 가짐

- 유향 그래프 : 그래프가 방향을 가진 그래프

 -> 기업들 간 제품 공급 관계

 -> 제품 생산 공정에서 선후 관계 등

- 무향 그래프 : 그래프가 방향이 없는 그래프

가중치를 가진 유향 그래프

- 누가 누구를 얼마만큼 좋아하는지를 나타냄

- 다른 예

 -> 서울과 LA간 비행기 노선 처럼 가는데 걸리는 시간과 오는데 걸리는 시간이 다른 경우

그래프 표현 방법

1. 그래프 표현방법 개요

2. 인접 행렬을 이용한 방법

3. 인접 리스트를 이용한 방법

4. 그래프 탐색

그래프 표현 방법

- 행렬을 이용하는 방법

- 리스트를 이용하는 방법

인접 행렬을 이용하여 그래프를 나타내는 표현

- 인접 행렬(Adjacency Matrix)를 사용

- n x n 행렬로 표현

 -> 원소 (i, j) = 1 : 정점 i와 정점 j사이에 간선이 있음

 -> 원소 (i, j) = 0 : 정점 i와 정점 j사이에 간선이 없음

- 유향 그래프의 경우

 -> 원소 (i, j)는 정점 i로부터 정점 j로 연결되는 간선이 있는지를 나타냄

- 가중치가 있는 그래프의 경우

 -> 원소 (i, j)는 1대신 가중치를 가짐

인접 행렬을 이용한 예

1. 무향 그래프를 인접 행렬로 표현

2. 가중치를 가진 무향 그래프를 인접 행렬로 표현

3. 유향 그래프를 인접 행렬로 표현

4. 가중치를 가진 유향 그래프를 인접 행렬로 표현

1. 무향 그래프와 인접 행렬 표현

2. 가중치를 가진 무향 그래프와 인접 행렬 표현

3. 유향 그래프와 인접 행렬 표현

4. 가중치를 가진 유향 그래프와 인접 행렬 표현

인접 행렬을 이용한 방법의 효율성 분석

1. 이해가 쉽고 간선의 존재 여부를 즉각 알수 있다는 장점을 가짐

 - 정점 I와 정점 j의 인접 여부는 행렬 (i, j) 원소나 (j, i) 원소의 값만 보면 알 수 있기 때문

2. n x n 행렬이 필요하므로 n^2에 비례하는 공간이 필요함

 - 행렬의 준비 과정에서 행렬의 모든 공간을 채우는 데만 n^2에 비례하는 시간이 소모됨

 - O(n^2) 미만의 시간이 소요되는 알고리즘이 필요한 경우에 행렬 표현법을 사용하면 행렬의 준비과정에만 Theta(n^2)의 시간이 소모되어 적합하지 않음

3. 간선의 밀도가 아주 높은 그래프에서는 인접 행렬의 표현이 적합함

 - 전체 (i, j) 쌍에서 둘 중 하나 꼴로 간선이 있는 경우 행렬을 사용하는 것이 효율 적임

 - 100만 개의 정점을 가진 그래프에서 간선이 200만개 밖에 없는 경우에 행렬 표현을 쓰면 시간과 공간이 많이 낭비됨

   -> 행렬의 총 원소 수는 1조개, 이 중 고작 200만(또는 400만) 개만 1로 채워지고 나머지는 0이 되기 때문

인접 리스트 Adjacency List

- n개의 연결 리스트로 표현

- i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓은 것 임

- 가중치 있는 그래프의 경우 -> 리스트는 가중치도 보관함

인접 리스트를 이용한 예

1. 무향 그래프와 인접리스트

2. 가중치를 가진 그래프의 인접 리스트

1. 무향 그래프와 인접 리스트₩

2. 가중치를 가진 그래프의 인접 리스트 표현

그래프 탐색

1. 너비 우선 탐색 BFS Breath-First Search

2. 깊이 우선 탐색 DFS Depth-First Search

너비 우선 탐색

- 깊이가 1인 모든 정점을 방분

 -> 깊이가 2인 모든 정점을 방문

 -> 깊이가 3인 모든 정점을 방문 ... (계속 방문)

- 더이상 방문 할 곳이 없으면 탐색을 마침

깊이 우선 탐색

- 깊이 들어가는 특징을 지니고 있음

- 나아갈 길이 존재하지 않으면 이전 위치로 돌아와 다른 길을 선택하여 움직임

행렬 경로 문제

문제 정의

- 양 또는 음의 정수 원소들로 구성도니 n x n 행렬이 주어짐

- 행렬의 왼쪽 위에서 시작하여 한 칸씩 이동해 오른쪽 아래까지 도달

- 방문한 칸에 있는 수들을 더한 값이 이 경로의 합임

이동 방법(제약 조건)

- 오른쪽이나 아래쪽으로만 이동 가능

- 왼쪽, 위쪽, 대각선 이동은 허용하지 않음

목표

- 행렬의 왼쪽 위에서 오른쪽 아래까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대화 되도록 함

불법 이동의 예

- 위쪽이나 왼쪽으로 이동하여선 안됨

유효한 이동의 예시

최적 부분 구조

- c_ij를 원소 (i, j)에 이르는 최고 점수라고 정의.

- m_ij는 행렬 원소 (i, j)의 값

1. i = j = 1이면 원소 (1, 1)에 이르는 최고 점수를 구하는 것.

 -> 원소 (1,1)만 방문하므로 원소 (1, 1)의 값이 답

2. i = 1, j > 1이면 첫째 행의 한 원소에 이르는 최고 점수를 구하는 것

 -> 첫째 행을 따라 오른쪽으로 수평 이동하는 방법밖에 없음. 따라서, (1, j)의 바로 왼쪽 원소 (1, j-1)에 이르는

   점수 ((1, j - 1)에 이르는 유일한 점수이자 최고 점수)에 원소 (1, j)의 값을 더하면 됨.

3. i > 1, j = 1이면 첫째 열의 한 원소에 이르는 최대 점수를 구하는 것

 -> 첫째 열을 따라 수직 이동하는 방법 밖에 없음. 따라서 (i, 1)의 바로 위쪽 원소 (i-1, 1)에 이르는

   점수 ((i-1, 1)에 이르는 유일한 점수이자 최대 점수)에 원소 (i, 1)의 값을 더하면 됨

4. '1, 2, 3'의 경우가 아니면

 -> 원소 (i, j)의 바로 왼쪽 원소에 이르는 최고점수와 원소 (i, j)의 바로 위쪽 원소에 이르는 최고 점수 중 큰 것에

   원소 (i, j)의 값을 더한 것이 원소 (i, j)에 이르는 최고 점수 임.

재귀적인 알고리즘의 유사 코드

matrixPath(i, j) (i, j)에 이르는 최고 점수
{
   if (i = 1 and j = 1) then return m_11;
   else if (i=1) then return (matrixPath(1, j-1) + m_1j);
   else if (j=1) then return (matrixPath(i-1, 1) + m_i1 ;
   else return ((max(matrixPath(i-1, j), matrixPath(i, j-1)) + m_ij);
}

호출 트리

mathPath()에서 문제 크기가 커짐에 따라 중복 호출이 증가

=> 부분 문제들의 총 수는 n^2, 중복 호출 회수는 지수적으로 증가

동적 프로그래밍을 이용한 유사 코드

mathPath(n) //(n, n)에 이르는 최고 점수
{
   c[1, 1] <- m_11;
   for i<-2 to n
      c[i,1] <- m_i1 + c[i-1, 1];
   for j<-2 to n
      c[1,j] <- m_1j + c[1, j-1];
   for i<-2 to n
      for j<-2 to n
         c[i, j] <- m_1j + max(c[i-1, j], c[i, j-1]);
   return c[n, n];
}

-> Theta(n^2)의 시간 복잡도

재귀적 해법

- 큰 문제에 닮은 꼴의 작은 문제가 깃듬

- 잘쓰면 보약, 못쓰면 맹독

 -> 관계 중심적으로 파악함으로써 문제를 간명하게 볼 수 있음

 -> 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있음

재귀적 해법이 바람직한 경우

- 퀵/병합 정렬 등 정렬 알고리즘

- 계승 구하기

- 그래프의 dfs 깊이 우선 검색

재귀적 해법이 치명적인 경우

- 피보나치 수 구하기

- 행렬 곱샘 최적 순서 구하기

동적 프로그램이의 기원

- 미국의 수학자 리처드 벨만이 1940년대 사용하던 용어

- 큰 문제안에 작은 문제가 중첩되어 있는 문제를 해결하는데 사용하는 방법을 동적 계획법이라 이름 붙임

- dynamic 이란 말은 벨만이 이런 알고리즘의 시가변적이며 다단계적인 특성을 나타내기 위해 채택한 용어

- programming 이란 단어는 공군 내에서도 워드프로세스 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것임

동적 프로그래밍이란

- 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 재귀적 중복을 해결하는 방법

- 재귀적 중복을 해결하기 위해, 적절한 저장 방법으로 중복 호추르이 비효율성을 제거 한 것

동적 프로그래밍 조건

- 최적 부분 구조를 이루어야함

- 재귀적으로 구현했을때 중복 호출로 심각한 비효율이 발생함

동적 프로그래밍 전략

- 기본적으로 분할 정복 알고리즘과 비슷

- 동적 프로그래밍을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분문제의 답을 계산하고, 이 계산한 결과 값을 이용해 원래 문제의 답을 산출하기 때문

분할 정복 알고리즘과의 차이점

- 분할 정복 알고리즘 : 원래 문제를 부분 문제로 나눔

- 동적 프로그래밍 : 주어진 부분 문제 정담답을 저장 해둔 뒤 동일 문제를 이용 할 때 저장해둔 정답을 바로 산출하여 이용함(속도 향상)

피보나치 수의 정의

- f(n) = f(n-1) + f(n-2)

- f(1) = f(2) = 1

- n의 피보나치 수는 n-1의 피보나치 수와 n-2의 수를 포함함

-> 최적 부분 구조 : 이처럼 큰 문제의 해답에 작은 문제의 해답이 포함 된 경우

피보나치 수를 구하는 재귀 알고리즘

fib(n)
{
  if (n = 1 or n = 2)
     then return 1;
     else return (fib(n - 1) + fib(n - 2));
}

-> 중복 호출이 많이 발생

피보나치 수열의 재귀 알고리즘 call tree

- fib(3)을 구할떄는 fib(2)와 fib(1)이 필요

- fib(4)을 구할때 fib(2)가 2번 호출

- fib(5)는 fib(2)가 3번 호출

- fib(6)을 구할때는 fib(2)가 6번 호출

중복 호출이 증가하는 정도

- 중복 호출 회수 자체가 다시 피보나치 수열을 이름

- 증가 속도 : Omega(2^{n/2}) -> 지수 함수적

동적 프로그래밍을 이용한 해법

- 접근 방법 : 중복되는 호출 결과를 한번만 구해 저장해 놓았다가 나중에 다시 사용

- ex : fib(3)을 처음 호출하고 결과를 얻었으면 이것을 어딘가에 저장해두고 나중에 fib(3)이 필요하면 저장된 것을 이용

피보나치 수열과 동적 프로그래밍 조건

- 최적 부분 구조를 이루어야 함 -> 만족

- 재귀적으로 구현했을때 중복 호출로 심각한 비효율이 발생함 -> 만족

=> 동적 프로그래밍이 그 해결책

피보나치 수를 구하는 동적 프로그래밍 해법 유사 코드

fibonacci(n)
{
   f(1) <- f(2) <- 1;
   for i <- 3 to n
      f[i] <- f[i-1] + f[i-2];
   return f[n];
}

=> Theta(n) 시간에 끝난다.

해시

- 원재료를 다른 재료와 함께 다지고 섞어서 새로운 형태의 요리로 만드는 것

자료구조의 해시

- 데이터를 입력 받으면 완전히 다른 모습의 데이터

해시 테이블 개개요

- 아래의 배열에서 623453을 찾기 위해서 어떻게 해야할까?

- 지금 상태에서는 순차 탐색 밖에 대안이 없음

-> 원하는 값이 k번째에 있는 경우 k번 비교 연산을 수행해야함

해시 테이블 개요

1. 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료 구조

- 저장된 자료와 비교를 통해 자리를 찾지 않고 단 한번의 계산으로 자신의 자리를 찾음

2. 직접 주소 테이블 direct address tables

- 원본 데이터의 키를 직접 주소 테이블의 주소에 바로 기재하는 방법

  -> 크기가 |U|인 테이블 T를 생성하고 키 k를 slot k에 저장하는 방식

- 키가 중복되어서는 안됨

3. 평균 상수 시간에 삽입, 삭제, 검색

- 매우 빠른 응답을 요구하는 응용에 유용함

 -> ex : 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록시스템

- 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않음

해시 테이블의 예시

- 입력 : 25, 13, 16, 15, 7

- 해시 함수 h(x) = x mod 13

-> 탐색 성능은 향상되었으나 저장 공간은 희생 됨

해시 함수

- 키 값을 입력으로 받아 해시 테이블 상 주소를 리턴

- 해시 함수가 가져야 하는 성질 : 입력 원소가 해시 테이블 전체에 고루 저장되어야 함. 계산이 간단해야함

해시 함수 종류

1. 제산법 division method

2. 곱하기 방법 multiplication method

3. 제곱법 mid square

4. 숫자 분석법 digit analysis

5. 이동법 shifting

6. 기수변환법 radix conversion

7. 접지법 floding

8. 난수 생성법 pseudo random

9. 대수적 코딩 algebraic coding

10. 자릿수 재배열

레코드

- 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위

ex 사람의 레코드

- 주민번호, 이름, 집주소, 집 전화번호 ,직장전화번호, 휴대전화번호, 연소득 등

ex 학생의 레코드

- 이름, 학번, 주소, 연락처 등의 정보 포함

필드

- 레코드에서 각가의 정보를 나타내는 부분

ex 학생의 레코드

- 필드 : 이름, 학번, 주소, 연락처

키, 검색키

- 다른 레코드와 중복되지 않도록 각 레코드를 대표할수 있는 필드

- 키는 하나의 필드나 두 개 이상의 필드로 이루어 질 수 있음

검색 트리

1. 자료를 저장하고 검색하는데 유용한 자료구조이며 알고리즘

2. 레코드를 트리 모양으로 만들어서 자료를 저장하고 찾음

3. 각 노드가 규칙에 맞도록 하나씩의 키를 가지고 있음

4. 1:n 관계의 비선형 자료구조

5. 계층 관계로 만들어진 계층형 자료구조

검색 트리의 요소

- 노드 node : 트리를 구성하는 원소

- 간선 edge : 노드를 연결하는 선

- 루트 노드 root : 트리 시작 노드

- 부모 노드 parent

- 자식 노드 child

- 형제 노드 sibling : 같은 부모 노드를 가진 자식 노드

- 차수 degree : 자식 노드 수

- 레벨 level : 특정 깊이에 해당하는 노드 집합

- 리프 노드, 단말 노드 : 차수가 0인 노드

검색 트리의 종류

1. 자식 노드의 개수에 따른 분류

- 이진 검색 트리 : 최대 두 개 이상의 자식 노드

- 다진 검색 트리 : 세 개 이상의 자식 노드로 분기

2. 저장되는 장소에 따른 분류

2.1. 내부 검색 트리

- 메인 메모리내에 존재

- 메인 메모리에 있는 모든 키를 수용할 수 있으며 내부 검색 트리 사용

2.2 외부 검색 트리

- 검색 트리가 외부(주로 하드디스크)에 존재

- 메인 메모리에 모든 키를 수용하지 못하면 외부검색트리를 사용

- 디스크 접근 시간이 검색의 효율을 좌우함

이진 검색 트리

- 최대 두 개의 자식 노드를 갖는 검색 트리

- 각 노드는 하나씩의 키를 가짐

- 각 노드의 키 값은 다름

- 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두개의 자식을 가짐

- 임의의 노드의 키 값은 자신의 왼쪽 자식 노드의 키 값보다 크고 오른쪽 자식의 키 값보다 작음

이진 검색 트리 검색 방법

1. 키 x를 가진 노드를 검색

2. 트리에 키 x를 가진 노드가 존재하면 해당 노드를 리턴함

3. 존재하지 않으면 NIL을 리턴

treeSearch(t, x) //t : 서브 트리의 루트 노드, x 검색하고자 하는 키
{
   if (t = NIL or key[t]=x) then return t;
   if (x < key[t])
       then return treeSearch(left[t], x);
       else return treeSearch(right[t], x);

}

리스트

- 동일한 값이 두 번 이상 나타날수 있는, 셀수 있는 정렬된 값을 나타내는 자료구조

리스트 종류

1. 선형 리스트

2. 단일 연결 리스트

3. 이중 연결 리스트

4. 원형 연결리스트

선형 리스트

- 리스트 중에서 순서를 가지는 리스트

- 순차 방식으로 구현하는 선형 순차 리스트

- 순차 자료구조는 원소를 논리적은 순서대로 메모리에 연속하여 저장

- 원소의 삽입, 삭제가 비효율적임

단일 연결 리스트

- 저장할 떄 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 자료구조

- 각 노드는 다음 노드를 가리키는 포인터를 가짐

- 각 노드로 다음 노드를 가리키는 포인터로 연결하여 만든 리스트

- 하지만 포인터 데이터를 잃어버리면 이후 데이터들을 손실하게 됨

typedef struct tagNode
{
   int Data; //데이터 필드
   struct tagNode* NextNode; //다음 노드를 가리키는 포인터
} Node;

이중 연결 리스트

- 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키게한 연결 리스트

원형 연결 리스트

- 이중 연결 리스트에서 마지막 원소가 널 대신 처음 원소를 가리키게 한 연결 리스트

스택

- 먼저 들어간 요소가 가장 나중에 나오는(LIFO, Last in First Out) 자료구조

-  스택에서의 삽입(push), 스택에서의 삭제(pop)

- 스택의 응용 : 역순 문자열 만들기, 시스템 스택

역순 문자열 만들기

1. 문자열 ABCD를 스택에 삽입

2. pop을 하면 DCBA가 출력

시스템 스택

- 함수 호출과 복귀에 따른 전체 프로그램 수행 순서

- 함수를 수행 후 돌아올수 있는 지점을 저장하는 곳이 시스템 스택

시스템 스택 예시

1. main()함수 실행 시작

2. F_1() 함수 호출

3. 호출된 함수 F_1() 실행

4. F_2() 함수 호출

5. 호출된 함수 F_2() 함수 실행

6. F_2() 함수 실행 종료, F_1() 함수로 복귀

7. F_1() 함수로 복귀하여 F_1() 함수의 나머지 부분 실행

8. main()함수 실행 완료(전체 프로그램 실행 완료) -> 스택 프레임도 삭제

큐

- 먼저집어넣은 데이터가 먼저 나오는 FIFO(First In, First Out)구조로 저장하는 자료구조

- 삽입 enQueue, 삭제 deQueue

선택 알고리즘

- n개의 원소가 불규칙하게 저장된 배열에서 i번째 작은 원소(큰 원소)를 찾는 문제를 해결하기 위한 알고리즘

- 정렬과 비슷

- 두 가지 알고리즘

 1. 평균적으로 선형 시간이 소요되는 알고리즘

 2. 최악의 경우에 선형 시간이 소요되는 알고리즘

평균 선형시간 선택 알고리즘

- 퀵 정렬처럼 분할한 후 자기 호출 방법을 이용하여 평균적으로 선형시간 i번째 작은 원소를 찾는 것

배열 A에서 i번째 요소 찾기

- 경우 1. 워소가 하나뿐인 경우 하나 리턴

- 경우 2. 원소가 다수인 경우, 파티션을 통해 중간값이 몇번째인지 확인

- 경우 3. 중간값이 i와 같은 경우, A[파티션을 통해 얻은 중간] 값을 리턴

- 경우 4. 중간 값이 i보다 클 경우, 오른쪽 그룹으로 범위를 좁혀 재귀적으로 실행

- 경우 5. 중간 값이 i보다 작을 겨웅, 왼족 그룹으로 범위를 좁혀 재귀적으로 실행

평균 선형시간 선택 알고리즘 작동 예

- 2번째 작은 원소 찾기

- 기준 원소를 r이라 지정하고 분할 수행

- 15와 31을 비교, 15와 8을 비교 ... 15를 기준으로 큰 수는 15 뒤 작은 수는 15 앞

- r을 3으로 지정하여 다시 분할 수행

유사 코드

select(A, p, r, i) //배열 A[p ... r]에서 i번째 작은 워소를 찾는다
{
   if (p = r) then return A[p];            //원소가 하나 뿐인 경우 i는 반드시 1
   q <- partition(A, p, r);
   k <- q - p + 1;                 //k : 기준 원소가 전체에서 k번째 작은 원소임을 의미
   if (i < k) then return select(A, p, q-1, i); // 왼쪽 그룹으로 범위를 좁힘
   else if (i = k) then return A[q];           // 기준 원소가 바로 찾는 원소임
   else return select(A, q+1, r, i-k);         // 오른쪽 그룹으로 범위를 좁힘
}

최악의 경우 선형시간 선택 알고리즘

- 평균 선형 시간 선택 알고리즘의 단점

-> 분할 균형이 맞지 않고, 찾고자 하는 원소가 운나쁘게 큰 그룹에 속하는 일이 반복하는 경우 성능이 보장되지 않음

- 분할 균형이 나빠보여도 일정한 상수비를 유지하면 점근적 복잡도는 항상 Theta(n)이 됨

- 균형을 맞추기 위한 오버헤드가 너무 커져버리면 최악의 경우 선형시간 선택 알고리즘이 될 수 없음.

linearSelect(A, p, r, i) //배열 A[p ... r]에서 i번째 작은 원소를 찾는다
{
  1. 원소 총 수가 5개 이하면 원하는 원소를 찾고 알고리즘을 끝냄
  2. 전체 원소들을 5개씩 원소를 가진 [n/5]개의 그룹으로 나눔
   - 원소의 총 수가 5의 배수가 아니면 이 중 한 그룹은 5개 미만이 됨.
  3. 각 그룹에서 중앙값(원소가 5개이면 3번째 원소)을 찾임
   - 이렇게 찾은 중앙값들을 m1, m2, .., m_{n/5}라 함
  4. m1, m2 ..., m_{n/5}들의 중앙값 M을 재귀적으로 구함
   - 홀수면 중앙값이 하나이므로 문제없고, 원소의 총 수가 짝수인 경우 두 중앙값중 아무거나 임의로 선택
      -> call linearSelect()
  5. M을 기준 원소로 삼아 전체 원소를 분할함
   - M보다 작거나 같은것은 M의 왼쪽에 M보다 큰 것은 M의 오른쪽에 오도록 함
  6. 분할 된 두 그룹 중 적합한 쪽을 선택하여 단계 1 ~ 6을 재귀적으로 반복함 -> call linserSelect()
   

}

최악의 경우 선형시간 선택 알고리즘 동작

1. 원소들이 한쪽으로 몰리는 경우

- 원/사각형 그룹 -> 3n/10 - 3개의 원소

- M까지 포함하는 경우 -> 3n/10 - 2개

- 이를 제외한 원소들 -> n - (3n/10-2) = 7n/10 + 2

- 최악의 경우 -> 7n/10 + 3 : 3n/10-3

 => 대략 7:3

정렬 알고리즘

1. 정렬이란?

2. 정렬의 에

3. 정렬 방식 구분

정렬

- 알고리즘에서 설계와 분석, 생각하는 방법 등을 훈련하기 위한 적합한 주제

- 알고리즘 분야에서 사용하는 여러 기술부분들이 상당 부분 정렬에 포함되 있어, 정렬을 잘 이해하면 알고리즘 과정에서 다른 주제를 이해하는데 큰 도움 될 것!

정렬의 정의

- 순서 없이 배열된 자료를 오름차순이나 내림차순으로 나열한 것

- 컴퓨터 공학을 포함한 모든 과학기술분야에서 가장 기본적이고 중요한 알고리즘 중 하나

- 자료 탐색에 있어서 필수 적임 : 만약 영어 사전에서 단어들이 알파벳 순으로 정렬되어 있지 않다면?

정렬의 대상

- 일반적으로 정렬시켜야 할 대상 = 레코드

- 레코드는 보다 작은 단위인 필드로 구성

- 키 필드로 레코드 식별

정렬 방식 구분

- 정렬은 실행 방법과 정렬 장소를 기준으로 아래 표와 같이 구분할 수 있음