[Algorithm] 다익스트라 알고리즘 : 음수 간선이 있으면 안 되는 이유

인트로 [2021.11.15 오타 수정] [2022.08.16 오류 수정] 다익스트라 알고리즘은 가중치 그래프에서 최단 경로를 찾는 알고리즘이다. 단 가중치가 모두 양수라는 조건이 있다. 이러한 이유는 다익스트라 알고리즘은 그리디(Greedy) 기반의 알고리즘으로 최소 거리에 최소 거리를 붙여가면 최종적으로 길을 찾기 때문에 음수 가중치는 고려하지 못한다. 반면 음수 가중치가 포함된 그래프라면 벨만-포드 알고리즘 사용 시 목표 노드까지의 최단 경로를 구할 수 있다. 그렇다면 음수가 포함된 가중치에서 다익스트라 알고리즘을 사용하면 어떤 문제가 발생할까? - - 음수 가중치가 포함된 그래프에서 다익스트라 알고리즘의 문제점을 파악하면 벨만-포드 알고리즘을 더 쉽게 이해할 수 있을 것이다. 다익스트라 문제점 :..

• format_list_bulleted Algorithm/탐색
• · 2021. 10. 12.
• textsms

[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,..

• format_list_bulleted Algorithm/탐색
• · 2021. 10. 6.
• textsms

[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..

• format_list_bulleted Algorithm/탐색
• · 2021. 10. 5.
• textsms

[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..

• format_list_bulleted Algorithm/탐색
• · 2021. 10. 4.
• textsms

[Algorithm] 이진 탐색 (이분 탐색, Binary Search) 코드와 시간 복잡도

인트로 이진 탐색이란 정렬된 배열에서 특정 값을 찾는 탐색 알고리즘이다. 이진 탐색은 배열의 중간을 기준으로 데이터를 탐색하기 때문에 반드시 데이터가 정렬된 상태로 존재해야 한다. 이진 탐색의 시간 복잡도는 O(logN)으로 배열을 전수 조사하는 O(N)에 비하면 상대적으로 빠른 탐색 알고리즘에 속한다. O(logN)만에 값을 찾을 수 있는 이유는 중간을 기준으로 탐색 대상을 절반씩 줄여나가기 때문이다. 본 포스팅 말미에 코드와 시간 복잡도 계산법을 상세히 적어놨으니 참고하시길 바랍니다. 이진 탐색 : 개념 이진 탐색은 내가 찾고자 하는 값이 정렬된 배열의 중간 값보다 크면 중간값을 포함한 하위 값들은 탐색 대상에서 제외된다. 반대로 찾고자 하는 값이 배열의 중간 값보다 작으면 중간 값을 포함한 상위 값..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 16.
• textsms

[Algorithm] A* 알고리즘 : 최단 경로 탐색

✍️ 인트로 A* 알고리즘은 그래프의 탐색 알고리즘으로 주로 게임에서 플레이어를 목표지점으로 이동시킬 때 사용하는 알고리즘이다. 대표적인 그래프 탐색 알고리즘들과 A*의 차이점은 BFS는 가중치가 없는 그래프에서 최단 경로를 찾는 완전 탐색 알고리즘이며 다익스트라는 가중치 그래프에서 시작 노드를 기준으로 모든 노드까지의 최단거리를 구하는 그리디 알고리즘이다. 반면 A* 알고리즘은 가중치 그래프에서 시작 노드에서 목표 노드까지의 최단 경로만 구하려 하는 그리디 알고리즘이다. [※ 정리 ※] BFS : 가중치 없는 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 완전 탐색 다익스트라 : 가중치 그래프, 시작 노드 기준으로 모든 노드의 최단 경로 구함, 그리디 알고리즘 A* : 가중치 그래프, 시작..

• format_list_bulleted Algorithm/탐색
• · 2021. 9. 3.
• textsms