Krafton Jungle Third

모기·2025년 3월 31일

Study.Jungle

목록 보기

4/12

public string DevelopmentDiary(Knowledge knowledge) {
	if (knowledge != null) {
		return "level up"
    } else {
    	return "level down"
    }
}

컴퓨터 과학

1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다.

최신 시스템은 네트워크에 의해 다른 시스템과 연결되기도 한다. 개별 시스템의 관점에서 볼 때 네트워크는 또 다른 입출력 장치이다.

hello 프로그램을 원격으로 실행하는 5단계

hello 스트링을 telnet 클라이언트에 입력하고 엔터키를 누른다.
클라이언트 프로그램은 이 스트링을 telnet 서버로 보낸다.
telnet 서버가 네트워크에서 스트링을 받은 후 원격 쉘 프로그램에 이들을 전달한다.
telnet 서버는 네트워크를 거쳐 출력 스트링을 telnet 클라이언트로 전달한다.
클라이언트 프로그램은 출력 스트링을 자신의 로컬 터미널에 표시한다.

1.9 중요한 주제들

시스템 - 응용프로그램의 실행이라는 궁극의 목적을 달성하기 위해 하드웨어와 소프트웨어가 서로 연결된 것

1. Adamhl의 법칙

시스템의 한 부분의 성능을 개선할 때 전체 시스템 성능에 대한 효과를 계산하는 방식
=> 해당 부분이 얼마나 중요한가, 얼마나 빨라졌는가를 확인함.

T old = 응용프로그램을 실행하는 시간
a = 특정 부분이 소모하는 시간의 비율
k = 개선하려는 성능의 배수

전체 실행시간 = 예전 시간 - 특정 부분이 예전에 소모한 시간 + 특정 부분이 새로 소모하는 시간

T new = T old - a*T old + (a*T old)/k

S = 개선된 속도
= 1/((1 - a) + a/k)

note. 시스템의 60%에 해당하는 부분을 시간이 거의 걸리지 않는 지점까지 속도를 올려도 속도개선율은 2.5배이다.

2. 동시성과 병렬성

동시성(concurrency): 다수의 동시에 벌어지는 일을 갖는 시스템에 관한 일반적인 개념
병렬성(parallelism): 동시성을 사용해서 시스템을 보다 빠르게 동작하도록 하는 것

쓰레드 수준 동시성

쓰레드를 이용하면 한 개의 프로세스 내에서 실행되는 다수의 제어흐름을 가짐.

단일 프로세서 시스템 - 한 개의 프로세서가 다수의 태스크들 간에 전환을 함.
멀티 프로세서 시스템 - 시스템이 여러 개의 프로세서를 가지고 하나의 운영체제 커널의 제어하에 동작

멀티쓰레딩(하이퍼 쓰레딩) - 하나의 CPU가 여러 개의 CPU인 것처럼 여러 개의 제어 흐름을 실행할 수 있게 해주는 기술

멀티 프로세싱의 이용이 시스템 성능을 개선하는 방법

다수의 태스크를 실행할 때 동시성을 시뮬레이션할 필요를 줄여줌.
멀티프로세싱으로 한 개의 응용프로그램을 빠르게 실행할 수 있지만 프로그램이 병렬로 효율적으로 실행할 수 있는 멀티쓰레드의 형태로 표현되었을 때에만 가능함.

인스트럭션 수준 병렬성

여러 개의 인스트럭션을 한 번에 실행하는 것

파이프 라이닝

하나의 인스트럭션을 실행하기 위해 요구되는 일들을 여러 단계로 나누고
프로세서 하드웨어가 일련의 단계로 구성되어 이들 단계를 하나씩 각각 수행하는 것
ex) 빨래
파이프 라이닝이 아닌 경우
세탁 - 건조 - 정리 -> 세탁 - 건조 - 정리 ->

파이프 라이닝인 경우
세탁 - 건조 - 정리 ->
건조 - 정리 - 세탁 ->
정리 - 세탁 - 건조 ->

슈퍼스케일러 - 사이클 당 한 개 이상의 인스트럭션을 실행할 수 있는 프로세서

-싱글 인스트럭션 다중 데이터 병렬성 (SIMD 병렬성)

한 개의 인스트럭션이 병렬로 다수의 연산을 수행

3. 컴퓨터 시스템에서의 추상화의 중요성

인스트럭션 집합 구조 - 실제 프로세서 하드웨어의 추상화 제공
가상머신 - 운영체제, 프로세서, 프로그램 모두를 포함하는 컴퓨터 전체의 추상화 제공

자료구조와 알고리즘

그래프의 종류와 표현 방식

트리 구조

    A
   / \
  B   C

Node와 Edge로 표현된 자료 구조. 가장 위쪽에 있는 노드를 root 노드라고 하고, 가장 아래에 있는 노드를 leaf 노드라고 함. (가지가 없다는 의미) 그래프에 속하며 사이클을 형성하지 않음.

부모 노드: 어떤 노드와 가지가 연결되었을 때 위쪽에 있는 노드로 노드의 부모는 하나 뿐임.
자식 노드: 어떤 노드와 가지가 연결되었을 때 아래쪽 노드를 자식이라고 함. 노드는 자식을 몇 개라도 가지 수 있음.
차수: 각 노드가 갖는 자식의 수

순회(루트노드를 언제 방문하는 지에 따라)
--전위 순회(preorder): 루트 노드를 먼저 방문함
--중위 순회(inorder): 루트 노드를 중간에 방문함
--후위 순회(postorder): 루트 노드를 마지막에 방문함

이진트리: 자식을 최대 둘까지 갖는 트리(왼쪽, 오른쪽 자식)
완전이진트리: 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리
이진검색트리: 루트노트를 기준으로 왼쪽 자식은 루트노드보다 작은 값, 오른쪽 자식은 루트노드보다 큰 값임.

그래프 구조

A - B
|   |
C - D

정점(Vertex)와 간선(Edge)를 갖는 자료 구조
간선은 양방향일 수도 있고, 단방향일 수도 있음
간선에 가중치가 있을 수도 있고, 없을 수도 있음

BFS/DFS

A-B-C-D
| |  
E-F-G-H
|
I-J

BFS(너비 우선 탐색)
시작 정점을 기준으로 가까이 있는 정점들을 먼저 탐색하는 알고리즘
일반적으로 Queue를 활용하여 구현
위 그래프에서 A가 출발점이라고 하면

while Queue

----------
deque:
enque: A
[A]
----------
deque: A
enque: B, E
[B, E]
----------
deque: B
enque: C, F
[E, C, F]
----------
deque: E
(visit 처리) enque: I 
(visit 처리X) enque: F, I
visit 처리 여부에 따라 enque가 달라짐. 처리했다고 가정하겠음.
[C, F, I]
----------
deque: C
enque: D
[F, I, D]
----------
deque: F
enque: G
[I, D, G]
----------
deque: I
enque: J
[D, G, J]
----------
deque: D
enque: 
[G, J]
----------
deque: G
enque: H
[J, H]
----------
deque: J
enque: 
[H]
----------
deque: H
enque: 
[]

탐색 종료

DFS(깊이 우선 탐색)
시작 정점을 기준으로 간선으로 연결된 정점들을 먼저 탐색하는 알고리즘
일반적으로 Stack이나 재귀 함수를 활용하여 구현
연결된 정점을 방문하므로 알고리즘을 어떻게 처리했느냐에 따라 작동 방식이 변함
여기서는 아래쪽, 오른쪽, 위쪽, 왼쪽 순으로 동작한다고 가정하겠음

while Stack
----------
pop:
push: A
[A]
----------
pop:
push: E
[A, E]
----------
pop:
push: I
[A, E, I]
----------
pop:
push: J
[A, E, I, J]
----------
pop: J
push:
[A, E, I]
----------
pop: I
push: F
[A, E, F]
----------
pop: 
push: G
[A, E, F, G]
----------
pop: 
push: H
[A, E, F, G, H]
----------
pop: H
push: 
[A, E, F, G]
----------
pop: G
push: B
[A, E, F, B, C]
----------
pop: 
push: C 
[A, E, F, B, C]
----------
pop: 
push: C 
[A, E, F, B, D]

모두 pop한 뒤
탐색 종료

위상 정렬
방향 그래프에서 진입차수가 0일 때 탐색하는 알고리즘
방향 그래프: 간선에 의해 연결되어 있지만, 한 정점에서 다른 정점으로만 갈 수 있음.
진입차수: 외부 정점으로부터 들어오는 간선의 수

A -> B -> C -> D
     ^
     |
     E

와 같은 그래프가 있을 때
진입 차수는 다음과 같음

A(0) -> B(2) -> C(1) -> D(1)
        ^
        |
        E(0)

따라서 A와 E부터 출발
Queue를 활용하여 BFS탐색하듯이 하나 진입차수를 수정하면서 진행해야함.
즉, 진입 차수가 0일 때 Queue에 enque 가능
괄호 안은 진입차수

Queue [A, E]

A(0) -> B(2) -> C(1) -> D(1)
        ^
        |
        E(0)
------------------------------
Queue [E]

A(0) -> B(1) -> C(1) -> D(1)
        ^
        |
        E(0)
------------------------------
Queue [B]

A(0) -> B(0) -> C(1) -> D(1)
        ^
        |
        E(0)
------------------------------

B-Tree

자식 노드의 최대 숫자가 2보다 큰 트리
최대 자식(M)에 따라 M차 트리라고 불리며
4차 트리에 대표적으로 2-3-4트리가 있음.

데이터의 삽입
-leaf 노드에서 삽입을 한다.
-노드가 넘친다면 가운데 키를 기준으로 좌우로 분할하고 가운데는 승진한다.

데이터의 삭제
-항상 leaf 노드에서 삭제한다.
-삭제 후 최소 key수보다 작아진다면 재조정한다.
-1. key수의 여유가 있는 형제한테 지원 받기
-2. 1번이 불가능하다면 부모의 지원받고 형제랑 합치기
-3. 2번 후 부모에게 문제가 생긴다면 다시 조정

선택된 데이터가 중간 노드일 경우)
leaf노드랑 위치바꾸고 지운다.
삭제할 데이터의 선임자(작은 놈 중에 큰 놈) 혹은 후임자(큰 놈 중에 작은놈)

트라이(Trie)
다익스트라

최단 거리를 찾는 알고리즘
1. 진입한 정점에서 진입 가능한 정점으로 가중치를 더하여 최솟값으로 업데이트 한다.
2. 최소 비용을 가지는 정점으로 진입한다.
3. 진입했던 정점은 표시를 한다.

각 정점의 최소 비용을 고려하므로 보통 우선순위큐, 힙을 사용한다.
예시에 표현한 자료 구조는 우선순위 큐이며 우선순위큐에는 출발점이 들어간다.
화살표의 ()안에는 가중치가 있고, 각 점의 []에는 비용이 있으며, 진입했던 점은 *로 표시하겠다.

1.
Priority Queue
[A[0]]

A[0] ->(4) B[0] ->(3) C[0] ->(1) D[0]
  ↘(1)                 ↑(1)  ↗(3)
     E[0]     ->(4)     F[0]
     
2.
Now = A[0]
PQ = [E[1], B[4]]

A*[0] ->(4) B[4] ->(3) C[0] ->(1) D[0]
  ↘(1)                 ↑(1)  ↗(3)
       E[1]  ->(4)     F[0]
       
3.
Now = E[1]
PQ = [B[4], F[5]]

A*[0] ->(4) B[4] ->(3) C[0] ->(1) D[0]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)    F[5]

4.
Now = B[4]
PQ = [F[5], C[7]]

A*[0] ->(4) B*[4] ->(3) C[7] ->(1) D[0]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)    F[5]
       
5.
Now = F[5]
PQ = [C[6], C[7], D[8]]

A*[0] ->(4) B*[4] ->(3) C[6] ->(1) D[8]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)   F*[5]
       
       
6.
Now = C[6]
PQ = [C[7], D[7], D[8]]

A*[0] ->(4) B*[4] ->(3) C*[6] ->(1) D[7]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)   F*[5]

7.
Now = C[7]
PQ = [D[7], D[8]]

A*[0] ->(4) B*[4] ->(3) C*[6] ->(1) D[7]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)   F*[5]
       
8.
Now = D[7]
PQ = [D[8]]

A*[0] ->(4) B*[4] ->(3) C*[6] ->(1) D*[7]
  ↘(1)                 ↑(1)  ↗(3)
       E*[1]  ->(4)   F*[5]
       
종료

꼭 이렇게 그래프를 다 탐색하지는 않는다.

플로이드 워셜
그래프의 모든 최단 거리를 찾는 알고리즘이다.
아직 문제를 접해본 적은 없지만
시간복잡도가 무려 O(N3)이기 때문에 쓰지 않는다.

우리는 0번에서 2번으로 가는 형태에만 집중할 것이다.

2차원 배열	0	1	2	3
0	0	3	INF	INF
1	INF	0	3	1
2	INF	INF	0	INF
3	INF	INF	1	0

위와 같은 표가 있다면
그래프 모양은 다음과 같다.

0      →(3)    1

       ↙(3)    ↓(1)

2      ←(1)     3

쉬운 이해를 위해 대충 그렸다.
표에서 INF로 표시된 곳이 있다.
지금은 못간다는 의미, 혹은 영원히 못간다는 의미이다.
(Infinite의 INF)
그렇다면 현재의 표는 무슨 의미인가?
딱 한 번의 이동으로 갈 수 있는 곳을 의미한다.
현재 그래프를 보면 결국 다른 노드들을 통해서 0에서 2와 3을 갈 수 있긴 하다.
따라서 이제부터 업데이트를 해준다.

플로이드 워셜을 어디를 거쳐가느냐 위주로 업데이트를 한다.
먼저 1을 거쳐가는 경우이다.
2차원 배열[start][end]이라고 생각하고
array[0][2] = min(array[0][1][1][2], array[0][2])
array[0][3] = min(array[0][1][1][3], array[0][3])
이렇게 업데이트 하면

2차원 배열	0	1	2	3
0	0	3	6	4
1	INF	0	3	1
2	INF	INF	0	INF
3	INF	INF	1	0

위와 같이 바뀌게 된다.

2를 거쳐가는 경우는 없으니 패스
3을 거쳐 가는 경우는

array[0][2] = min(array[0][3][3][2], array[0][2])
array[1][2] = min(array[1][3][3][2], array[1][2])
이렇게 업데이트 하면

2차원 배열	0	1	2	3
0	0	3	5	4
1	INF	0	2	1
2	INF	INF	0	INF
3	INF	INF	1	0

최소 신장 트리
간선 옆의 괄호는 가중치이다.

A-(2)B-(4)C-(1)D
|(1) |(3)  
E-(1)F-(2)G-(1)H
|(2) |(2)
I-(1)J

--크루스칼 알고리즘
크루스칼은 가중치가 낮은 간선들을 우선 선택한다.
간선을 골라나가는 방식이기 때문에 방문한 정점을 표시하는 방식으로는 사이클 여부를 판단하기에는 어려움이 있다.

예를 들어

A-(2)B
|(1) |(1)  
E-(2)F

위과 같은 그래프가 있을 때
가중치를 위주로 선택하면 다음과 같이 먼저 선택된다.

A    B
|(1) |(1)  
E    F

근데 이때 간선을 선택하는 기준을 방문한 정점로 하면
3가지의 경우로 나눌 수 있을 것이다.

간선의 양 끝 정점을 방문하지 않았을 때,
(이 경우에는 어려움 없이 간선을 선택할 수 있다.)
=> 두 정점을 방문한 것으로 처리
간선의 한 쪽 끝 정점이 방문한 정점일 때
(이 경우에 간선을 선택하지 않으면 트리를 만드는 것이 아마 어려울 것이다.)
=> 방문하지 않은 정점을 방문한 것으로 처리
간선의 양쪽 끝 정점이 방문한 정점일 때
(이 경우는 사이클이 될 가능성이 높아보인다.)
=> 간선을 선택하지 않음.

그러면 다시 선택한 간선을 보자

A    B
|(1) |(1)  
E    F

위에서 A, B, E, F 모두 방문한 정점임에도 불구하고 사이클을 형성하지 않았다. 따라서 A, B사이나 E, F사이의 간선이 선택이 되어야 트리를 완성할 수 있다.

그렇다면 3번 규칙을 수정해야 할까?
3. 간선의 양쪽 끝 정점이 방문한 정점일 때
=> 간선을 선택한다.

그러면 다음과 같은 일이 발생할 것이다.

A - (2) B
|(1)    |(1)  
E - (2)F

트리의 간선은 정점의 개수보다 하나 작아야 한다고 반문할 수도 있다.
그렇다면 이런 그래프는?

A - B
| \ |  
E - F

대각선의 가중치가 낮다면 순식간에 사이클을 형성할지도 모른다.
따라서 크루스칼에서는 서로소 집합(disjoint set) 및 union find를 사용한다.

좀 어려워보일 수 있겠지만 개념은 단순하다.
연결하려는 두 정점이 특정 트리에 속해있다면 해당 트리의 루트 노드를 살펴보면 된다.

A-B-C-D
| |  
E-F-G-H
| |
I-J

여기서

A-B-C-D
|   
E

이런 트리(루트 노드: A)와

  F-G-H
  |
I-J

이런 트리(루트 노드: F)가 있고, I와 E를 잇는 간선의 가중치가 낮아서 연결하려 한다.
둘의 루트 노드는 각각 A와 F이다.
루트 노드가 다르기 때문에 둘은 서로 다른 트리에 속해있다고 볼 수 있고,
둘을 연결하더라도 사이클을 형성하지 않는다는 것을 알 수 있다.

그렇다면 만약

A-B-C-D
| 	  
E-F-G-H

이런 트리가 형성됐고 (루트 노드: A) 남은 가중치가 다음과 같다고 하자.

A  -  B-C-D
|     |(1)  
E  -  F-G-H
|(2)  |(2)
I -(2)J

그러면 B와 F를 선택할 수 밖에 없다. 물론 선택하면 사이클이 형성된다.
그러나 B와 F의 루트 노드가 A로 같다는 것을 확인하면
둘은 같은 트리에 속해있다는 것을 알 수 있고, 간선은 선택되지 않는다.
트리를 하나의 집합으로 봤을 때 루트 노드가 다르다는 것은 교집합이 없다는 것을 의미한다.
그러나 루트 노드를 찾고 정하는 코드를 구현하는 것은 쉽지 않다.(적어도 나는)
따라서 set에다가 모든 노드를 넣었을 때 두 집합이 서로소이면(disjoint set)
사이클이 형성되지 않는 것을 이용하기도 한다.

그럼 본격적으로 트리 형성 과정을 들여다보자
가중치는 조금 수정했다.
최소 가중치를 사용하므로 Heap을 쓴다.
모든 간선을 Heap에 넣는다.
파이썬 튜플을 활용하여 (가중치, 정점1, 정점2)를 넣겠다.

1.
Heap
[(1, A, E), (1, E, F), (1, I, J), (2, A, B), (2, E, I), (2, F, J), (3, B, F), (3, G, H), (4, B, C), (5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>





<현재 그래프 집합>


비용: 0
2.
Heap
[(2, A, B), (2, E, I), (2, F, J), (3, B, F), (3, G, H), (4, B, C), (5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A
|  
E - F

I - J
<현재 그래프 집합>
{A, E, F}, {I, J}
비용: 3

원래 하나씩 heap pop 하는게 맞으나 공간도 없고 사이클도 형성되지 않으므로 바로 추가했다.
그 다음은 (2, A, B)이고

3.
Heap
[(2, E, I), (2, F, J), (3, B, F), (3, G, H), (4, B, C), (5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B
|  
E - F

I - J
<현재 그래프 집합>
{A, E, F, B}, {I, J}
비용: 5

그 다음은 (2, E, I)다
E에 해당하는 집합 {A, E, F, B}과 I에 해당하는 집합 {I, J}은 교집합이 없으므로

4.
Heap
[(2, F, J), (3, B, F), (3, G, H), (4, B, C), (5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B
|  
E - F
|
I - J
<현재 그래프 집합>
{A, E, F, B, I, J}
비용: 7

이제 (2, F, J) 차례인데, 보다시피 두 정점 모두 같은 집합에 속해있다.
마찬가지로 (3, B, F)도 탈락이다. 탈락이다.

5.
Heap
[(4, B, C), (5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B
|  
E - F   G - H
|
I - J
<현재 그래프 집합>
{A, E, F, B, I, J}, {G, H}
비용: 10


6.
Heap
[(5, C, D), (6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B - C
|  
E - F   G - H
|
I - J
<현재 그래프 집합>
{A, E, F, B, I, J, C}, {G, H}
비용: 14


7.
Heap
[(6, F, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B - C - D
|  
E - F   G - H
|
I - J
<현재 그래프 집합>
{A, E, F, B, I, J, C, D}, {G, H}
비용: 19


8.
Heap
[]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 간선>
A - B - C - D
|  
E - F - G - H
|
I - J
<현재 그래프 집합>
{A, E, F, B, I, J, C, D, G, H}
비용: 25

따라서 다음이 크루스칼 알고리즘을 통해 완성된 최소 신장 트리이다.

A - B - C - D
|  
E - F - G - H
|
I - J
비용: 25

--프림 알고리즘
프림은 시작 정점이 필요하다. 최소 신장 트리는 결국 모든 정점을 연결하는 트리이기 때문에 어떤 정점을 시작 정점으로 선택해도 가중치의 합은 같다. 사실 알고리즘 자체는 다익스트라와 거의 동일하다. 다만 다익스트라는 도착 정점을 찾으면 끝내고 프림은 heap이 빌 때까지 계속한다.
방문한 노드인지 확인해야 하기 때문에 Visit 배열이 필요하다.
이해를 위해 배열의 인덱스를 A ~ J로 하겠다. True는 T, False는 F이다.

1.
Visited
A B C D E F G H I J
T F F F F F F F F F
Heap
[(1, E), (2, B)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A
 
 
비용: 0


2.
Visited
A B C D E F G H I J
T F F F T F F F F F
Heap
[(1, F), (2, B), (2, I)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A
 |
 E

비용: 1


3.
Visited
A B C D E F G H I J
T F F F T T F F F F
Heap
[(2, B), (2, I), (2, J), (3, B), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A
 |
 E - F
 
 
비용: 2


4.
Visited
A B C D E F G H I J
T T F F T T F F F F
Heap
[(2, I), (2, J), (3, B), (3, F), (4, C), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B
 |
 E - F
 
 비용: 4
 
 
5.
Visited
A B C D E F G H I J
T T F F T T F F T F
Heap
[(1, J), (2, J), (3, B), (3, F), (4, C), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B
 |
 E - F
 |
 I
 
 비용: 6

사실 (1, J)와 (2, J)에서 간선에 대한 정보는 가중치 밖에 없다.
따라서 저장된 정보는 아래 그림과 다름없긴 하지만, 이해를 위해 간선을 그렸다.

<선택된 정점>
 A   B
 
 E   F
  
 I   J
 
 가중치의 합: 7

설명을 이어나가겠다.

6.
Visited
A B C D E F G H I J
T T F F T T F F T T
Heap
[(2, J), (2, F), (3, B), (3, F), (4, C), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B
 |
 E - F
 |
 I - J
 
비용: 7

(2, J)와 (2, F)에서 J, F는 이미 방문했으므로 패스한다.

7.
Visited
A B C D E F G H I J
T T F F T T F F T T
Heap
[(4, C), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B
 |
 E - F
 |
 I - J

방문한 것들은 모두 제외시킨다.

8.
Visited
A B C D E F G H I J
T T T F T T F F T T
Heap
[(5, D), (6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B - C
 |
 E - F
 |
 I - J

비용: 11


9.
Visited
A B C D E F G H I J
T T T T T T F F T T
Heap
[(6, G)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B - C - D
 |
 E - F
 |
 I - J
 
 
 비용: 16
 
 
10.
Visited
A B C D E F G H I J
T T T T T T T F T T
Heap
[(3, H)]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B - C - D
 |
 E - F - G
 |
 I - J
 
 비용: 22
 

11.
Visited
A B C D E F G H I J
T T T T T T T T T T
Heap
[]
<전체 그래프>
A-(2)B-(4)C-(5)D
|(1) |(3)  
E-(1)F-(6)G-(3)H
|(2) |(2)
I-(1)J

<선택된 정점>
 A - B - C - D
 |
 E - F - G - H
 |
 I - J

비용: 25

따라서 다음이 프림 알고리즘을 통해 완성된 최소 신장 트리이다.
다시 말하지만, 최소 신장 트리는 유일하지 않을 수도 있다.

A - B - C - D
|  
E - F - G - H
|
I - J

비용: 25

모기

안녕

이전 포스트

Krafton Jungle Second

다음 포스트