Preparing Coding Test/Algorithm14 [자료구조/Java] 선택 정렬(Selection Sort) youtu.be/uCUu3fF5Dws 배열을 돌면서 작은 값부터 하나씩 앞으로 차곡차곡 옮기는 것 - 처음부터 끝까지 돌면서 가장 작은 값을 시작점의 숫자와 swap → 두번째부터 끝까지 돌면서··· - 시간복잡도 : O(n^2) 코드 public class Test{ private static void selectionSort(int[] arr){ selectionSort(arr, 0); } private static void selectionSort(int[] arr, int start){ if(start < arr.length-1){ int min_index = start; for(int i=start; i 2020. 8. 20. [자료구조/Java] 버블 정렬(Bubble Sort) youtu.be/YbsQiiubO74 앞에서부터 2개씩 비교해서 작은 것을 앞으로, 큰 것을 뒤로 보낸다. (제일 뒤부터 정렬된다) - 시간 복잡도 : O(n^2) 코드 public class Test{ private static void bubbleSort(int[] arr){ bubbleSort(arr, arr.length-1); } private static void bubbleSort(int[] arr, int last){ if(last > 0){ for(int i=1; i arr[i]){ swap(arr, i-1, i); } } bubbleSort(arr, last-1); } } private static void swap(int[] arr, int source, int target){ int .. 2020. 8. 20. [자료구조/Java] 병합정렬(Merge Sort) youtu.be/QAyl79dCO_k 1. 파티션이 낱개가 될 때까지 배열을 반으로 쪼갠다. 2. 두 배열을 잡아 작은 수부터 비교하고, 작은 것을 먼저 넣는다. 정렬이 완료되면 원래 배열의 자리에 복사한다. 3. (2의 반복) 정렬된 작은 배열을 병합한다. 과정) 각 배열의 가장 작은 수부터 비교하고 작은 것을 먼저 넣는다. n개만큼씩 logn번 돌기 때문에 시간복잡도는 O(nlogn) n번 호출, 1번 호출 당 검색해야 하는 데이터의 개수가 절반씩 줄어드니까 logn Merge Sort 는 실행시에 별도의 저장공간을 필요로 하기 때문에, 저장공간이 없다면 Quick Sort를 사용한다. 코드 public class Test{ private static void mergeSort(int[] arr){ .. 2020. 8. 19. [자료구조/Java] 퀵 정렬(Quick Sort) youtu.be/7BDzle2n47c 시간 복잡도 한 값을 기준으로(pivot) 왼쪽은 그보다 작은 것, 오른 쪽은 그보다 큰 것으로 정렬한다. 시간 복잡도는 평균적으로는 O(nlogn), 최악의 경우 O(n^2)이다. O(nlogn) - 배열이 1개가 될 때까지 계속 나눈다. (n번) - 나눌 때마다 데이터가 절반씩 줄어든다. (logn) O(n^2) - 정한 pivot이 맨 끝의 값만 선택할 경우이다. 코드 설명 pivot을 기준으로 start point인 s, end point인 e를 정한다. 변수 s - pivot보다 작을 경우 hold - pivot보다 클 경우, e가 pivot보다 작을 경우 swap - pivot보다 클 경우, e가 pivot보다 클 경우 e의 위치를 하나 앞으로 당긴다. (.. 2020. 8. 19. [자료구조/Java] Graph 검색 DFS, BFS 구현 https://www.youtube.com/watch?v=_hxFgg7TLZQ 따르고 싶은 유튜브 선생님이 생겼다.......... 1. BFS : 넓이 우선 탐색 1) Queue로 구현 가능 시작 노드 하나를 큐에 넣고 시작 → 큐에서 하나 꺼내고 → 해당 노드의 자식 노드들을 하나씩 큐에 넣음 → 처음에 넣은 노드를 출력 → (큐가 빌 때까지 반복) 2. DFS : 깊이 우선 탐색 1) Stack으로 구현 가능 스택에 노드를 하나 넣고 시작 → 스택에서 노드를 꺼내고 → 자식 노드들을 넣고 → 꺼낸 노드를 출력 → (스택이 빌 때까지 반복) 2) 재귀 호출로 구현 가능 노드에 방문하면 우선 출력 → 자식들을 재귀로 호출 내용 정리 import java.util.LinkedList; import jav.. 2020. 8. 14. 이전 1 2 다음