그래프란
- 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조
- 그래프를 구현하는 방식은 두 가지가 있다.
- 알고리즘 문제에서 서로 다른 개체가 연결되어 있다.고 하면, 가장 먼저 그래프 알고리즘을 떠올리기.
1. 연결 리스트를 이용한 인접 리스트 방식
- 간선의 개수(O(E)) 만큼 메모리가 필요로 하지만 인접 행렬에 비해서 O(V)의 시간복잡도를 가진다.
- -> E(Edge) : 그래프 안에 있는 모든 간선들의 집합 , V(Vertax) : 그래프 내에 있는 모든 노드들의 집합
2. 2차원 배열을 이용하는 인접 행렬 방식
- 메모리 공간을 많이(O(V^2)) 필요로 하는 대신 노드간 간선의 비용을 구하는 시간이 O(1)의 시간복잡도를 가진다.
트리란
- 그래프의 일종으로 노드(정보의 단위)와 노드 사이에 하나의 간선만 존재하는 계층형 자료구조.
그래프와 트리 차이점
|
그래프 |
트리 |
방향성 |
방향 그래프 혹은 무방향 그래프 |
방향 그래프 (전통 수학에서는 무방향으로 간주) |
순환성 |
순환 및 비순환 |
비순환 |
루트 노드 존재 여부 |
루트 노드가 없음 |
루트 노드가 존재 |
노드간 관계성 |
부무와 자식 관계가 없음 |
부모와 자식 관계 |
모델의 종류 |
네트워크 모델 |
계층 모델 |
1. 서로소 집합
- 공통 원소가 없는 두 집합
- EX) {1,2} 와 {3,4} 두 집합은 서로소 집합이다. -> {1,2} 와 {2,3} 두 집합은 2를 공통원소로 가지므로 서로소 집합이 아니다.
서로소 집합 자료구조 -> Union-Find 자료구조
- 서로소 집합 자료구조는 몇몇 그래프 알고리즘에서 매우 중요하게 사용됨
- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조
- 두 집합이 서로소 관계인지 확인 -> 각 집합이 어떤 원소를 공통으로 가지고 있는지 확인
- Union-Find 자료구조라고 불리며, 서로소 집합 자료구조는 Union 과 Find 2가지 연산으로 조작한다.
- Union : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산
- Find : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산
- 트리 자료구조를 이용하여 집합을 표현
- 서로소 집합 정보(합집합 연산)가 주어졌을 때 트리 자료구조를 이용해서 집합을 표현하는 서로소 집합 계산 알고리즘
- Union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 -> A가 속한 집합과 B가 속한 집합을 합집합으로 생성
- A와 B의 루트 노드 A', B'를 찾음
- A'를 B'의 부모 노드로 설정(B'가 A'를 가르키도록 한다.)
- 모든 Union(합집합) 연산을 처리할 때까지 1번 과정을 반복
- 실제로 구현할 때 A와 B 중에서 더 번호가 작은 원소가 부모 노드가 되도록 구현하는 경우가 많으므로, 그러한 구현 방식을 따름 - EX) A가 1이고, B가 3이면 B가 A를 가르키도록(A를 B의 부모 노드로) 설정 -> B와 A를 연결하는 형태의 그래프
예시로 알고리즘 동작 방식 이해하기
전체 집합 : {1, 2, 3, 4, 5, 6}
주어진 연산: Union 1, 4 / Union 2, 3 / Union 2, 4 / Union 5, 6
- 4가지 Union -> 두 원소가 속한 집합들을 묶어서 한 집합으로 묶음
- Union 연산의 각 원소는 그래프의 노드로, '같은 집합에 속한다' 정보를 담은 Union 연산들은 간선으로 표현
- 6개의 노드와 4개의 간선이 존재하는 그래프로 바꾸어 생각 가능하다.
- 4 -> 1, 3 -> 2, 4 -> 2(이 때 4가 속한 집합({1,4}) 와 2가 속한 집합({2.3}) 을 합친 집합인 {1,2,3,4}가 한 집합이 된다.
- 6 -> 5 연산으로 인해 {5,6} 집합이 생기며 모든 연산 후에는 {1,2,3,4} 와 {5,6} 2가지의 집합이 생긴다.
1. Union 1, 4 연산
2. Union 2, 3 연산
3. Union 2, 4 연산
4. Union 5, 6 연산
5. 특정 원소가 속한 집합 찾기
- 루트 노드가 아니라면 -> 루트 노드를 찾을 때까지 재귀적으로 호출해서 루트 노드를 찾는다 -> 루트 노드의 집합이 현재 원소가 속한 집합
6. 두 원소가 속한 집합 합치기
- 두 원소를 위의 메소드로 속한 집합을 찾고, 두 집합 중에서 큰 원소의 루트 노드를 작은 원소로 바꾼다.
알고리즘 문제 추천
- 집합의 표현 (골드 5)
2. 신장 트리 (Spanning Tree)
- 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프
- 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다.
최소 신장 트리 알고리즘
- 신장 트리 중에서 최소 비용(최소 시간복잡도)으로 만들 수 있는 신장 트리를 찾는 알고리즘
그리디(탐욕) 알고리즘
- 매순간마다 최선의 선택을 하는 방법이다.
- 장점 : 빠르다.
- 단점 : 항상 최적화 되지 않고, 구한 답이 최적이 아닐 가능성이 존재한다.
1. 프림(Prim's) 알고리즘
- 루트 노드부터 시작하여, 노드마다 최소 비용인 간선만을 골라서 신장 트리를 찾는 알고리즘
2. 크루스칼(Kruskal) 알고리즘
- 가장 대표적인 최소 신장 트리 알고리즘이다.
- 가장 적은 비용으로 모든 노드를 연결할 수 있음
- 동작 원리
- 간선 데이터를 비용에 따라 오름차순으로 정렬
- 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
- 모든 간선에 대하여 2번 과정을 반복
- 시간 복잡도 : 알고리즘에서 시간이 가장 오래 걸리는 부분이 간선 정렬이므로, 간선의 개수가 E개일 때 O(ElogE)
동작 원리
- 초기 단계에 모든 간선 정보만 따로 빼내어 오름차순 정렬.
- 오름차순대로 간선을 이어가는데(Union 연산) 만약 사이클이 생기면(양쪽 원소가 이미 동일한 집합이면) 그 다음 큰 간선으로 간다.
- 모든 간선을 다하면 종료 후 간선의 값을 다 더한다.
알고리즘 문제 추천
- 최소 스패닝 트리 (골드 4)
- 멀티탭 스케줄링 (골드 1)
위상 정렬
- 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘
- 그래프 상에 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있음.
- 정렬 알고리즘의 일종이다.
동작 원리
- 진입차수가 0인 노드를 큐에 넣기.
- 큐가 빌 때까지 다음의 과정을 반복.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거
- 새롭게 진입차수가 0이 된 노드를 큐에 넣기
- 큐가 빌 때까지 원소를 계속 꺼내서 처리하는 과정을 반복하고, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 가능
- 사이클이 존재하는 경우 사이클에 포함되어 있는 원소 중에서 어떠한 원소도 큐에 들어가지 못하기 때문이다.
- 단, 기본적으로 위상 정렬 문제에서는 사이클이 발생하지 않는다고 명시하는 경우가 더 많아, 예시에서는 사이클을 고려하지 않음.
- 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
예시
- 1 -> 2 , 1 -> 5, 2 -> 3, 2 -> 6, 3 -> 4, 4 -> 7, 5 -> 6, 6 -> 4 라고 가정해보자.
- 처음 노드 1은 진입차수가 0이므로 바로 큐에 삽입.
- 큐에 있는 노드 1을 꺼내고, 노드 1과 연결된 간선을 제거.
- 이후 노드 2와 노드 5의 진입차수가 0이 되므로, 2와 5를 큐에 삽입
- 큐에 있는 노드 2를 꺼내고, 노드 2와 연결된 간선을 제거.
- 진입차수가 0이 된 노드 3을 큐에 넣고, 다음 순서인 노드 5를 꺼내고, 노드 5와 연결된 간선을 제거.
- 진입차수가 0이 된 노드 6을 큐에 넣고, 노드 3을 꺼내고, 노드 3과 연결된 간선을 제거.
- 진입차수 0이 되는 노드가 없으므로, 노드 6을 꺼내고, 노드 4를 넣어준다.
- 노드 4의 간선을 제거 하고, 노드 7을 큐에 넣고, 노드 7을 꺼낸다.
- 순서가 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7 로 결과가 나온다.
알고리즘 문제 추천
- 줄 세우기 (골드 3)
참고 자료
https://scshim.tistory.com/414
댓글