알고리즘 스터디 8일차

에이블 스쿨에서 진행하는 미니프로젝트가 끝나고 다시 시작하는 알고리즘 스터디. 밀린 만큼 더 힘내서 하자 화이팅!

 

목차

1. 그래프의 표현

2. 유니온 파인드 (Union-Find)

3. 위상 정렬 (Topological sort)

4. 다익스트라 (Dijkstra)

 

 

출처

Do it! 알고리즘 코딩테스트 with Python

 

 

1. 그래프의 표현

1.1 에지 리스트

출발 노드, 도착 노드를 저장하여 에지를 표현 (혹은 가중치도 추가)

 

가중치 없는 그래프의 에지 리스트

만약 방향이 없는 그래프라면 [1,2] = [2,1]

가중치 있는 그래프의 에지 리스트

가중치 행만 추가됨

1.2 인접 행렬

2차원 배열을 자료구조로 이용하여 그래프를 표현 (노드가 5개인 그래프는 5x5)

 

가중치 없는 그래프의 인접 행렬

가중치가 없기 때문에 1을 저장

가중치 있는 그래프의 인접 행렬

가중치를 해당 배열에 적

 

1.3 인접 리스트

행렬 관련 문제는 전부 인접 리스트를 사용할 수 있다 (매우 중요함)

 

가중치 없는 그래프 인접 리스트

3->4 노드의 경우 A[3].add(4) 와 같이 저장

 

가중치 있는 그래프 인접 리스트

3->4 노드의 경우 A[3].add(NewNode(4,3)) 와 같이 저장

인접 리스트는 그래프 구현은 복잡하지만 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나고 매모리 초과도 발생하지 않음.(공간 효율이 좋기 때문)

따라서 인접 리스트를 활용한 그래프 구현에 익숙해져야 함.

 

 

2. 유니온 파인드

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산

두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산 (자신의 대표노드를 찾아줌)

union시 대표노드 지정됨, 대표 노드가 아닌 노드끼리 union시 find로 대표 노드를 찾아 연결

경로 압축 : 실제 그래프에서 여러 노드를 거쳐야 하는 경로에서 그래프를 변형해 더 짧은 경로로 갈 수 있도록 함으로써 시간 복잡도를 효과적으로 줄이는 방법

 

 

3. 위상 정렬

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

시간 복잡도 : O(V+E)

자기 자신을 가리키는 에지의 개수로 집입 차수 배열을 만듦

진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장하는 과

따라서 위상 정렬 배열은 1 2 3 4 5 이다.

 

4. 다익스트라

그래프에서 최단 거리를 구하는 알고리즘

출발 노드와 모든 노드간의 최단거리 탐색

에지는 모두 양수

시간 복잡도 : O(ElogV)

인접 리스트로 그래프 구현

최단 거리 배열 초기화하기

값이 가장 작은 노드 고르기

최단 거리 배열 업데이트하기

과정 3~4를 반복해 최단 거리 배열 완성하기