[TIL][Krafton Jungle] 2주차 - (1) : 트리 & 그래프 알고리즘

새로운 2주차를 맞이하고 조원이 변경됐다.

 

---

2주차는 조원들과 매일 1개의 키워드를 정해 공부한 뒤 익일 오전에 발표하는 형식으로 공부하기로 정했다.

 

---

그래프 자료 구조

---

그래프 알고리즘은 코딩 테스트에서 주로 사용되는 풀이 방식의 알고리즘으로, 매우 중요한 만큼 어렵기도 하다.

 

팀 코어타임 발표를 위해서라도 열심히 준비해보자

 

 

구현 방법

 그래프 G = (V,E)를 표현하는 두가지의 표준 방법이 있다.

1. 인접 리스트의 집합

2. 인접 행렬

 

먼저 인접 리스트(Adjacency List)의 집합으로 그래프를 표현하는 방식

이 방식은 낮은 밀도의 그래프에 선호된다.

메모리 양이 세타(V+E) 여서 데이터 사용량측에서 매우 바람직한 특성을 가진다.

 

 

인접 행렬(Adjacency Matrix) : 2차원의 배열을 사용하는 방식

이 방식은 높은 밀도, 즉 간선이 매우 조밀하게 연결되어 있는 경우에 더 선호된다.

 

특히 간선의 가중치가 있는 경우, 배열에 가중치를 저장하면 되므로 비용을 아는데 O(1)의 시간이 소요된다.

 

 

다양한 그래프 알고리즘

 

1. 다익스트라 최단 경로 알고리즘

이 알고리즘은 인접 리스트를 이용하는 방식으로,

노드의 개수가 V일 때 V개의 인접 리스트를 만들어 각 노드의 연결 성분을 저장한다.

최단 경로를 찾아야 하는 문제에서, 노드와 간선의 개수가 많은 경우에는 우선순위 큐와 함께 사용된다.

 

 

2. 크루스칼 알고리즘

이 알고리즘은 최소 신장 트리 알고리즘이라고도 하며,

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘이다.

 

가장 적은 비용으로 모든 노드를 연결할 수 있다.

 

알고리즘 순서는 다음과 같다.

 

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하며 현재 간선이 사이클을 발생시키는지 확인한다.

 2-1 . 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 시킨다.

 2-2 . 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다.

3. 모든 간선에 대하여 2.번의 과정을 반복한다

 

 

3. 너비 우선 탐색 (BFS)

시작 노드를 선정하고 해당 노드의 인접점을 모두 방문한 뒤 방문한 노드들의 자식 노드들을 방문하는 탐색방법

task를 기억하는 방식으로 탐색을 하므로 queue 자료구조를 사용한다.

노드들을 queue에 넣고 pop하는 방식으로 방문을 진행한다.

---

 

이진 탐색 트리 알고리즘 (BaekJun - #5639 : 이진 검색 트리)

이진 탐색 트리의 전위 순회 결과를 보고 

후위 순회 결과를 출력하도록 하는 문제였다.

 

2시간동안 고민했는데 도저히 못풀겠어서 구글링을 했다.

 

import sys

treeList = []

while True:
    try:
        treeList.append(int(sys.stdin.readline().rstrip()))
    except:
        break

def solve(start,end):
    if start > end:
        return
    mid = end + 1
    for i in range(start+1,end+1):
        if treeList[start] < treeList[i]:
            mid = i
            break
    solve(start+1,mid-1)
    solve(mid,end)
    print(treeList[start])


solve(0,len(treeList)-1)

전위 순회는 맨처음 root가 출력되고

그 이후 root보다 작은값인 트리의 왼쪽 서브트리가 전부 출력,

마지막으로 root 오른쪽 서브트리가 출력되는 것을 이용한다.

 

그리고 try - except 문으로 예외적인 key출력을 감지하여 input 종료를 통제했다.

 

메인 알고리즘인 solve 함수의 로직은 다음과 같다.

 

트리의 범위를 시작과 끝의 index로 받아

 

왼쪽 서브 트리를 받아 출력하고

백트래킹으로 서브트리의 오른쪽을 출력

그리고 서브트리의 루트를 출력하는 방식으로 알고리즘을 구성했다.

 

---

백준 문제 풀이를 위한 Python 문법 정리

---

딕셔너리

key - value 쌍으로 이루어진 자료구조

 

예를 들면

graph = {1:[2,3,4],2:[1,3],3:[2,1],4:[1]}

이런 딕셔너리가 있다면

graph[key] = key의 value

ex) graph[1] = [2,3,4]

위와 같은 형식으로 출력되는 것을 딕셔너리라 한다. 

 

딕셔너리의 데이터는 다음과 같이 for문을 활용하여 출력될 수 있다.

>>> for k in a.keys():
...         print(k)
...
name
phone
birth

 

딕셔너리 Key 로 Value 값 얻기 - get

get(x) 함수는 x라는 Key에 대응되는 Value를 리턴한다. 앞에서 살펴보았듯이 a.get('name')은 a['name']을 사용했을 때와 동일한 결괏값을 리턴한다.

다만, 딕셔너리에 존재하지 않는 키로 값을 가져오려고 할 경우, a['nokey'] 방식은 오류를 발생시키고 a.get('nokey') 방식은 None을 리턴한다는 차이가 있다.