반응형 알고리즘58 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) - O(N logN) ▶ [그래프] 힙(Heap) 구조를 이용해서 정렬합니다. 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com ▶ 더 많은 예제: 힙 정렬 [예제] 힙 정렬 구현 Heap Sort ▶ Heap 구조가 궁금한 경우 [그래프] 힙(Heap) 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 zoosso.tistory.com 구현 ① 주어진 원소를 Heap.. 2021. 3. 6. Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Algorithm) 주어진 문제의 크기가 감당하기 어려운 경우 보다 작은 문제로 나누어 해결하는 방법(알고리즘) 이진검색, 퀵정렬, 합병정렬 등이 대표적인 예이다. ex) 원소 『41』 을 찾아가는 과정 이진 검색 과정 정렬된 데이터 배열 A[ ]가 주어지고 목표값(target)을 찾는다고 가정해보자. 이때, 첫 번째 원소의 인덱스는 low이고, 마지막 원소의 인덱스는 high 라고 하자. ① 현재 탐색 구간의 가운데 배열 번호(인덱스) mid 구한다. mid = (low.. 2021. 3. 6. 계수 정렬(Counting Sort) 계수 정렬(Counting Sort) → O(N) - 숫자가 등장한 횟수를 세서 그 기준으로 정렬하는 방법 - 정렬하는 숫자가 특정한 범위안에 있을 때 사용할 수 있습니다. + 메모리 낭비가 있을 수 있습니다. - 비교나 위치 교환 없이 정렬이 가능. 시뮬레이션 Array = [2, 4, 3, 0, 2, 3, 0, 3] ▷ 각 숫자의 등장 횟수 『 0 』 → 2번 『 1 』 → 0번 『 2 』 → 2번 『 3 』 → 3번 『 4 』 → 1번 구현 [C 언어 코드] #include void countingSort(int arr[], int n, int count[]) { for (int i = 0; i < n; i++) { count[arr[i]]++; } } void main() { int n = 8; .. 2021. 3. 6. LCP (Longest Common Prefix) LCP (Longest Common Prefix) LCP는 두 접미사의 최대 공통 접두사의 길이를 의미 ※ 앞서 접미사 배열(Suffix Array)에 대해서 알고 있어야 합니다. 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열. ex) S = "banana"에는 접미사가 총 6 개 있습니다. "banana", "anana", "nana", "ana", "na", "a" ▶Suffix.. zoosso.tistory.com ex) 문자열 S = "banana" Suffix Array에서 LCP(최대 공통 접두사)를 구하는 방법은 아래와 같습니다. ① 『a』 이전 값 존재 x → LCP[1] = x ② 『a』 와.. 2021. 3. 6. [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com ※ 이분 탐색할 때 보통 데이터가 정렬된 상태이어야 합니다. 예시 [BOJ] 2110 공유기 설치 [BOJ] 백준 2110 공유기 설치 출처: https://www.acmicpc.net/prob.. 2021. 3. 4. PS시 어떤 정렬을 선택하는 것이 좋을까? 어떤 정렬을 선택해야할까? 원소(숫자, 문자열)가 있을 때 정렬하는 기법은 여려가지 알려져 있습니다. ex) 단순히 두 원소를 비교해서 자리를 찾아가는 기본적인 Bubble Sort 시작해서 Quick Sort, Merge Sort ※ 정렬 알고리즘 비교 정렬 알고리즘 비교 시간 복잡도 비교 ▶ O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ) 정렬 알고리즘 시간 복잡도 특징 안전성은 주어진 배열 원소의 배치와 상관없이 구현 속도에 변함이 없는가를.. zoosso.tistory.com PS 하다보면 문제에서 여러 원소 중 가장 큰 값, 상위 1~10등, 오름/내림차순 순서를 요구할 때가 있습니다. 시간 제한 까다롭지 않다면 어떤 기법.. 2021. 3. 2. 합병 정렬(Merge Sort) Merge Sort 분할 정복(divide and conquer) 기법으로 만들어진 정렬 방법 → O(N * logN) - 1단계 분할(Divide) - 해결이 용이한 단계까지 문제를 분할해 나간다. - 2단계 정복(Conquer) - 해결이 용이한 수준까지 분할된 문제를 해결한다. - 3단계 결합(Combine) - 분할해서 해결한 결과를 결합하여 마무리한다. ※ 일반적으로 정렬할 자료의 양이 많으면 많을수록 정렬 수행시간은 기하급수적으로 길어져 많은 자룔르 한번 정렬하는 것 보다 적은 수의 자료를 여러 번 정렬 하는 것이 유리하다고 판단합니다. ex) { 6, 5, 3, 1, 8, 7, 2, 4 }를 병합정렬 하는 과정 시뮬레이션 [분할 과정] 재귀함수르 통해 크기가 = 1 (left >= right.. 2021. 3. 2. 연속된 부분 합(연속합) - 2 (Prefix Sum) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) Prefix Sum : psum[i] = 첫번째 원소부터 i 번째 원소까지의 구간 합 A[i] = psum[i] - psum[i-1] ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4 psum[]을 이용한 특정 구간 합 ▶ 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8 ↔ psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지의 합) .. 2021. 2. 28. 연속된 부분 합(연속합) - 3 (DP) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) DP ① D[i] = 인덱스 i를 오른쪽 끝으로 갖는 연속 구간의 최대값 ② D[i - 1] > 0인 경우는 활용하지만 D[i-1] ≤ 0 이라면 이용하지 않습니다. partialSum = Math.max(partialSum, 0) + A[i]; answer = Math.max(answer, partialSum); 즉, 배열을 순회하며 부분합이 0보다 작으면 이전의 부분 배열의 합은 무시하고 다시 순회한다고 보면됩니다. (※ patialSum = D[i] / answe.. 2021. 2. 28. 알고리즘 문제에서 시간 복잡도는 어떻게 하는걸까? (빅-오) 알고리즘 성능 알고리즘은 크게 시간과 공간을 통해 설명할 수 있다. 이 두 기준은 서로 상충하는 경우가 많다. 물론 더 빠르면서 메모리도 더 적게 사용하는 알고리즘이 있을 수 있지만, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄인 알고리즘들이 더 많이 존재한다. ex) 동적 계획법의 경우에도 더 많은 메모리를 사용해 알고리즘의 수행 속도를 높이는 경우가 많다. 프로그램의 실행 시간을 단순히 측정하는 것에는 한계가 있다. 왜냐하면 프로그래밍 언어, 하드웨어는 물론이고 운영체제, 컴파일러까지 수많은 요소에 의해 바뀔 수 있기 때문이다. 이런 외적 요인을 전부 동일하게 하더라도 어떤 문자열 구현을 사용했는지, 함수 인자를 어떻게 넘겼는지 등의 사소한 문제에 따라 프로그램의 최종.. 2021. 2. 28. 이전 1 2 3 4 5 6 다음 반응형
