728x90 알고리즘42 힙(heap)의 용용 : 우선순위 큐(priority queue) 우선순위 큐 - 최대 우선순위 큐 - 최소 우선순위 큐 최대 우선순위 큐 - INSERT(x) : 새로운 원소 x를 삽입 - EXTRACT_MAX() : 최대값을 삭제하고 반환 최소 우선순위 큐 - EXTRACT_MAX 대신 EXTRACT_MIN을 지원하는 자료구조 INSERT a) max heap의 형태 b) 아무 곳에 원소를 삽입하면 complete binary tree가 깨지기 때문에 삽입할 수 있는 위치가 정해져 있음, max heap property는 깨짐 c) heap property를 지키기 위해 부모노드와 현재 삽입된 노드를 교환함 INSERT 수도코드 - 새로운 원소를 삽입할 때 제일 마지막에 삽입해야 하므로 heap_size에 +1을 해준다. - 배열의 마지막 원소로 추가 - 현재 삽입.. 2021. 3. 1. Heap_sort(힙 정렬) [java] Heap_sort 개념 - 최대 힙 트리나 최소 힙 트리를 이용해 정렬을 하는 방법 - 최악의 경우 시간 복잡도 : O(nlogn) - 추가 배열이 불필요 - 이진 힙 자료구조를 사용 1. 정렬해야 할 n개의 요소들을 최대 힙을 만든다. - 최대 힙 - 완전 이진 트리 : 부모 노드의 가장 큰 값, 자식 노드에 작은 값으로 만든다. 2. 완전 이진 트리에서 루트의 값이 가장 큰 값 혹은 가장 작은 값이므로 배열에 정렬시키고 그 값은 다음 계산부터는 제외시킨다. ** Heap - complete binary tree - heap property 위 두 가지를 모두 만족해야 heap이라 할수 있다. complete binary tree : 마지막 레벨을 제외하면 완전히 꽉 차있고, 마지막 레벨에는 오른쪽부터.. 2021. 2. 28. quick_sort(퀵 정렬) [java] quick_sort 개념 - 앞서 설명한 merge_sort랑 마찬가지로 분할정복법을 사용하는 정렬이다. 분할 : 배열을 pivot을 기준으로 작은 값들은 왼쪽으로 큰 값은 오른쪽으로 나눈다. , pivot값은 맨 마지막 값으로 한다. 정복 : 각 부분을 순환적으로 정렬한다. ->partition 합병 : 정복하면서 정렬되므로 따로 합병을 해주지 않아도 된다. 분할 - partition을 통해 pivot의 위치를 리턴받고 그 값을 기준으로 두 개의 분할 메서드를 다시 호출한다. public static int[] quickSort(int[] base,int p,int r){ if(p 2021. 2. 25. merge_sort(합병 정렬)[java] merge_sort 개념 - 분할정복법을 사용하는 정렬이다. 분할정복법은 특정한 문제를 분할하고 그 부분을 정복하는 방법으로 문제를 해결한다. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 정복 : 각각의 작은 문제를 순환적으로 해결 합병 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함 위의 세가지 방식으로 merge_sort가 문제를 해결한다. * 중요한 점은 문제를 분할할 때 작은 크기의 동일한 문제가 되므로 새로운 알고리즘을 만들 필요가 없다. 그림을 첨부해 보았다.... 그림에서 처럼 우선 배열의 원소가 하나가 될때까지 분할을 하고 원소가 하나인 배열부터 비교하며 합병을 한다. 분할과 합병 모두 크기만 작아지거나 커질 뿐 방법이 달라지는 것이 아니다. 따라서 .. 2021. 2. 24. 기본적인 알고리즘 - selection sort selection sort 개념 - 배열중에 가장 큰 값을 찾고 맨 끝값과 바꾼다. 이제 맨 끝값은 생각하지 않아도 된다. 좀 더 쉽게 계획을 세우면 1. 가장 큰 값을 찾는다. 2. 맨 끝 값과 바꾼다. 3. 맨 끝 값을 제외하고 배열의 나머지 값들로 1,2번을 반복한다. 9 5 3 7 6 5 3 7 6 9 5 3 6 7 9 5 3 6 7 9 3 5 6 7 8 빨간색 - 가장 큰 값 노랑색 - 배열의 원소들을 비교할 때 생각하지 않아도 되는 부분 시간 복잡도를 생각해보자 배열의 원소가 n개일 경우 우선 모든 배열의 값들을 다 비교해야 하므로 n-1번 반복해야한다. 가장 큰 값을 찾아야 하는데 이는 위의 n을 기준으로 달라진다. 따라서 시간복잡도 T(n) = (n-1) + (n-2) + (n-3) + ... 2021. 2. 22. 캐시 교체 알고리즘 처음 쓰는 알고리즘 페이지!! 캐시 교체 알고리즘은 프로그래머스에서 문제를 풀다가 캐시 교체 알고리즘으로 풀라고 했을 때 공부하고 공부한 내용을 블로그에 올리면서 정리하면 좋겠다고 생각해서 이 글을 쓰게 되었다! 캐시 교체 알고리즘이란! - 가장 최근에 사용되지 않은 메모리를 지우는 것이다. 기본적으로 가장 오랫동안 사용되지 않았다면 앞으로도 사용되지 않을 것이라는 생각을 기본으로 한다. * cache hit - cache에 넣으려는 값이 cache에 있는 경우 * cache miss - cache에 넣으려는 값이 cache에 없는 경우 최종적으로 정리하면 1. 캐시에 없는 데이터가 들어온 경우 1. 캐시가 가득차있으면, 가장 오래된 데이터를 제거 후 캐시에 데이터를 넣는다. 2. 캐시에 공간이 있으면 .. 2021. 1. 23. 이전 1 ··· 4 5 6 7 다음 728x90
