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] 삽입 정렬은 작은 수에서만 효과적인 경우가 많습니다. 또한 이미 정렬되어 있는 배열에 새로운 원소를 집어 넣..

재귀를 통하여 배열의 합을 구하였다. sum 함수에 배열의 합을 구하기 위한 길이와 배열을 인자값으로 넣는다. n이 0이하이면 리턴을 해주고 그렇지 않으면 n이 0이 될때까지 배열을 더하여 출력을 한다.