유니온 파인드(Union-Find) 그래프/트리의 대표적인 알고리즘이다 상호 배타적 집합(Disjoint-set)이라고도 부른다 하나의 원소가 둘 이상의 집합에 속하지 않는 서로소 집합으로 표현하기 때문이다 여러 노드가 있을 때, 두 노드가 같은 그래프(집합)에 속해 있는지 판별하는 알고리즘이다 union 연산과 find 연산으로 이루어져 있다 union 연산 : 두 원소가 속한 각 집합을 합치는 연산 find 연산 : 주어진 원소가 포함된 집합의 부모 노드를 구하는 연산 시간복잡도 : O(log N) 평균적으로 트리의 높이만큼을 탐색한다 Union 연산 다음과 같은 두 집합이 있다고 하자. 집합은 모두 대표노드가 존재하며, 대표 노드는 집합에서 최종 부모 노드, 즉 가장 값이 작은 노드이다. 따라서 노..

이분탐색(이진탐색, Binary Search) 정의 정렬된 자료를 절반씩 쪼개어 탐색하는 방법이다 순차탐색보다 빠른 탐색을 위해 나온 방법이다 탐색을 진행할 때마다 탐색 범위가 반으로 줄어드므로, 분할 정복 알고리즘의 일종이다 데이터가 고정되어 있는 경우에 적합하다 삭제 또는 삽입이 빈번한 경우에는 적합하지 않다 장점 시간 복잡도가 O(log N) 으로 빠른 탐색 속도를 갖는다 모든 값을 순차적으로 탐색하는 순차적 탐색방법(O(N))에 비해 시간 복잡도가 낮다 적용 가능한 경우 1. 원소가 정렬되어 있는 경우 원소가 정렬된 경우에만 mid 인덱스의 수와의 비교를 통해 탐색 범위를 줄일 수 있다. 따라서 오름차순 혹은 내림차순으로 정렬이 되어 있어야만 이분탐색이 가능하다. 2. 원소의 Random Acce..

브루트 포스 (Brute Force) 브루트(Brute)는 '무식한'을 뜻하고, 포스(Force)는 '힘'을 뜻한다. 즉, '발생가능한 모든 경우를 탐색하는 무식한 방법'을 말한다. 정의 모든 영역을 전체 탐색(완전 탐색)하는 방법이다. 전체 탐색이므로 해만 존재한다면, 반드시 찾을 수 있다. 전체 탐색하는 방법으로 문제를 해결한다면 브루토 포스 알고리즘으로 문제를 해결한 것이다. 순차탐색 : 선형 구조(ex-배열)를 전체적으로 탐색 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) : 비선형 구조를 전체적으로 탐색 더보기 전체 탐색(완전 탐색) 모든 경우의 수를 탐색하는 알고리즘이다. 장점 알고리즘 설계와 구현이 쉽다. 복잡한 알고리즘 없이 빠르게 구현가능하다. 입력 값이 작은 경우 유용하다. 단점 ..