IT, FIRE, License and Daily life

<인접 행렬(adjacent matrix)>

행렬에 대한 2차원 배열을 사용하는 순차 자료구조 방법이다. 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장한다.
- n개의 정점을 가진 그래프 : n x n 정방행렬
- 행렬의 행번호와 열번호 : 그래프의 정점
- 행렬 값 : 두 정점이 인접되어있으면 1, 인접되어있지 않으면 0 

무방향 그래프의 인접 행렬 : 행 i의 합 = 열 i의 합 = 정점 i의 차수
방향 그래프의 인접 행렬 : 행 i의 합 = 정점 i의 진출차수, 열 i의 합 = 정점 i의 진입차수 

ex - 1)

G1

ex - 2)

G2

ex - 3)

G3

ex - 4)

[인접 행렬 표현의 단점]
- n개의 정점을 가지는 그래프를 항상 n x n개의 메모리 사용
- 정점의 개수에 비해서 간선의 개수가 적은 희소 그래프에 대한 인접 행렬은 희소 행렬이 되므로 메모리의 낭비 발생

Copyrightⓒ2014 By 한빛아카데미(주)

<그래프(graph)>

선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계를 가지는 원소들을 표현하기 위한 자료구조
그래프 G
- 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합
G = (V, E)
- V는 그래프에 있는 정점들의 집합
- E는 정점을 연결하는 간선들의 집합
그래프사용 예 : 버스노선도, 지하철노선도, 인맥 지도, 길찾기, 최단거리 구하기

<그래프의 종류>

1. 무방향 그래프(undirected graph)
두 정점을 연결하는 간선의 방향이 없는 그래프이며, 정점 Vi와 정점 Vj을 연결하는 간선을 (Vi, Vj)로 표현 - (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미.
V(G1)={A, B, C, D} E(G1)={(A,B), (A,D), (B,C), (B,D), (C,D)}
V(G2)={A, B, C} E(G2)={(A,B), (A,C), (B,C)}

                                    G1                                  G2

                              G3                                    G4

3. 완전 그래프(complete graph)
각 정점에서 다른 모든 정점을 연결하여 가능한 최대의 간선 수를 가진 그래프이다.
정점이 n개인 무방향 그래프에서 최대의 간선 수 : n(n-1)/2개
정점이 n개인 방향 그래프의 최대 간선 수 : n(n-1)개
완전 그래프의 예
- G5는 정점의 개수가 4개인 무방향 그래프이므로 완전 그래프가 되려면 4(4-1)/2=6개의 간선 연결

- G6은 정점의 개수가 4개인 방향 그래프이므로 완전 그래프가 되려면 4(4-1)=12개의 간선 연결

                                G5                                     G6

4. 부분 그래프(subgraph) : G'
원래의 그래프에서 일부의 정점이나 간선을 제외하여 만든 그래프이다.
그래프 G와 부분 그래프 G'의 관계
V(G')⊆V(G), E(G')⊆E(G)
그래프 G1에 대한 부분 그래프의 예

                                 G1                                          G`

5. 가중 그래프(weight graph) , 네트워크(network)
정점을 연결하는 간선에 가중치(weight)를 할당한 그래프

                               G7                                        G8                        

<​그래프 관련 용어>

​1. 그래프에서 두 정점 Vi과 Vj를 연결하는 간선 (Vi, Vj)가 있을 때, 두 정점 Vi와 Vj를인접(adjacent)되어 있다고 하고,
2. 간선 (Vi, Vj)는 정점 Vi와 Vj에 부속(incident)되어있다고 한다.

ex) 그래프 G1에서 정점 A와 인접한 정점은 B와 D이고, 정점 A에 부속되어 있는 간선은 (A,B)와 (A,D)이다.

                                                    G1

                                                  G3

3. 차수(degree) – 정점에 부속되어있는 간선의 수
ex) 무방향 그래프 G1에서 정점 A의 차수는 2, 정점 B의 차수는 3
방향 그래프의 정점의 차수 = 진입차수 + 진출차수
- 방향 그래프의 진입차수(in-degree) : 정점을 머리로 하는 간선의 수
- 방향 그래프의 진출차수(out-degree) : 정점을 꼬리로 하는 간선의 수
- 방향 그래프 G3에서 정점 B의 진입차수는 1, 진출차수는 2
정점 B의 전체 차수는 (진입차수 + 진출차수) 이므로 3이 된다.

4. 경로(path) - 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것 즉, 정점 Vi에서 Vj까지 간선으로 연결된 정점을 순서대로 나열한 리스트
ex) 그래프 G1에서 정점 A에서 정점 C까지의 경로 : A-B-C 경로, A-B-D-C 경로, A-D-C 경로, A-D-B-C 경로

5. 경로길이(path length) - 경로를 구성하는 간선의 수

6. 단순경로(simple path) - 모두 다른 정점으로 구성된 경로
ex) 그래프 G1에서 정점 A에서 정점 C까지의 경로 A-B-C는 단순경로이고, 경로 A-B-D-A-B-C는 단순경로가 아니다.

7. 사이클(cycle) - 단순경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로
ex) 그래프 G1에서 단순경로 A-B-C-D-A는 사이클이 된다.

8. DAG(directed acyclic graph) - 방향 그래프이면서 사이클이 없는 그래프 

9. 연결 그래프(connected graph) - 서로 다른 모든 쌍의 정점들 사이에 경로가 있는 그래프 즉, 떨어져있는 정점이 없는 그래프
그래프에서 두 정점 Vi에서 Vj까지의 경로가 있으면 정점 Vi와 Vj가 연결(connected)되었다고 한다. 

10. 트리는 사이클이 없는 연결 그래프이다.

Copyrightⓒ2014 By 한빛아카데미(주)

<이진 탐색 트리(Binary Search Tree)>

이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조이다.
[이진 탐색 트리의 정의]

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.

[이진 탐색 트리의 탐색 연산]
1. 루트에서 시작한다.
2. 탐색할 킷값 x를 루트 노드의 킷값과 비교한다.
3. (킷값 = 루트노드의 킷값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공
4. (킷값 < 루트노드의 킷값)인 경우 : 루트노드의 왼쪽 서브트리에 대해서 탐색연산 수행
5. (킷값 > 루트노드의 킷값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행
-> 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

[알고리즘]

예) 원소 11 탐색하기
① 찾는 킷값 11을 루트노드의 킷값 8과 비교
(찾는 킷값 11 > 노드의 킷값 8) 이므로 오른쪽 서브트리를 탐색
② (찾는 킷값 11 > 노드의 킷값 10) 이므로, 다시 오른쪽 서브트리를 탐색
③ (찾는 킷값 11 < 노드의 킷값 14) 이므로, 왼쪽 서브트리를 탐색
④ (찾는 킷값 11 = 노드의 킷값 11) 이므로, 탐색 성공! (연산 종료)

[이진 탐색 트리의 삽입 연산]
1. 먼저 탐색 연산을 수행
- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.
2. 탐색 실패한 위치에 원소를 삽입한다.

예) 원소 4 삽입하기
① 찾는 킷값 4를 루트노드의 킷값 8과 비교하여, (찾는 킷값 4 < 노드의 킷값 8) 이므로, 왼쪽 서브트리를 탐색한다.
② (찾는 킷값 4 > 노드의 킷값 3) 이므로, 오른쪽 서브트리를 탐색한다.
③ (찾는 킷값 4 < 노드의 킷값 5) 이므로, 왼쪽 서브트리를 탐색해야하는데 왼쪽 자식노드가 없으므로 탐색 실패!
이때, 탐색 실패가 결정된 위치 즉, 왼쪽 자식노드의 위치가 삽입 위치가 된다.
④ 탐색작업으로 찾은 자리 즉, 노드 5의 왼쪽 자식노드 자리에 노드 4를 삽입한다.

[이진 탐색 트리의 삭제 연산]
1. 먼저 탐색 연산을 수행
2. 탐색하여 찾은 노드를 삭제한다.
3. 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요하다. 

−삭제할 노드의 경우

① 삭제할 노드가 단말노드인 경우 : 차수가 0인 경우

② 삭제할 노드가 하나의 자식노드를 가진 경우 : 차수가 1인 경우

노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다.
- 후속 처리 : 이진 탐색 트리의 재구성. 삭제한 부모노드의 자리를 자식노드에게 물려준다.

③ 삭제할 노드가 두개의 자식노드를 가진 경우 : 차수가 2인 경우

Copyrightⓒ2014 By 한빛아카데미(주)

<이진트리(Binary Tree)>

트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리이다. 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만을 가진다.
- 부모 노드와 자식 노드 수와의 관계 -> 1:2
- 공백 노드도 자식 노드로 취급한다.
0 ≤ 노드의 차수 ≤ 2

[이진트리의 특성]
1. n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
− 루트를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한 개의 간선을 가짐

2. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.
− 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h+1)개
− 하나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2i개 이므로 높이가 h인 이진 트리 전체의 노드 개수는 2^(h+1)-1 개

ex) 높이가 3이면서 최소의 노드를 갖는 이진트리와 최대의 노드를 갖는 이진트리

<포화이진트리(Full Binary Tree)>

<편향 이진 트리(Skewed Binary Tree)>

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리 

왼쪽 편향 이진 트리
−모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리
오른쪽 편향 이진 트리

−모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리

<연결 자료구조를 이용한 이진트리>

단순 연결 리스트를 사용하여 구현. 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

[구조체]

typedef struct treeNode {
char data;
struct treeNode *left;
struct treeNode *right;
} treeNode;

[연결 자료구조의 이진트리 그림]

<이진 트리의 순회(traversal)>

계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산이다.
순회를 위해 수행할 수 있는 작업 정의
⑴ 현재 노드를 방문하여 데이터를 읽는 작업 D
⑵ 현재 노드의 왼쪽 서브트리로 이동하는 작업 L
⑶ 현재 노드의 오른쪽 서브트리로 이동하는 작업 R

1. 전위 순회(preorder traversal) : root-left-right
[수행 방법]
① 현재 노드 n을 방문하여 처리한다. : D(루트에서 아래로 내려서 처리)
② 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리 끝까지 처리)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리 처리)

2. 중위 순회(inorder traversal) : left – root - right
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리를 시작하여)
② 현재 노드 n을 방문하여 처리한다. : D(하위에 걸친 루트까지 거친 후)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리로 이동)

3. 순회(postorder traversal): left - right - root
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위트리부터 시작후)
② 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(우측 형제노드이동방문후)
③ 현재 노드 n을 방문하여 처리한다. : D(루트 노드까지만이동후, 다시 L)

Copyrightⓒ2014 By 한빛아카데미(주)

<트리(Tree)>
​

원소들 간에 1:多 관계를 가지는 비선형 자료구조이며, 원소들 간에 계층관계를 가지는 계층형 자료구조이다. 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

[트리관계 해설]

① 노드(node) – 트리의 원소
−트리 A의 노드 - A,B,C,D,E,F,G,H,I,J,K,L
② 루트 노드(root node) – 트리의 시작 노드 (루트노드 - A)
③ 간선(edge) – 노드를 연결하는 선. 부모 노드와 자식 노드를 연결
④ 형제 노드(sibling node) – 같은 부모 노드의 자식 노드들 (B,C,D는 형제 노드)
⑤ 조상 노드 – 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 (K의 조상 노드 : F, B, A)
⑥ 서브 트리(subtree) – 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
−각 노드는 자식 노드의 개수 만큼 서브 트리를 가진다.
⑦ 자손 노드 – 서브 트리에 있는 하위 레벨의 노드들 (B의 자손 노드 – E,F,K,L)

⑧ 차수(degree) - 노드의 차수 : 노드에 연결된 자식 노드의 수.
A의 차수=3, B의 차수=2, C의 차수=1, D의 차수=3
⑨ 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
트리 A의 차수=3
⑩ 단말 노드(리프 노드) : 차수가 0인 노드. 자식 노드가 없는 노드

노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
B의 높이=1, F의 높이=2

포리스트(forest) : 서브트리의 집합
−트리A에서 노드 A를 제거하면, A의 자식 노드 B, C, D에 대한 서브 트리가 생기고, 이들의 집합은 포리스트가 된다.

Copyrightⓒ2014 By 한빛아카데미(주)

<덱(Deque)>

큐의 양쪽 끝에서 삽입 연산과 삭제 연산을 수행할 수 있다. 스택의 특성과 큐의 특성을 모두 가지고 있다.

덱의 front와 rear의 구조를 보면 다음과 같다.

Copyrightⓒ2014 By 한빛아카데미(주)

<연결 큐(연결리스트 큐)>

[연결 큐 알고리즘]

1. 공백 연결 큐 생성

createLinkedQueue()

   front <- null;

   rear <- null;

end createLinkedQueue()

2. 공백 연결 큐 검사

isEmpty(LQ)

   if(front=null) then return true;

   else return false;

end isEmpty()

3. 연결 큐의 삽입

enQueue(LQ, item)

   new <- getNode();   // ⓐ

   new.data <- item;

   new.link <- null;

   if(front=null) then {  // ⓑ

      rear <- new;

      front <- new;

   }

   else {   // ⓒ

      rear.link <- new;

      rear <- new;

   }

end enQueue()

ⓐ 삽입할 새 도르를 생성하여 데이터 필드에 item을 저장.

ⓑ 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지를 검사

ⓒ 큐가 공백이 아닌경우, (노드가 있는 경우) 현재 큐의 마지막 노드의 다음에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정

4. 연결 큐 삭제

deQueue(LQ)

   if(isEmpty(LQ)) then Queue_Empty();

   else {

      old <- front;          // ①

      item <- front.data;

      front <- front.link;   // ②

      if (isEmpty(LQ)) then rear <- null;  // ③

      returnNode(old);     // ④

      return item;

}

end deQueue()

​

​①  old <- front;

front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다.

② front <- front.link;

삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드)가 되어야 하므로, 포인터 front를 재설정한다.​ 

③ if (isEmpty(LQ)) then rear <- null;

현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 큐의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다.​

④ ​returnNode(old);

포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환한다​

삭제만 하는 연산

/*

delete(LQ)

   if(isEmpty(LQ) then Queue_Empty();

   else {

      old <- front;

      front <- front.link;

      if(isEmpty(old)) then rear <- null;

      returnNode(old);

   }

end delete()

*/

5. 연결 큐의 검색

peek(LQ)

   if(isEmpty(LQ)) then Queue_Empty()

   else return (front.data);

end peek()

​

​

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 큐>

1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용.

초기 공백 상태 : front = rear = 0
front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해서 나머지연산자 mod를 사용한다.
3 ÷ 4 = 0 …3 (몫=0, 나머지=3)
3 mod 4 = 3

[원형 큐 알고리즘]

[코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<큐(Queue)>

스택과 마찬가지로 삽입과 삭제의 위치가 제한되어있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조로 되어 있다.
선입선출 구조 (FIFO, First-In-First-Out) : 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다.

2개의 포인터를 가지고 한쪽 끝에서 삽입이 발생되고 다른 한쪽 끝에서 삭제가 일어나는 순차적 구조이다. 뒤(rear)에서 노드가 삽입되고 앞(front)에서 삭제가 일어나도록 제한된다.

[적용분야] -> 정보처리 산업기사/기사 문제에도 나옴
컴퓨터 운영체제 작업 스케쥴링(job scheduling)이나 시분할 방식에 많이 사용되고, 키보드를 사용한 컴퓨터로의 입력이나 모니터, 프린트기를 사용한 출력에 사용된다.

큐의 연산은 enQueue와 deQueue로 한다.

enQueue : 삽입연산, (스택으로 비교하자면 push를 말함)

deQueue : 삭제연산 (스택으로 비교하자면 pop을 말함)

[큐 알고리즘 풀이]

<1차원 배열을 이용한 큐>

큐의 크기 = 배열의 크기
- 변수 front : 저장된 첫 번째 원소의 인덱스 저장
- 변수 rear : 저장된 마지막 원소의 인덱스 저장
- 초기 상태 : front = rear = -1 공백 큐 생성
- 공백 상태 : front = rear
- 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

[코드]

<전위 표기법(prefix notation)>

연산자를 피연산자를 앞에 표기하는 방법
예) +AB

중위 표기를 전위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.

② 각 연산자를 그에 대응하는 왼쪽괄호의 앞으로 이동시킨다.

③ 괄호를 제거한다.​

<중위 표기법(infix notation)>

연산자를 피연산자의 가운데 표기하는 방법
예) A+B

<후위 표기법(postfix notation)>

연산자를 피연산자 뒤에 표기하는 방법

예) AB+

중위 표기를 후위 표기법으로 바꿔보자.

① 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다.
② 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다.
③ 괄호를 제거한다.

<스택을 사용한 후위표기식으로 변환>

⑴ 왼쪽괄호를 만나면 무시하고 다음 문자를 읽는다.
⑵ 피연산자를 만나면 출력한다.
⑶ 연산자를 만나면 스택에 push한다.
⑷ 오른쪽괄호를 만나면 스택을 pop하여 출력한다.
⑸ 수식이 끝나면, 스택이 공백이 될 때까지 pop하여 출력한다.

[코드]