알고리즘/알고리즘 도감 (44) 썸네일형 리스트형 A* 지난 글 : [알고리즘] - 다익스트라 알고리즘 A*(에이 스타)는 그래프의 최단 경로를 찾는 알고리즘으로 다익스트라 알고리즘을 발전시킨 것이다. 다익스트라 알고리즘에서는 시작점에서 각 정점까지의 최단 경로를 순서대로 결정해 가며, 시작점에 가까운 정점부터 순서대로 결정한다. 따라서 시작점에서 멀리 떨어진 정점의 최단 경로도 결정한다. 허나 이것은 결국 사용하지 않아 의미가 없게 된다. A*는 미리 추정 가중치를 설정해 불필요한 탐색을 방지하도록 개선한 기법이다. 1 칸으로 이루어진 미로 속에서 시작점과 목표 정점을 정한다. 미로는 각 칸을 정점으로 간주하고 각 정점 사이의 가중치가 1인 그래프라고 해석한다. 2 다익스트라 알고리즘으로 최단 경로를 구하면 필요 없는 경로도 모두 구한다. 하지만 A*에서는.. 다익스트라 알고리즘 지난 글 : [알고리즘] - 벨먼-포드 알고리즘 다익스트라(Dijkstra) 알고리즘은 지난 글에서 배운 벨먼-포드 알고리즘과 같이 그래프의 최단 경로 문제를 해결하기 위한 알고리즘이다. 시작점부터 종점까지의 경로 중 가중치의 합이 가장 작은 것을 구한다. 1 B---3---E /|\ / \ 2 | 1 4 9 / | \ / \ A 6 D G \ | / 5 | 7 \| / C---8---F 시작점 A, 종점 G이다. 먼저 각 정점의 초기 가중치를 시작점은 0, 그 외 정점은 무한대로 설정한다. 2 'B'--3---E /|\ / \ 2 | 1 4 9 / | \ / \ "A" 6 D G \ | / 5 | 7 \| / 'C'--8---F 현재 정점을 " "로, 후보 정점은 ' '로 표시한다. 현재 정점에서 갈 .. 벨먼-포드 알고리즘 지난 글 : [알고리즘] - 깊이 우선 탐색 벨먼-포드(Bellman-Ford) 알고리즘은 그래프의 최단 경로 문제를 해결하기 위한 알고리즘이다. 최단 경로 문제에서는 간선에 가중치가 부여된 '가중 그래프'가 주어지며 시작점과 종점이 지정된다. 시작점부터 종점까지의 경로 중 간선의 가중치 합이 가장 작은 것을 구하는 문제다. 1 B---1---E /|\ /|\ 9 | 3 5 | 7 / | \ / | \ "A" 6 D 3 G \ | / \ | / 2 | 2 6 | 4 \|/ \|/ C---9---F 여기서 A를 시작점, G를 종점으로 한다. 각 종점의 초기 가중치를 설정한다. 시작점은 0, 그 외의 정점은 무한대로 설정한다. 이 가중치는 A부터 해당 정점까지의 최단 경로의 길이를 나타내는 임시 가중치다. .. 깊이 우선 탐색 지난 글 : [알고리즘] - 너비 우선 탐색 깊은 우선 탐색은 너비 우선 탐색과 마찬가지로 그래프를 탐색하는 알고리즘이다. 시작점으로부터 지정한 정점(목표)에 도달하는 것이 목적이다. 깊이 우선 탐색에서는 정점을 탐색할 때 하나의 길을 끝까지 따라가며 더 이상 진행할 수 없는 곳에 다다르면 다음 후보가 되는 길을 따라간다. 1 "A" / | \ B C D / | | | \ E F H I J | | | K G L A를 시작점, G를 목표로 한다. 현재 위치는 " "로 표시한다. 2 "A" / | \ 'B C D' / | | | \ E F H I J | | | K G L A에서 도달할 수 있는 정점 B, C, D를 다음 후보로 표시한다. 후보는 ' '로 표시한다. 3 A / | \ "B"'C D' / | |.. 너비 우선 탐색 지난 글 : [알고리즘] - 그래프 너비 우선 탐색은 그래프를 탐색하는 알고리즘이다. 최초 시점에 자신이 특정 정점(시작점)에 있다고 하자. 단, 그래프의 전체 구조는 모른다. 목적은 시작점에서 간선을 따라 가며 정점을 탐색하고 지정한 정점(목표)에 도달하는 것이다. 정점에 도착하면 해당 점이 목표인지를 판단할 수 있다. 너비 우선 탐색이란, 정점을 탐색할 때 시작점에 가까운 정점부터 탐색하는 방식이다. 1 "A" / | \ B C D / | | | \ E F H I J / | \ K G L 자신이 현재 있는 정점을 " "로 표시한다(책에서는 빨간색). A를 시작점, G를 목표라 한다. 처음에는 시작점 A에 있으며 G가 어디에 있는지 모른다. 2 "A" / | \ 'B C D' / | | | \ E F .. 그래프 지난 글 : [알고리즘] - 이진 탐색 이산수학에서의 그래프 '그래프(graph)'라 하면 원 그래프나 막대 그래프 등을 떠올린다.하지만 컴퓨터 과학이나 이산수학에서 사용되는 '그래프'는 뉴런처럼 '정점(혹은 노드(node))'이라는 것과 정점과 정점을 연결하는 선, '간선(혹은 링크(link))'으로 이루어져있다. 즉, 그래프는 몇 개의 정점이 간선으로 연결된 것을 가리킨다. 그래프는 다양한 것들을 표현할 수 있다 그래프는 세상에 존재하는 다양한 것들을 표현할 수 있어 편리하다. 예로 역을 정점으로 하고 경로상 인접한 두 역을 선으로 연결하면 노선도를 나타내는 그래프가 만들어진다. 또, 컴퓨터 네트워크에서 라우터(router)를 정점으로 하고 링크로 연결된 두 개의 라우터를 간선으로 이으면 네트워크 접.. 이진 탐색 지난 글 : [알고리즘] - 선형 탐색 이진 탐색은 배열에서 데이터를 탐색하는 알고리즘이다. 지난 글에서 배운 선형 탐색과 달리, 데이터가 정렬된 경우에만 적용할 수 있다. 배열의 가운데 있는 데이터와 대상 데이터를 비교해서 대상 데이터가 정중앙보다 오른쪽에 있는지 왼쪽에 있는지를 알 수 있다. 한 번의 비교만으로 탐색해야 할 범위를 반으로 줄일 수 있는 것이다. 이것을 대상 데이터를 찾거나 존재하지 않는다는 것을 알 때까지 반복한다. 1 123456789 여기서 6을 탐색해보자. 123456789 ----- 먼저 배열의 정중앙에 있는 수를 찾는다. 여기서는 5가 된다. 2 123456789 --------- 5와 탐색할 수인 6을 비교한다. 5 < 6 이므로 대상 데이터(6)가 5보다 오른쪽에 있다는 .. 선형 탐색 지난 글: [알고리즘] - 퀵 정렬 선형 탐색은 배열에서 데이터를 탐색하는 알고리즘이다. '배열'에 대해서는 이전에 작성한 [알고리즘] - 배열에 상세히 설명하고 있다. 바로 다음에 배울 이진 탐색과 달리 데이터가 마구잡이로 나열돼 있어도 적용할 수 있다. 작업은 단순해서 배열의 앞에서부터 순서대로 데이터를 확인하면 된다. 저장되는 데이터는 아무 것이나 상관없지만 여기서는 잘 이해하기 위해 정수가 저장된 경우를 가정한다. 1 398214657 여기서 6을 탐색해보자. 398214657 ----- 먼저 배열의 왼쪽 끝 숫자를 확인한다. 6과 비교해서 일치하면 탐색을 종료, 그렇지 않으면 하나 오른쪽에 잇는 숫자를 확인한다. 2 398214657 ----- 일치하지 않았으므로 하나 오른쪽에 잇는 숫자를 확인.. 이전 1 2 3 4 5 6 다음
