1. 유니온 파인드(Union-Find)란 여러 개의 노드가 존재할 때, 두 개의 노드를 선택, 현재 이 두 노드가 서로 같은 그래프에 속하는 지를 판별하는 알고리즘이다. 2. 특징 합집합 찾기 union연산과 find연산으로 구성되어 있는 알고리즘으로 union : 여러 노드가 있는 경우, 특정 노드 2개를 연결하여 1개의 집합으로 묶는 연산 각 집합이 부모의 값을 얻어와서 한 쪽 부모가 다른 쪽 부모를 가리키게 만든다. (== 한개의 부모만 있는 집합을 만든다.) 주로 더 작은 쪽으로 합친다. a가 A의 요소이고 b가 B의 요소일 때, union(a, b)는 A U B를 뜻한다. find : 두 노드가 같은 집합에 속해 있는 지 확인하는 연산 A와 B의 부모를 구했을 때, 같은 부모를 가리킨다면 같은..
1. 탐욕 알고리즘이란 최적의 해를 구하기 위해 사용되는 알고리즘 여러 경우 중 하나를 결정해야할 때마다 매 순간 최적이라고 생각되는 경우를 선택하는 방식으로 최종 값을 구하는 방식이다. 매 순간 가장 탐욕스러운 선택을 해야 하며, 이전의 결정이 현재 결정에 영향을 미치지 않는다. 2. 탐욕 알고리즘의 수행과정 현재 상태에서 가장 최선인 해를 선택한다. 선택한 해가 전체 문제의 제약 조건을 벗어나지 않는지 검사한다. 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못하면 1로 돌아가서 반복한다. 3 탐욕 알고리즘의 한계 반드시 최적의 해를 구할 수 있는 것이 아니다. 그렇기 때문에 보통 근사치 추정에 활용하여 최적의 해에 가까운 값을 구하는 방법이다. 실제로 가장..
1. 구간 합이란 합 배열을 이용, 시간복잡도를 줄이는 특수한 목적으로 사용되는 알고리즘이다. 2. 합 배열의 정의 합 배열이란, 기존 배열의 합을 미리 구해놓는 전처리 배열이다. 합 배열을 미리 구해놓으면 구간합을 구할 때의 시간복잡도가 O(n)에서 O(1)로 줄어든다. sum[i] = a[0] + a[1] + ... + a[i - 1] + a[i] public static void main(String[] args) { int[] a = {15, 13, 10, 7, 3, 12}; int[] preSum = new int[a.length]; for (int i = 0; i < a.length; i++) { if(i == 0) preSum[i] += a[i]; else preSum[i] = preSum[..
1. 깊이 우선 탐색이란 맹목적 탐색 방법 중 하나로 연결된 노드(자식노드)를 따라서 계속 방문한 후 연결된 노드가 없을 경우, 이전 노드로 되돌아 다른 연결된 노드를 탐색하는 방 노드들의 자식들을 먼저 탐색하는 방식으로 스택을 활용한다. 스택을 사용하지 않고 재귀함수를 사용해서도 구현이 가능하다. 1) DFS의 흐름 스택에 시작노드를 담고 방문처리한다. 스택의 최상단을 확인한다. 최상단 노드와 연결된 노드 중 방문하지 않은 노드가 있으면 스택에 담고 방문 처리한다. 방문하지 않은 연결된 노드가 없으면 스택에서 제거한다. 2~4를 반복한다. 2. DFS 구현해보기 import java.util.*; public class DFSEx { public static void main(String[] args)..
1. 너비 우선 탐색이란 맹목적 탐색 방법 중의 하나로 시작 정점을 방문한 후, 한 노드와 같은 레벨에 있는 노드들을 먼저 탐색하는 방법으로 큐나 연결리스트를 활용한다. 인접한 모든 정점들을 우선 방문하는 방법으로 '큐'가 필요함 1) BFS의 흐름 배열 혹은 리스트 : 각 노드에 방문 했는지 여부를 담는다. 큐 혹은 리스트 : 해당 노드와 연결된 노드들을 담아둔다. 시작 노드를 큐에 담으면서 시작 + 시작 노드를 방문처리한다. 큐에서 노드를 하나 꺼낸다. 꺼낸 노드와 연결된 노드 중 방문하지 않은 노드를 방문한다.(연결된 노드를 큐에 담고 방문 처리) 큐에 노드가 없을 때까지 2~3을 반복한다. 시작 노드가 A일 경우 큐에 A를 담고 A를 방문처리한다. 담은 A를 꺼낸다. A와 연결된 B, C를 큐에 ..
1. 분할정복(Divide and Conquer)이란 여러 알고리즘의 기본이 되는 해결방법 엄청나게 큰 문제를 풀 수 있는 단위로 나눠서 각각을 해결한 후 다시 합병해서 문제의 답을 얻는 알고리즘을 말하는데 특정한 문제를 풀기위한 알고리즘이 아니라 문제 풀이 전략이다. 대표적으로 퀵정렬과 병합 정렬이 있다. 분할(divide): 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다. 정복(conquer): 분할한 문제를 해결한다. 조합(combine): 정복한 문제들을 합쳐서(조합하여) 원래 문제의 답을 얻는다. 2. 퀵정렬과, 병합정렬 외의 다른 분할정복의 예 public class Factorial{ public int factorialFunc(int data){ if(data
1. 순차탐색이란 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법이다. 1) 코드 import java.util.Arrays; public class LinearSearchEx { public static void main(String[] args) { int[] intArr = new int[10]; // 랜덤값으로 테스트 데이터 넣기 for (int i = 0; i < 10; i++) { intArr[i] = (int) ((Math.random() * 10) + 1); } System.out.println(Arrays.toString(intArr)); int result = linearSearch(intArr, (int)(Math.random() * 10 + 1)); ..
1. 힙 정렬 힙 트리구조를 이용하는 정렬방법으로 병합, 퀵 정렬만큼 빠른 알고리즘 힙 정렬을 이해하기 위해서는 이진 트리, 완전 이진 트리, 힙에 대해서 알고 있어야 한다. 1) 이진 트리(Binary Tree) 모든 노드의 자식 노드가 2개 이하인 노드 데이터를 표현할 때 각 노드에 담은 뒤 노드를 두 개씩 이어 붙이는 구조 2) 완전 이진 트리 데이터가 루트 노드부터 시작, 자식 노드가 왼쪽, 오른쪽 자식 노드로 차근차근 들어가는 구조 3) 힙 최소값이나 최대값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 하는 트리 최대 힙 : 부모 노드가 자식 노드보다 큰 힙 최소 힙 : 부모 노드가 자식 노드보다 작은 힙 → 아래와 같이 트리 안에서 특정 노드 때문에 최대 힙이 붕괴되는 경우가 있음 ⬇️ ..
