유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되는 알고리즘입니다. Union-Find 과정 최초 노드는 자기자신을 루트노드로 가짐 Union(x, y) : x가 속한 집합과 y가 속한 집합을 합침 대표 노드를 설정하고 자식이 되는 노드의 값을 대표 노드의 값으로 변경 Find(x) : x가 속한 집하의 root 노드를 반환 대상 노드 배열에 index 값과 value값이 동일한지 확인 동일하지 않으면 value값이 가리키는 index 위치로 이동 이동 위치의 index값과 value값이 같을 때까지 1~2번 반복 대표 노드에 도달하면 대표 노드로 도달하기 까지의 모든 노..
유클리드 호제법은 두수의 최대 공약수를 구하는 알고리즘입니다. 1071과 1029의 최대 공약수 1071 MOD 1029 = 42 1029 MOD 42 = 21 42 MOD 21 = 0 최대공약수 = 21 유클리드 호제법의 연산 순서는 다음과 같습니다. MOD연산은 두 값을 나눈 나머지를 구하는 연산입니다. 큰 수를 작은 수로 나누는 MOD 연산 수행 앞 단계에서의 작은수와 MOD연산 결괏값(나머지)로 MOD 연산 수행 2번을 반복하다가 나머지가 0이 되는 순가의 작은 수를 최대 공약수로 선택
소수는 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로 나누어 떨어지지 않는 자연수 입니다. 예를 들면 2, 3, 5, 7 등 다른 수로 나누어 질 수 없는 수입니다. 에라토스테네스의 체 소수를 구하는 대표적인 판별법은 에라토스테네스의 체가 있습니다. 에라토스테네스의 체를 이용해 소수를 구하는 방법은 다음과 같습니다. 구하고자하는 소수의 범위 만큼 1차원 배열 생성 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움 다음 숫자 중 지워지지 않은 숫자로 이동 배열의 끝에 도달할 때까지 2~3번 반복 에라토스테네스의 체의 경우 이중 for문을 이용하지만 배수를 삭제하는 연산으로 인해 실제 구현에서 for문이 생략되는 경우가 빈번하게 발생합니다. 그렇기 때문에 O..
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리기도 합니다. 그 이유는 미래는 생각하지 않고 현재 주어진 선택지에서 가장 최선의 선택을 하는 알고리즘 이기 때문입니다. 그리디 알고리즘의 수행 과정은 다음과 같습니다. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사. 전체 문제를 해결하지 못하면 1로 돌아가 반복
이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 입니다. 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는 방법입니다. 시간 복잡도는 O(log n)입니다. 탐색 과정 현재 데이터에서 중앙값 선택 중앙값 > 탐색값 일 때 중앙 값을 기준으로 왼쪽데이터셋 선택 중앙값 < 탐색값 일 때 중앙 값을 기준으로 오른쪽데이터셋 선택 탐색값을 찾을 때까지 1 ~ 3번 과정 반복 구현 아래의 문제를 예시로 들어 이진탐색을 구현하였습니다. 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에..
깊이 우선 탐색(DFS : Depth First Search) 너비 우선 탐색은 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 입니다. FIFO(First In First Out) 방식으로 큐를 이용하여 구현하며 탐색 시작 노드와 가까운 노드를 우선하여 탐색하기 때문에 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장합니다. 장단점 장점 시작 노드부터 목표 노드 까지의 최단 경로를 보장 단점 큐를 이용해 다음에 탐색 할 노드를 저장하기 때문에 노드의 수가 많을 수로 많은 저장 공간을 필요로함 노드의 수가 늘어나면 탐색해야 하는 노드가 많아지기 때문에 비효율적 구현 방법 BFS를 사용하기 위해서는 먼저 그래프를..
그래프의 연결관계를 나타내는 방식은 인접 행렬과 인접 리스트로 두 가지의 방법이 있습니다. 인접 행렬(Adjacency Matrix) 인접 행렬은 이차원 배열을 이용하여 그래프를 표현하는 방식입니다. 위 의 그림과 같이 2 차원 배열의 형태로 두 노드의 번호를 좌표로 이용하여 1이면 연결이 되었음을 0이면 연결 되지 않았음을 뜻하게 됩니다. 무방향 그래프의 경우 양방향으로 연결 되기 때문에 아래와 같이 두 좌표에 입력을 합니다. graph[i][j] = 1 graph[j][i] = 1 방향 그래프의 경우 한쪽에서만 연결 되기 때문에 한 좌표에만 입력을 합니다. graph[i][j] = 1 장단점 장점 구현이 쉬움 노드의 연결성을 확인할 때 시간 복잡도는 O(1)로 빠름 단점 간선의 수와 상관 없이 항상 ..
깊이 우선 탐색(DFS : Depth First Search) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나입니다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 입니다. 구현은 재귀 함수, 스택을 이용하며 시간 복잡도는 O(V + E) V = 노드 수, E = 엣지 수 입니다. 장단점 장점 현 경로상의 노드들만 기억하면 되기때문에 저장 공간의 수요가 적음 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음 단점 해가 없는 경로에 깊이 빠질 가능성이 있음 얻어진 해가 최단 경로가 된다는 보장이 없음 구현 방법 DFS를 사용하기 위해서는 먼저 그래프를 구현 해야합니다. 그래프를 ..
기수 정렬은 값을 비교하지 않는 특이한 정렬입니다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교합니다. 기수 정렬의 시간 복잡도는 O(kn)이고, k는 데이터의 자릿수를 의미합니다. 정렬 과정 입력한 수열은 몇 개의 키로 분류됩니다. 3자리이하 수라고 한다면, 1의 자리, 10의 자리, 100의 자리로 나누어 분류됩니다. 170, 45, 75, 90, 2, 24, 802, 66 1의 자리만 보고 정렬을 수행 ↓ 170, 90, 2, 802, 24, 45, 75, 66 10의 자리만 보고 정렬 수행 ↓ 2, 802, 24, 45, 66, 170, 75, 90 100의 자리만 보고 정렬 수행 ↓ 2, 24, 45, 66, 75, 90, 170, 802 위와 같은 과정을 통해 정렬이 ..
병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘 입니다. 시간 복잡도는 O(nlogn)입니다. 정렬 과정 최초에 N개의 그룹으로 나눕니다. 그림을 예로 들면 8개로 나누게 되고 이 상태에서 2개씩 그룹을 합치며 오름차순 정렬합니다. (1), (2), (3), (4), (5), (6), (7), (8) ↓ (5, 6), (1, 3), (7, 8), (2, 4) ↓ (1, 3, 5, 6), (2, 4 ,7, 8) ↓ (1, 2, 3, 4, 5, 6, 7, 8) 소스 코드 public void mergeSort(int A[], int low, int high, int B[]){ // 1. base condition if(low >= high) return; // ..
