분류 전체보기 (60) 썸네일형 리스트형 A* algorithm 안녕하세요. 오늘은 A* algorithm (A star algorithm) 에 대해 알아보겠습니다. 최단 경로 휴리스틱 알고리즘 시작 정점 s에서 끝 정점 e 까지의 최단 경로를 근사화한 값을 구하기 위한 최단 경로 알고리즘 입니다. 휴리스틱 알고리즘 중 하나 입니다. 최단 경로를 찾는데 가장 유명한 알고리즘이 다익스트라 알고리즘 입니다. 다익스트라 알고리즘은 시작 정점에서 현재 정점까지 걸린 비용이 작은 것을 우선으로 탐색합니다. A* algorithm은 f cost가 작은 것을 우선으로 탐색합니다. f cost = g cost + h cost g cost = 시작 정점에서 현재 정점까지 걸린 비용 h cost = 현재 정점에서 끝 정점까지 걸릴 예상 비용 g cost가 다익스트라 알고리즘에서 우선시.. Topological Sort (위상 정렬) 안녕하세요. Topological Sort (위상 정렬)에 대해 알아보도록 하겠습니다. 간선의 방향에 따라 노드를 정렬 위상 정렬은 DAG (Directed Acyclic Graph) 에서 작동하는 알고리즘 입니다. Directed : 간선에 방향성이 있음 Acyclic : 순환 경로가 없는 그래프 => DAG란, 간선에 방향성이 있고 사이클이 존재하지 않는 그래프 노드를 간선의 방향을 거스르지 않고 정렬하는 알고리즘 입니다. 간선 (u -> v)가 있다고 가정하면, 노드를 정렬했을 때 u가 v보다 먼저 나타나야 합니다. 위의 [그림 1]에서 위상 정렬을 하면 아래와 같이 나올 수 있습니다. (위상 정렬은 정답이 여러 개가 나올 수 있습니다.) 1 -> 2 -> 3 -> 4 -> 5 2 -> 1 -> 3.. Disjoint-set 안녕하세요. Disjoint-set에 대해 알아보도록 하겠습니다. 서로소 집합, 분리 집합 Disjoint-set은 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합입니다. 서로 다른 원소들이 같은 집합에 있는지, 혹은 다른 집합에 있는지를 판별할 수 있습니다. 트리 형태로 관리하며, 연산이 union과 find 두 가지가 있기에 union-find 라고도 불립니다. 과정 어떤 알고리즘을 거쳐서 disjoint-set이 같은 집합에 속하는지를 판별할 수 있는지 알아보겠습니다. 1) parent 배열 준비 parent 배열이란, parent(x)의 값은 x의 부모 노드를 의미합니다. 처음에는 모든 노드가 자기 자신이 루트 노드인 트리이므로 아래와 같이 설정해줍니다. 2) union 연산 union .. 네이버 블로그 기존에 작성하던 네이버 블로그에 이어서 티스토리에도 블로그를 작성합니다. 감사합니다. https://blog.naver.com/kdr06006 알고리즘 블로그 : 네이버 블로그 IT 블로그 경북대학교 모바일공학과 blog.naver.com 이전 1 ··· 5 6 7 8 다음
