안녕하세요 공공돌🧸 입니다.
알고리즘 문제들을 풀다보면 나오는 한번 정리 해보려 합니다.
순서는 아래와 같은 알고리즘 문제들을 Swift언어로 풀면서 올려보도록 하겠습니다.
그리디, 그래프이론, DFS, BFS, 트리순회, 완전탐색, 백트래킹, 비트마스킹, 라인스위핑, 투포인터, LIS, 이분탐색, DP, 최단거리, 펜윅트리
그리디(Greedy) 알고리즘이란?
그리디 알고리즘은 탐욕 알고리즘이라고도 불리며, " 매 선택에서 지금 이 순간 가장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지고 있는 알고리즘 설계법 입니다.
한마디로 설명한다면 유명한 마시멜로 실험에 비유할 수 있습니다. 그리디 알고리즘을 사용한다는 것은 마시멜로를 먹는 것 이지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못하는 것 처럼 그리디 알고리즘은 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻지만 현재의 선택이 나중에 미칠 영향을 고려하지 않기 때문에, 항상 최적해를 보장하는 것은 아닙니다.
정당성
그리디 알고리즘이 문제의 최적해를 보장하는가?를 판단할때 기준은 아래와 같이 정할 수 있습니다.
- 탐욕적 선택 속성(greedy choice property)
탐욕적 선택이 항상 최적해를 보장해야 합니다.
- 최적의 부분 구조(potimal substructure property)
하나의 선택을 하면 풀어야 할 하위 문제가 남아있어야 합니다 (Top-Down 방식)
대표적인 그리디 알고리즘 종류
| Algorithm | 목적 | 설명 | |
| 프림(Prim) | N개의 노드에 대한 최소 신장 트리(MST)를 찾는다. | 서브트리를 확장하면서 MST를 찾는다. | 그래프 |
| 크리스컬(Kruskal) | N개의 노드에 대한 최소 신장 트리(MST)를 찾는다. | 사이클이 없는 서브 그래프는 확장하면서 MST를 찾는다. | 그래프 |
| 다익스트라(Dijkstra) | 주어진 정점에서 다른 정점들에 대한 최단 경로를 찾는다. | 주어진 정점에서 가장 가까운 정점을 찾고, 그 다음을 정점을 반복해서 찾는다. | 그래프 |
| 허프만(Huffman) tree & code | 문서의 압축을 위해 문자들의 빈도수에 따라 코드 값을 부여한다. | 출현 빈도가 낮은 문자부터 선택해서 이진 트리를 완성하고 코드 값을 부여한다. | 문자열 |
그래프와 트리(G = Graph , T = Tree)
먼저 그래프와 트리에 대해서 정리를 하고 가겠습니다.
그래프란?
그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조
이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조
[ 특징 ]
- 그래프는 순환 혹은 비순환 구조를 이룬다.
- 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.
- 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.
- 2개 이상의 경로가 가능하다.(무방향, 방향, 양방향 가능)
- 그래프는 네트워크 모델이다.
트리란?
트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다.
트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다.
이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다.
부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.
[ 특징 ]
- 부모-자식 관계가 존재해 레벨이 존재한다.(최상위 노드=Root)
- 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개(완전이진트리의 경우)
- 방향성이 존재하고 사이클은 존재하시 않는다.(비순환)
- 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다.
최소 신장 트리(MTS , Minimum Spanning Tree)
최소 신장 트리 (MTS , Minimum Spanning Tree)란 주어진 가중치 그래프에서 사이클 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리를 말합니다.
[ 동작 원리 ]
- 간선의 가중치의 합이 최소이어야 한다.
- 반드시 (n - 1)개의 간선만 사용해야 한다.
- 사이클이 포함되어서는 안 된다.
프림 알고리즘(Prim Algorithm)
프림 알고리즘(Prim Algorithm) 이란 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장하는 기법을 말합니다.
Prim Algorithm 동작
프림 알고리즘은 매 순간 최선의 조건을 선택하는 그리디 알고리즘을 바탕에 둡니다.
즉, 탐색 정점에 대해 연결된 인접 정점들 중 비용이 가장 적은 간선으로 연결된 정점을 선택합니다.
1. 시작 단계에서는시작 노드만이 MST 집합에 속합니다.
2. 트리 집합에 속한 정점들과 인접한 정점들 중 가장 낮은 가중치의 간선과 연결된 정점에 대해 간선과 정점을 MST 트리 집합에 넣습니다.사이클이 생기는 것을 막기 위해 연결된 정점이 이미 트리가 속한다면 그 다음 순서를 넣습니다.
3. 2번 과정을 MST 집합의 원소 개수가 그래프의 정점의 개수가 될 때까지 반복합니다.
위 가중치 그래프로 최소 신장 트리를 프림 알고리즘을 통해서 구해보겠습니다.
시작 정점 = 1
시작 정점 1와 인접한 노드 중 가장 가중치가 낮은 노드는 3과 연결되어 있습니다.
| Nodes | [ 1 , 3 ] |
| Edges | [ 1 3 ] |
1 3 과 인접한 노드 중 가장 가중치가 낮은 노드는 4 입니다. 집합에 4를 넣고 3 4 가중치를 더해줍니다.
| Nodes | [ 1 , 3 , 4 ] |
| Edges | [ 1 3 , 3 4 ] |
1 , 3 , 4 와 인접한 노드 중 가장 가중치가 낮은 노드는 5 입니다. 집합에 5를 넣고 3 5 가중치를 더해줍니다.
| Nodes | [ 1 , 3 , 4 , 5 ] |
| Edges | [ 1 3 , 3 4 , 3 5 ] |
1 , 3 , 4 , 5 와 인접한 노드 중 가장 가중치가 낮은 노드는 6 입니다. 집합에 6을 넣고 5 6 가중치를 더해줍니다.
| Nodes | [ 1 , 3 , 4 , 5 , 6 ] |
| Edges | [ 1 3 , 3 4 , 3 5 , 5 6 ] |
1 , 3 , 4 , 5 , 6 와 인접한 노드 중 가장 가중치가 낮은 노드는 2 입니다. 집합에 2를 넣고 6 2 가중치를 더해줍니다.
| Nodes | [ 1 , 3 , 4 , 5 , 6 , 2 ] |
| Edges | [ 1 3 , 3 4 , 3 5 , 5 6 , 6 2 ] |
트리의 집합에 속한 원소의 개수가 N이 되었으므로 탐색을 중단합니다.
탐색 결과 최소 신장 트리 구축의 비용은 15으로 확인되었습니다.
| Nodes | [ 1 , 3 , 4 , 5 , 6 , 2 ] |
| Edges | [ 1 3 , 3 4 , 3 5 , 5 6 , 6 2 ] |
| Cost | 15 |
Prim Algorithm 구현 1
struct Edges {
var destination: Int
var cost: Int
}
func Dist(_ tree: [Edges], dist: inout [Int?]) -> [Edges] {
for edges in tree {
if let d = dist[edges.destination] {
if d > edges.cost {
dist[edges.destination] = edges.cost
}
} else {
dist[edges.destination] = edges.cost
}
}
return tree
}
func prim(_ n: Int, _ costs: [[Int]]) -> Int {
// 최소 비용을 저장할 배열
var dist = [Int?](repeating: nil, count: n)
// 방문 체크 배열
var visit = [Bool](repeating: false, count: n)
// 방문한 노드의 개수
var visitCount = 0
// 현재 방문 노드를 저장 0에서 시작
var now = 0
// 최소비용을 저장한다.
var minimumCost = 0
//배열의 인덱스가 해당 노드가 되고 연결된 선을 저장합니다.
var tree = [[Edges]](repeating: [], count: n)
// 선의 양 끝을 둘다 저장
for cost in costs {
tree[cost[0]].append(Edges(destination: cost[1], cost: cost[2]))
tree[cost[1]].append(Edges(destination: cost[0], cost: cost[2]))
}
visit[now] = true
visitCount += 1
// 탐색
while visitCount < n {
let tree = Dist(tree[now], dist: &dist)
// 최소값 구하기
var minCost: Int? = nil
for i in 0..<n {
guard !visit[i], let d = dist[i] else {continue}
if let min = minCost {
if min > d {
minCost = d
now = i
}
} else {
minCost = d
now = i
}
}
visit[now] = true
visitCount += 1
minimumCost += minCost!
}
return minimumCost
}
// 입력: ( Int: 노드의 개수, [[Int]]: [[출발 노드, 끝 노드, 비용]] )
// 1 - 6 까지 = 0 - 5 까지
let output = prim(6, [[0, 1, 7], [0, 3, 8], [0, 2, 1], [3, 2, 2], [3, 4, 10], [4, 2, 4], [4, 5, 3], [5, 2, 9], [5, 1, 5], [1, 2, 6]])
print(output)
Prim Algorithm 구현 2
밑에 글에서 가져온 구현인데 나중에 코드해석을 하기위해...‼️ 🤪
https://codereview.stackexchange.com/questions/215897/swift-prims-algorithm
func prims (_ matrix : [[Int]]) {
var selected = 0
var selectedSoFar = Set<Int>()
selectedSoFar.insert( (matrix[selected].enumerated().min{ $0.element < $1.element }?.offset)! )
while selectedSoFar.count < matrix.count {
var minValue = Int.max
var minIndex = selected
var initialRow = 0
for row in selectedSoFar {
let candidateMin = matrix[row].enumerated().filter{$0.element > 0 && !selectedSoFar.contains($0.offset) }.min{ $0.element < $1.element }
if (minValue > candidateMin?.element ?? Int.max ) {
minValue = candidateMin?.element ?? Int.max
minIndex = (candidateMin?.offset) ?? 0
initialRow = row
}
}
print ("edge value \(minValue) with \(initialRow) to \(minIndex)")
selectedSoFar.insert(minIndex)
selected = (minValue)
}
}
let input = [[0,9,75,0,0],[9,0,95,19,42],[75,95,0,51,66],[0,19,51,0,31],[0,42,66,31,0]]
prims(input)크리스컬, 다익스트라, 허프만은 2편에 따로 쓰도록 하겠습니다 !
