korean IT student

합집합 이란 - 서로 중복되지 않는 부분 집합들로 나눠진 노드들에 대해 저장하고 조작하는 알고리즘이다. ▼표를 보면 첫 번째 행은 노드 번호이고 두 번째 행은 노드들의 관계(부모 노드)를 의미한다. 아래와 같은 형식이라 보통 배열을 사용한다. ▼노드들이 그림과 같이 연결(Union)되어있다 가정 해보자. ▼노드들이 연결되면 갱신을 할때 작은값을 기준으로 갱신한다. ex) 1-2-3 -> 노드3은 2, 노드 2 는 1로 바꾼다. ▲위의 그림을 보면 노드들이 1-2-3, 4-5-6 연결되어 있다. ▼각각 같은 집단에 있으므로 '재귀 함수'를 사용하여 아래 그림과 같이 나타낸다. ▼ 코드로 나타내어 보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

깊이 우선 탐색(DFS, Depth-First Search) - 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 것이다. - 너비 우선 탐색에서는 큐가 사용되었다면 깊이 우선 탐색은 스택을 사용한다. ▼그림을 참고하자. ▼스택을 이용하여 노드를 담는다. ▼5번 노드까지 담고 3번 노드를 담기 위하여 다시 2번 노드까지 마지막에 담긴 순서대로 뺀다. 그렇게 1번 노드가 담긴 상태에서 3번 노드를 넣는다. 그림 순서대로와 같이 마지막에 선택된 노드의 인접한 방문하지 않은 노드를 방문한다. 방문하지 않은 노드가 없을 시 모든 노드를 스택에서 제거한다. 방문순서는 1-2-4-5-3-6이 된다.

너비 우선 탐색(Breath First Search, BFS) - 시작점에서 가까운 정점부터 순서대로 방문을 하는 탐색 알고리즘이다. 큐와 같이 사용된다. - 최단 경로를 구할 때 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있다. - 가까운 정점을 모두 저장해놓고 순서대로 방문해야 하므로 스택 구조는 구현이 어렵고 큐를 사용. 그림을 보며 이해를 해보자. 1에서 시작을 한다. 1은 큐에 저장 된다. 1에서 인접한 노드를 방문한다. 방문한 1은 큐에서 꺼내고 방문한적 없는 노드인 2, 3을 큐에 넣어준다. 방문한 2, 3 은 큐에서 꺼내고 방문한적없는 4, 5를 큐에 넣어준다. 모든 노드가 방문처리 되면 남은 노드들을 큐에서 꺼내준다. 큐에서 꺼낸 순서는 1, 2, 3, 4, 5..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 public class Main { static int[] sorted = new int[8]; public static void main(String[] args) { int[] arr = { 6, 5, 9, 8, 7, 4, 2, 1 }; mergeSort(arr, 0, arr.length - 1); for (int i = 0; i

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public class Main { public static void main(String[] args) { int[] arr = { 6, 5, 9, 8, 7, 4 }; quickSort(arr, 0, arr.length - 1); for (int i = 0; i 9보다 큰 숫자를 찾지 못해서 9로 돌아오고 작은 숫자는 4입니다. 둘이 교환합니다. { 6, 5, 4, 8, 7, 9 } -> 4보다 큰 숫자를 왼쪽에서 찾고 4보다 큰수를 오른쪽부터 찾는다. ..

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. [1, 2, 5, 4, 3] -> 첫 번째는 그대로 둡니다. [1, 2, 4, 3, 5] -> 두 번째도 오름차순으로 있어 그대로 둡니다. [1, 2, 5, 4, 3] -> 세 번째도 앞의 숫자보다 크기 때문에 그대로 둡니다. [1, 2, 5, 4, 3] -> 네 번째는 앞의 숫자 5보다 작기 때문에 앞으로 이동합니다. [1, 2, 4, 5, 3] -> 다섯 번째는 앞의 숫자 보다 작기 때문에 4 앞으로 이동합니다. [1, 2, 3, 4, 5] 삽입 정렬은 작은 수에서만 효과적인 경우가 많습니다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어 넣..

버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. - 오름차순으로 정렬을 한다면 처음 한바퀴 돌때 맨 뒤에는 가장 큰 값이 오게 된다. [1, 2, 5, 4, 3] -> 1, 2 순서가 정렬되어 있으니 그대로 둡니다. [1, 2, 5, 4, 3] -> 2, 5 순서가 정렬되어 있으니 그대로 둡니다. [1, 2, 5, 4, 3] -> 5, 4를 바꿔줍니다. [1, 2, 4, 5, 3] -> 5, 3을 바꿔줍니다. [1, 2, 4, 3, 5] -> 한 사이클이 끝났습니다. ..... -> 다시 처음부터 비교를 하여줍니다. [1, 2, 4, 3, 5] -> 4, 3을 바꿔줍니다. [1, 2, 3, 4, 5] -> 정렬 버블 정렬의 시간복잡도(위의 예제를 참고한다.) 1, 2, 3, 4 , 5, 6, ..

선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 선택 정렬의 시간복잡도(위의 예제를 참고한다.) 1, 2, 3, 4 , 5, 6, 7, 8, 9, 10 -> 데이터가 10개일때 총 몇번의 비교 연산을 해야할까. 10 + 9 + 8 + 7 ...... + 1 -> 총 비교 연산을 55번해야한다. -> 10*(10 + 1) / 2 데이터가 N개일때 -> N * (N + 1) / 2 (등차수열)