Log

1. 이전 집에서 RGB 중에서 선택한 색을 저장해놓는다. 2. 현재 집을 색칠할 때, 이전 집에서 선택한 색과 같지 않은 것 중 최소값인 색을 칠한다. → F[k] = F[k-1] + Min( 이전 집에서 선택한 색과 같지 않은 것들 ) 위에 처럼 하게되면 가장 작은 문제인 F(1)이 명확하지 않아진다는 문제가 생긴다... 그리고 현재의 선택이 최소값이더라도 전체의 해가 최소가 된다는 보장을 할 수 없다...ㅠ F[k][0] = Min(F[k-1][1], F[k-1][2] ) + RGB[k, 0]; F[k][1] = Min(F[k-1][0], F[k-1][2] ) + RGB[k, 1]; F[k][2] = Min(F[k-1][0], F[k-1][1] ) + RGB[k, 2]; 현재 집을 색칠할 때 RG..

접근방법을 아예 못 찾겠던 문제...! 거의 1시간 30분동안 멍 때리고 있었다...ㅋㅋ 원래 치즈 모양에서 (0, 7)의 c를 기준으로 팔방 탐색을 통해 c가 되는 좌표를 모두 찾아 bfs를 돌릴 생각이었는데... 도저히 c가 되는 좌표를 구하는 방법을 못찾았다... 알고 보니 치즈를 탐색하는 게 아닌 공기를 탐색하는 방법으로 접근했어야 했다. (0,0)을 기준으로 모든 공기를 탐색해 나가면서 주변에 치즈가 있으면 녹이는 방식... 그러면 치즈 내부의 구멍도 따로 생각 안 해도 되고...!! 설명 듣자마자 유레카 그 자체 그래프 탐색 꾸준히 공부해야지...허허 코드는 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import ja..

1. Arrays.sort() API를 확인해보면 Arrays.sort()는 Dual-Pivot Quicksort 알고리즘으로 구현되었다고 한다. Dual-Pivot Quicksort는 배열의 길이가 17보다 작으면 Insertion Sort를 수행하고, 아니면 두개의 pivot을 가지는 dual-pivot quicksort를 수행한다고 한다. 시간복잡도는 평균 O(n log n), 최악일 때는 O(n^2) 가진다. [참고] https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort 2. Collections.sort() Collections.sort()는 List.sort(..

정렬 알고리즘의 시간, 공간 복잡도 비교 1. 삽입정렬(Insertion Sort) public static void insertionSort(int[] arr) { for(int i = 1; i = 0 && arr[index] > curr) { arr[index+1] = arr[index]; index--; } arr[index+1] = curr; System.out.println(" " + Arrays.toString(arr)); } } 최선인 경우 : 이미 정렬이 된 상태일 때 - [ 1, 2, 3, 4, 5 ] while문의 arr[index] > arr의 조건만 확인하고,..

힙(Heap) : 완전 이진트리에서 다음을 만족하는 것을 말한다. 마디에 저장된 값은 순서를 매길 수 있는 원소이다. 각 마디에 저장된 값은 그의 자식마디에 저장된 값보다 크거나 같다. → 힙 성질(heap property) 힙 정렬 (Heap Sort) : 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법을 말한다. 힙 정렬 과정 초기배열의 상태가 위와 같다고 해보자. 배열을 완전 이진 트리로 그려보면 위와 같다. 위의 트리는 아직 힙은 아니므로 정렬을 통해 최대 힙을 만들어 볼 것이다. 가장 하위의 서브트리를 보면 3은 자식인 10보다 작고, 1은 자식인 8보다 작다. 따라서 3과 10, 1과 8을 교체하여 정렬한다. 그러면 가장 하위의 서브트리에 대해서는 힙이 완성되었다. 그 다음 루트의 왼..

부들부들....시간초과로 6번 실패하고 겨우 맞춘 문제... 문제만 읽고는 쉬운 편인 줄 알았는데... 우선 크레인의 무게 제한과, 박스들의 무게를 리스트에 저장 후 내림차순으로 정렬한 다음 제일 무거운 무게를 들 수 있는 크레인이 가장 무거운 박스를 못 들 경우에는 -1출력 후 프로그램 종료. 크레인이 j번째 박스를 들 수 있으면 리스트에서 삭제 크레인이 j번째 박스를 들 수 없으면 j++ 처음엔 크레인 리스트는 조회만 이루어지기 때문에 배열에 저장을 하였고, 박스 리스트는 삭제가 빈번하게 진행된다고 생각하여 LinkedList로 저장하였다. → BufferedReader + LinkedList 조합 → 실패!!! (아무래도 while - for - for 로 시간초과가 당연한...) 계속 틀리다가 ..

퀵정렬(Quick Sort) : 배열에서 하나의 값을 기준으로(pivot) 앞에는 기준값보다 작은 요소들, 뒤에는 기준값보다 높은 요소들이 오도록 정렬하는 알고리즘(분할정복) 리스트에서 하나의 원소를 고른다. → 기준값(Pivot), 원소를 고르는 기준은 따로 없다. 다만 보통 가운데 원소를 고르는 편. 기준값 앞에는 기준값보다 작은 원소들, 뒤에는 기준값보다 높은 요소들로 리스트를 두개로 나눈다.(분할) 분할된 리스트가 0 또는 1이 된다면 전체적으로 봤을 때 리스트는 정렬된 상태가 된다. 퀵 정렬 과정 퀵정렬 코드(Java) public static void quickSort(int start, int end, int[] arr) { int i, j, pivot; if(start < end) { pi..

합병정렬(Merge Sort) : 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할하고 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성하는 알고리즘 (분할정복 알고리즘) → 흔히 사용하는 2-way 합병정렬 정렬되지 않은 리스트를 2개의 부분리스트로 분할 (Divide) 부분리스트들의 원소가 1개일 때까지 분할 계속 진행 두개의 부분리스트를 하나의 정렬된 리스트로 합병한다. (Conquer) 최종 부분리스트가 1개가 될 때까지 합병 계속 진행 합병정렬 과정 합병정렬 코드(Java) public static void mergeSort(int start, int end, int[] arr) { if(end-start == 1) { // 부분리스트의 원소가..

1. 삽입정렬(Insertion Sort) : 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입하는 알고리즘 → i번째 데이터를 앞쪽 데이터와 비교하여 알맞은 자리에 삽입해주는 방법 8, 10, 9, 7, 3 위와 같은 배열이 있다고 하자. 모든 배열이 정렬이 안되어 있으므로 맨 앞이 아닌 두 번째 요소부터 확인을 한다. 8, 10, 9, 7, 3 두 번째 요소인 10은 첫 번째 요소 8과 비교를 하면 8의 오른쪽에 위치해야 하는 것이 맞으므로 위치를 변경하지 않고 그대로 내버려둔다. 10의 자리가 결정되었으므로 다음 요소를 정렬한다. 8, 10, 9, 7, 3 세 번째 요소인 9는 두 번째 요소 10과 비교를 하면 10의 왼쪽에 위치해야 하는 것이..