트리(Tree, 수학적 이론에서의)
아래의 그림은 정점이 13개, 간선이 12개인 트리이다.
트리의 특징
- 트리는 특정하지 않는 한 어떤 노드든지 루트노드(root node)가 될 수 있다.
- 가장 바깥쪽 노드는 리프노드(leaf node)이다.
아래 그림의 경우 11,8,3,9,10,5,12,6,4번 노드가 해당된다. - 한 노드(A)에서 다른 노드(B)로 가는 경로는 반드시 존재하며 유일하다.
- 노드개수 = 간선개수 + 1 인 공식이 항상 성립한다.
자료구조에서 쓰이는 트리
이 트리 개념에서 트리의 root node는 8번이 유일하다.
8번 노드는 3번 노드의 부모이고, 3번 노드는 8번 노드의 자식이다.
일반적인 알고리즘 문제에서는 이 트리의 개념이 더 자주 출제된다고 한다.
그래프
그래프의 구성 요소
각각의 역(포인트)들을 Vertex(=node, 정점)이라고 하고, 역들을 잇는 선을 edge(간선) 이라고 한다.
그래프 실생활 예) 지도, 내비게이션, SNS, 메신저, VCS(버전관리시스템)인 git 등
그래프의 종류
①그래프는 무방향 그래프와 방향 그래프로 나눌 수 있다.
방향 그래프는 화살표가 있는 쪽으로만 이동할 수 있고,
무방향 그래프는 양방향 그래프와 같다(양방향으로 모두 이동이 가능하다)
또한, ②그래프는 순환성으로 나눌 수도 있다.
순환 그래프와 비순환 그래프로 나눌 수 있는데,
그래프 전체에 순환이 하나라도 존재한다면 순환그래프, 그래프 전체에 순환이 하나도 없다면 비순환 그래프라고 할 수 있다.
위 2가지 개념이 합쳐진 것 중에 따로 용어가 존재하는 것은 아래의 그래프가 있다.
이 그래프의 예시로 VCS(버전관리시스템, git)가 될 수 있다. 시간은 계속 흐르므로..
아래의 그림을 따로 떨어진 3개의 그래프로 보는 것이 아니라 하나의 그래프라고 봤을 때, 연결 요소는 3개가 된다.
위의 다른 예시 그래프에서처럼 노드들이 이어져있는 그래프는 연결 요소가 1개이다.
코드로 그래프를 나타내는 방법
1. 인접행렬
- 방향 그래프의 경우는 아래 그림과 같다.
행렬은 노드의 개수 * 노드의 개수가 되고, 간선이 있는 곳만 행렬이 1로 채워지고, 나머지는 0으로 채워진다. - 무방향 그래프의 경우 간선이 있는 곳은 전부 1(양방향 모두)로 채워진다.
- 행렬의 좌상우하 대각선에 대칭을 이루게 된다.
- (1,0), (2,0), (3,0), (2,1), (2,3)이 모두 1이 된다.
2. 인접리스트
여기서 리스트는 자료구조 연결리스트를 말한다.
- 방향 그래프의 경우 간선이 있을 경우 출발노드쪽에 도착노드를 계속해서 이어붙여준다.
인접행렬과의 차이는 간선이 없는 경우 0으로 채워주는 것이 없다는 것이다. - 무방향 그래프의 경우 양방향을 모두 리스트에 붙여주게 된다.
3. 인접행렬 vs 인접리스트
문제에 V,E 몇 개가 있고 V-E 연결정보 등이 주어질 것이다.
그것을 가지고 판단을 해서 사용을 하게된다.
- 인접행렬이 인접리스트보다 메모리를 많이 쓰게 된다.
- 인접행렬에서는 노드가 N개라면 N^2만큼의 메모리를 쓰게 된다.
- 인접리스트는 간선이 적을수록 메모리를 적게 쓰게 된다.
- 인접행렬은 인접리스트보다 시간적인 측면에서 유리하다.
- 특정 노드 A에서 B로의 간선이 존재하는 지 확인할 때 배열 임의접근으로 O(1)로 확인가능하다.
- 인접리스트는 해당 노드A의 정보를 모두 확인하면서 B가 존재하는 지 확인해야 한다. O(N)
- 기본적인 복잡도는 V가 정점 / E가 간선이라고 할 때,
- 인접행렬 : O(V^2), 인접리스트 : O(V + E)가 된다.
- O(V + E)는 O(max(V,E))라고 볼 수 있다. 빅오 표기법에서는 가장 크게 증가하는 항이 중요하므로..
그렇게 따지면 E가 작으면 O(V)가 되므로 O(V^2)보다 작고 E가 V^2만큼 크다면 O(V+V^2)이 되므로 거의 비슷하니, 시간적인 측면에서라도 유리한 인접행렬을 쓰는 게 좋다는 결론이다.
결론
그러므로 시간/메모리 제한이 있는 문제라면..
간선이 많은 그래프가 주어지면 인접행렬을 사용하고 그렇지 않다면 인접리스트를 사용하는 등.. 선택을 하면 좋다.
그러나, 보통 어느 것을 사용해도 정답처리가 되긴 한다고 한다.
혹시 모를 상황을 위해 둘 다 쓸 수는 있어야 겠다.
출처
이것이 취업을 위한 코딩테스트다 with 파이썬
이코테 저자(나동빈님) 깃허브(참고코드)
알고리즘 코딩 테스트 입문부터 합격까지
