Code IT/Data-Structure11 [자료구조] Quick Sort 퀵정렬 (left/rightmost, middle pivot) quick sort 퀵정렬: 피벗(중심) 값을 설정하고, 그 값보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보낸다. 그 후 피벗 값을 중간으로 옮겨주기. 피벗을 보통 맨 앞 값으로 설정한다. 그 방법이 (leftmost) 마지막 값으로 설정 시 (rightmost) 중간 값으로 설정 시 (middle) public class QuickSort { public void sort(int[] nums, int start, int end, int howpivot) { int lefti = start; int righti = end; int pivoti = findpivot(nums, start, end, howpivot); /****** leftmost ******/ if (howpivot == 0).. 2021. 4. 3. [자료구조] Merge Sort 합병정렬 (iterative 반복, recursive 재귀) merge sort 합병정렬 : 배열을 반으로 싹둑 잘라 2개 - 4개 - 8개... 씩 서로 비교하며 그때그때 정리한다, 배열의 길이가 n면 n만큼의 추가 메모리가 필요. 반복을 사용하는 것과 재귀 사용의 차이. public void iterativeMergeSort(int[] nums) { int left = 0; // left의 시작 인덱스 int right = 0; // right의 시작 인덱스 int end = 0; // right의 마지막 인덱스 for (int size = 1; size = nums.length) { // left와 right의 배열 크기가 같지 않을 때 if (right >= nums.length) right = left; // right 배열이 아예 없는 경우 end .. 2021. 4. 3. [자료구조] Dynamic Programming 동적 계획법 Dynamic Programming/ Dp/ 동적 계획법 : 복잡한 문제를 단순한 작은 문제들로 나누고 반복적인 계산을 통해 최적해를 찾는 방법. * 아래와 같은 키워드 사용 1. 분할과 정복 Divide and Conquer 2. 재사용 Reuse - '함수의 재사용, 메모이제이션 통한 계산 결과 재사용 등등' 에서의 재사용을 의미하는 듯. 3. 효율성 - 공간적 Memory Intensive 4. 효율성 - 시간적 Speedy *메모이제이션 Memoization : 결과값을 저장하여 이후 계산에 계속 사용하는 것. 중복 계산이 없도록 함. (피보나치 계산 시 계속 첫 값부터 재귀 시키는 것은 단순한 재귀, 시간도 오래 걸리며 효율이 떨어진다. 배열 잡아주고 결과값을 계속 저장하며 필요시에 불러.. 2021. 4. 3. [자료구조] Shortest Path 최단 경로 알고리즘, Dijkstra Algorithm 다익스트라 알고리즘 Dijkstra 다익스트라 알고리즘 : 최단 경로 / 최소 비용으로 가는 알고리즘, 양의 간선 사용 *중요한 부분: dist[i] = dist[i] i의 최소 경로 갱신. '이전 방문노드의 최소 경로 + 이전 방문노드에서 i로 가는 비용' 과 현재 저장되어 있는 i의 최소 경로 중 더 적은 값을 택하여 i의 최소 경로로 설정. 나는 좀 이상하게 푼 것 같지만.. 최소 힙을 사용하면 더 수월하게 풀 수 있다. 갈 수 있는 경로들 중 가장 적은 값을 빼내서 저장하는 ? public static void Dijkstra(String vertex[], int.. 2021. 4. 3. 이전 1 2 3 다음
