알고리즘 개념 2일차

작일에 대해 알고리즘 2일차에 접어들었다. 알고리즘을 배우면서 상당히 많은 곳에서 쓰인다는 것을 깨달았다. 예를 들어서 우리가 게임을 하면서 자동 길찾기 시스템이나 마우스로 누르면 그곳으로 이동하는 것도 알고리즘 시스템이 들어간다는 것이다. 그렇기에 상황이 일어났을 때 어떤 알고리즘을 써야하는지 파악해둘 필요가 있다. 전에처럼 모든 상황에서의 최고의 알고리즘은 없지만 어떤 상황에서의 최적의 알고리즘이 있기 때문이다.

깊이 우선 탐색 (Depth First Search)

그래프가 분기를 만났을 때 시작 노드에서 자식의 노드를 깊이 우선으로 찾는 탐색 방법이다. 분기의 탐색을 마쳤을 때 다음 분기를 탐색하는 방식으로 스택을 통해 구현된다. 일반적으로 경로가 하나밖에 없는 트리의 사용을 선호한다

장점 : 지금 탐색상황에서 필요한 점정데이터만 보관가능하고 탐색이 끝나면 버려도 무관하다.
단점 : 최단 경로를 보장하지 않음

활용된 게임 예시 : 할로우 나이트, 오리와 눈먼 숲, 슬레이 더 스파이어

다음 그림에서는 시작 노드인 0에서 부터 시작해서 왼쪽에 있는 1로 가고 3으로 간다. 다음은 2가 아닌 1에서 5로 가는 노드로 가는데 깊은 곳으로 가기 때문이다. 5에서 더 깊은 곳으로 이어진 노드가 없으니 2로 이어지고 이 순서대로 가면 0-1-3-5-2-4-6-7 순서가 된다.

장점 : 지금 탐색상황에서 필요한 점정데이터만 보관가능하고 탐색이 끝나면 버려도 무관 하다.
단점 : 최단 경로를 보장하지 않음.

너비 우선 탐색 (Breadth-Frist Search)

그래프가 분기를 만났을 때 모든 분기들을 탐색한 뒤 다음 깊이의 분기들을 탐색하는 방법이다. 시작 노드에서 가까운 지점을 먼저 찾고 머리 떨어져 있는 지점을 나중에 찾는 방법이다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택하며 큐를 통해 탐색한다.

아래 그림을 예시로 시작 노드인 0은 1, 2, 3의 분기를 가지고 있기에 0-1 과 0-2 로 시작한다 그 다음 0의 마지막 분기인 3에 도착하고 다음 1의 분기인 6으로 간다. 이 순서대로 나타낸 순서는 0-1-2-3-6-4-5 이다.

장점 : 최단 경로를 보장한다
단점 : 지금 탐색상황에서 필요하지 않은 정점데이터도 큐에 보관할 필요가 있다.

다익스트라 알고리즘

특정한 노드에서 출발하여 다른 노드까지 가는 각각의 최단 경로를 구하는 알고리즘이다.하지 않은 노드 중에서 가장 가까운 노드를 선택한 후, 택한 노드를 거쳐서 더 짧아지는 경로가 있는 경우에는 덮어씌운다. 음수 가중치가 없는 그래프에서 동작하며 큐를 활용한다.

아래의 그림을 살펴보자 우선 0인 시작 노드에서 6까지 갈려면 최단 경로는 0-2-6 처럼 보일 것이다. 하지만 가중치에 의해서 0-2-6은 값이 14인데 비해 0-3-7-6은 6이다. 그러므로 아래의 표에서 6은 6의 가중치 값을 가지는 것이다.

장점 : 빠른 실행 속도, 다양한 분야에서 활용 가능
단점 : 모든 노드에 대해 탐색해야함, 메모리 사용량 증가