728x90 분류 전체보기138 힙(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. 프로그래머스 3단계 여행경로 [java] 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 [[ICN, JFK], [HND, IAD],.. 2021. 2. 20. 이전 1 ··· 19 20 21 22 23 다음 728x90
