본문 바로가기

Algorithm/탐색10

[Algorithm] 다익스트라 알고리즘 : 음수 간선이 있으면 안 되는 이유 인트로 [2021.11.15 오타 수정] [2022.08.16 오류 수정] 다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘이다. 단 가중치가 모두 양수라는 조건이 있다. 이러한 이유는 다익스트라 알고리즘은 그리디(Greedy) 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다. 반면 음수 가중치가 포함된 그래프라면 벨만-포드 알고리즘 사용 시 목표 노드까지의 최단 경로를 구할 수 있다. 그렇다면 음수가 포함된 가중치에서 다익스트라 알고리즘을 사용하면 어떤 문제가 발생할까? - - 음수 가중치가 포함된 그래프에서 다익스트라 알고리즘의 문제점을 파악하면 벨만-포드 알고리즘을 더 쉽게 이해할 수 있을 것이다. 다익스트라 문제점 :.. 2021. 10. 12.
[Algorithm] 유니온 파인드 (Union-Find) : Disjoint-set 표현 인트로 Union-Find 알고리즘은 서로소 집합*(Disjoint-set)을 표현하는 그래프 알고리즘으로 임의의 두 노드(원소)가 서로 같은 그래프(집합)에 속하는지 판별하는 알고리즘이다. 여기엔 핵심이 되는 두 가지 연산이 존재한다. Union : 원소 x가 포함된 집합과 원소 y가 포함된 집합을 하나로 합치는 연산 Find : 원소 x가 포함된 집합을 반환하는 연산 참고로 Union-Find 알고리즘은 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘에 사용된다. 서로소 집합 (Disjoint-set)이란? 공통 원소가 없는 두 집합을 서로소 집합이라 한다. A = { 1, 2 ,3 } B = { 5, 7, 9 } 집합 A와 B는 서로소 집합이다. A = { 3, 5 ,7 } B = { 7, 9,.. 2021. 10. 6.
[Algorithm] 조합(Combination) 구현 코드 인트로 본 포스팅에선 조합을 구하는 코드를 소개하려 한다. 결론부터 말하면 재귀 함수(DFS)로 조합을 구할 수 있다. 조합이란 n개 중에 r개를 "순서에 무관하게" 뽑는 경우의 수로 다음과 같이 표현한다. $_nC_r=\frac{n!}{(n-r)!r!}$ 이와 유사하게 순서를 고려해 n개 중에 r개를 뽑는 것을 순열이라고 한다. ※참고 - 순열 포스팅 [Algorithm] 순열(Permutation) 구현 코드 조합 : 코드 순서에 무관하게 숫자를 뽑기때문에 별도의 visited 배열이 필요하지 않다. #include using namespace std; int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int cnt, n, r; int order[4]; void c.. 2021. 10. 5.
[Algorithm] 순열(Permutation) 구현 코드 인트로 본 포스팅에선 순열을 구하는 코드를 소개하려 한다. 결론부터 말하면 재귀 함수(DFS)로 순열을 구할 수 있다. 순열이란 n개 중에 r개를 뽑아 순서 있게 나열하는 경우의 수로 다음과 같이 표현한다. $_nP_r=\frac{n!}{(n-r)!}$ 이와 유사하게 순서가 없이 n개 중에 r개를 뽑는 것을 조합이라고 한다. 순열 : 코드 DFS로 순열을 구하는 코드이다. 집합의 원소 번호를 order배열에 순열의 형태로 저장하고 출력 시 arr배열의 인덱싱 용도로 사용한다. #include using namespace std; int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int cnt, n, r; int visited[4]; int order[4]; void p.. 2021. 10. 4.
[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도 인트로 이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다. 본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다. 이진 탐색 : 개념 이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값.. 2021. 9. 16.
[Algorithm] A* 알고리즘 : 최단 경로 탐색 ✍️ 인트로 A* 알고리즘은 그래프의 탐색 알고리즘으로 주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다. 대표적인 그래프 탐색 알고리즘들과 A*의 차이점은 BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며 다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다. 반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다. [※ 정리 ※] BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘 A* : 가중치 그래프, 시작.. 2021. 9. 3.
[Algorithm] 다익스트라 알고리즘 : 최단 경로 탐색(1) - 배열 인트로 다익스트라 알고리즘은 그래프의 탐색 알고리즘으로 BFS가 가중치 없는 그래프의 최단경로를 찾는 알고리즘이라면 다익스트라 알고리즘은 가중치가 있는 그래프의 최단경로를 구할 때 사용된다. 참고로 다익스트라 길 찾기 알고리즘은 DFS, BFS와 마찬가지로 완전 탐색 알고리즘에 속한다. 다익스트라(Dijkstra) 이해하기 1) 아래와 같은 가중치 그래프가 있다. 0번 정점에서 시작해 5번 정점까지의 최단거리를 구해보자. 최단거리를 저장할 배열(DIST)이 다음과 같은 형태로 있다. DIST[ ∞, ∞, ∞, ∞, ∞, ∞ ] (+ 아직 최단거리를 모르니 모두 ∞로 초기화한다.) 2) 시작 정점인 "0"번 정점을 방문한다. 시작 정점인 "0"번 정점은 최단거리가 "0"이므로 DIST[ 0, ∞, ∞, ∞.. 2021. 8. 31.
[Algorithm] 이진 탐색 트리 (Binary Search Tree, BST) + 전위 중위 후위 순회 인트로 그래프의 탐색 방법으로 DFS와 BFS가 대표적이다. 트리는 특정 조건을 만족하는 그래프이다. 따라서 트리에 BFS와 DFS 탐색 알고리즘을 적용할 수 있다. 본 포스팅에선 DFS에 기반한 이진 트리 탐색 알고리즘인 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)를 다루려 한다. (+ 2021.09.01 추가 이진 트리의 순회 알고리즘을 소개하며 이진 트리와 이진 탐색 트리를 모두 소개하다 보니 전달하려는 의미가 모호해졌네요.일반적으로 이진 트리의 순회는 전위 중위 후위 순회가 있습니다. 물론 이진 탐색 트리도 일종의 이진 트리이기에 순회 가능합니다. 나아가 이진 탐색 트리는 "이진 탐색"에 기반한 추상.. 2021. 8. 27.
[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 인트로 그래프의 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색)를 구현해보려 한다. DFS와 다르게 BFS는 주로 한 가지 목적으로 사용된다. 그것은 가중치가 없는 그래프의 최단 경로를 구할 때 사용된다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 BFS를 구현하는 간단한 코드와 최단 경로 출력 코드를 소개하려 한다. 결론부터 말하면 Queue를 사용해서 BFS를 구현했다. DFS가 궁금하다면? DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 [Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘 인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한.. 2021. 8. 23.
반응형

티스토리툴바