[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

[코딩 팁] 방향 배열(Direction Array) : 상하좌우 이동

인트로 2차원 좌표상에서 한 점을 기준으로 상하좌우 좌표를 구할 때 코드를 간결하게 작성하는 방법이다. 방향 배열은 BFS, 다익스트라, A*알고리즘에 자주 등장한다. 코드 switch 혹은 if-else문을 작성하지 않아도 된다. int main() { //상 하 좌 우 int dirY[4] = { -1, 1, 0, 0 }; int dirX[4] = { 0, 0, -1, 1 }; int arr[3][3] = { {1,2,3},{4,5,6}, {7,8,9} }; int posY = 1, posX = 1; cout

• format_list_bulleted Algorithm/감명 깊게 본 코딩 팁
• · 2021. 10. 3.
• 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