자료구조 & 알고리즘 (5)
이 글은 자료구조와 알고리즘을 '코딩 인터뷰'를 준비하기 위해서 정리한 글입니다.
이번 글은 이진 힙, 트라이, 그래프를 다루겠습니다.
(1) 이진 힙
- 이진 힙에는 최소 힙과 최대 힙이 있습니다.
최소 힙은 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있다는 점에서
완전 이진 트리이며,
각 노드의 원소가 자식들의 원소보다 작다는 특성이 있습니다.
따라서 루트는 트리 전체에서 가장 작은 원소가 됩니다.
최소 힙에는 insert와 extract_min이라는 핵심 연산 두 가지가 존재합니다.
최대 힙은 최소 힙의 반대 개념입니다.
(1-1) 삽입
- 최소힙에 원소를 삽입할 때는 언제나 트리의 밑바닥에서부터 삽입을 시작합니다.
완전 트리의 속성에 위배되지 않게 새로운 원소는 밑바닥 가장 오른쪽 위치로 삽입됩니다.
그 다음에 새로 삽입된 원소가 제대로 된 자리를 찾을 때까지 부모 노드와 교환해 나갑니다.
힙에 있는 노드의 개수가 n이라 할 때, 위의 연산은 O(logn) 시간이 걸립니다.
(1-2) 최소 원소 뽑아내기
- 최소힙에서 최소 원소를 찾기란 쉬운 일입니다.
다만, 이 최솟값을 어떻게 힙에서 제거하느냐가 까다로운 부분입니다.
순서는 다음과 같습니다.
(1) 루트에 있는 원소를 제거합니다.
(2) 힙에 있는 가장 마지막 원소를 루트로 옮깁니다.
(3) 루트에 있는 원소를 자식 노드와 비교해서 교환해 나갑니다.
이 때, 왼쪽 자식과 오른쪽 자식 중 더 작은 원소와 교환해 나갑니다.
(4) 계속 교환해나가다가 더 이상 교환할 필요가 없어지면, 완성된 것입니다.
이 알고리즘은 O(logn) 시간이 걸립니다.
(2) 트라이(접두사 트리)
- 생략
(3) 그래프
- 사실 트리는 그래프의 한 종류입니다.
하지만 모든 그래프가 트리는 아닙니다.
간단히 말해서 트리는 사이클(cycle)이 없는 하나의 연결 그래프(connected graph)입니다.
그래프는 단순히 노드와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 것과 같습니다.
그래프에는 다음과 같은 특징이 있습니다.
(1) 그래프는 방향성이 있을 수도 있고 없을 수도 있습니다.
방향성이 있는 간선은 일방통행, 방향성이 없는 간선은 양방향 통행 도로입니다.
(2) 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있습니다.
모든 노드간에 경로가 존재하는 그래프는 연결 그래프라고 부릅니다.
(3) 그래프에는 사이클이 존재할 수도 있고, 존재하지 않을 수도 있습니다.
사이클이 없는 그래프는 비순환 그래프(acyclic graph)라고 부릅니다.
(3-1) 인접 그래프
- 인접 리스트는 그래프를 표현할 때 사용되는 가장 일반적인 방법입니다.
모든 노드를 인접 리스트에 저장합니다.
무방향 그래프에서 (a,b) 간선은 두 번 저장됩니다.
그래프에서 노드를 정의하는 간단한 클래스는 트리의 노드 클래스와 궁극적으로 같아 보입니다.
(3-2) 인접 행렬
- 생략
(3-3) 그래프 탐색
- 그래프를 탐색하는 일반적인 방법 두 가지로는
깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있습니다.
깊이 우선 탐색은 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에
해당 분기를 완벽하게 탐색하는 방법을 말합니다.
너비 우선 탐색은 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법을 말합니다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때는, BFS가 일반적으로 더 낫습니다.
깊이 우선 탐색을 사용하면 아주 정답에서 동떨어진 경로를 계속해서 탐색해 나갈 수 있습니다.
(3-4) 깊이 우선 탐색(DFS)
- DFS는 a 노드를 방문한 뒤 a와 인접한 노드들을 차례로 순회합니다.
전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류입니다.
이 알고리즘을 구현할 떄 가장 큰 차이점은,
그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다는 것입니다.
이를 검사하지 않을 경우 무한루프에 빠질 위험이 있습니다.
(3-5) 너비 우선 탐색(BFS)
- BFS는 직관적이지 않은 면이 있습니다.
BFS 구현에 실패하는 가장 흔한 이유는 BFS가 재귀적으로 동작할 거라고 잘못 가정하는 것입니다.
BFS는 재귀적으로 동작하지 않습니다. BFS는 큐(queue)를 사용합니다.
BFS는 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작합니다.
(3-6) 양방향 탐색
- 양방향 탐색은 출발지와 도착지 사이에 최단 경로를 찾을 때 사용되곤 합니다.
기본적으로 출발지와 도착지 두 노드에서 동시에 BFS를 수행한 뒤,
두 탐색 지점이 충돌하는 경우에 경로를 찾는 방식입니다.
Q&A
(1) 이진 힙
Q. 왜 이진 힙은 최소 힙과 최대 힙으로 구분 되는가? 최소 힙은 어떤 용도로 사용되는가?
A.
Q. 왜 힙에 있는 노드의 수가 n이라고 할 때, 삽입은 O(logn)이 걸리는가?
A.
(3) 그래프
Q. 왜 그래프에는 방향성이 있을 수도 있고 없을 수도 있는가?
A.
Q. 왜 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있는가?
A.
Q. 왜 그래프에는 사이클이 존재할 수도 있고, 존재하지 않을 수도 있는가?
(3-1) 인접 리스트
Q. 왜 인접 리스트는 그래프를 표현할 때 사용되는 가장 일반적인 방법인가?
A.
(3-3) 그래프 탐색
Q. 왜 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때는, BFS가 일반적으로 더 나은가?
(3-4) 깊이 우선 탐색(DFS)
Q. 왜 DFS를 구현할 때는, 어떤 노드를 방문하였었는지 반드시 검사를 해야 하는가?
A. 같은 노드를 중복해서 방문하면 안되기 때문입니다.
Q. 왜 같은 노드를 중복해서 방문하면 안되는가?
A. 같은 노드를 중복해서 방문하면 무한루프에 빠지게 되기 때문입니다.
Q. 왜 같은 노드를 중복해서 방문하면 무한루프에 빠지는가?
A. 결국 깊이 우선 탐색의 목적은 그래프에서 특정 노드에 저장된 데이터를 검색하는 것입니다.
이 때, 특정 노드를 방문해서 원하는 데이터를 검색하지 못했다면,
그 노드는 다시 방문할 필요가 없습니다.
만약 특정 노드를 방문했는데, 그 노드를 방문했다는 검사를 하지 않으면,
그 노드를 방문했는지 안했는지 알 수 없어서 다시 그 노드를 방문해야 하는 일이 발생합니다.
따라서 무한루프에 빠질 수 있고, 그것을 방지하려면
어떤 노드를 방문했는지 반드시 검사해야 합니다.
(3-5) 너비 우선 탐색
Q. 왜 BFS는 재귀적으로 동작하지 않고 큐(queue)를 사용합니까?
A.
Q. 왜 BFS는 큐를 이용해서 반복적으로 구현하는 것이 가장 잘 동작합니까?
A.
- 이 글의 내용은 '코딩 인터뷰 완전 분석'을 참조했습니다.
