Algorithm
-
Quick Select를 O(n)에 구현 가능한 Median of Medians 알고리즘Algorithm 2021. 1. 3. 15:00
2jinishappy.tistory.com/124 Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘 Size가 n인 int형 Array에서 k번째로 작은 element를 찾는 방법은 여러 가지가 있다. 가장 formal하게, 배열을 sort한 뒤 인덱스가 k인 element를 반환하면 간단하게 구할 수 있다. 우리가 알고있는 Sort 알고 2jinishappy.tistory.com 이전 포스팅에서 배열에서 k번째로 작은 element를 찾아내는 Quick Select 알고리즘을 알아봤다. Quick Select를 진행하면서 선정한 pivot이 너무 작거나 크다면, partitioning이 제대로 이루어지지 않아 Worst-Case에 O(n²)이 소모됨을 확인했다 그렇기 때문에..
-
Array의 k번째 작은 element 찾기 - QuickSelect 알고리즘Algorithm 2021. 1. 1. 18:05
Size가 n인 int형 Array에서 k번째로 작은 element를 찾는 방법은 여러 가지가 있다. 가장 formal하게, 배열을 sort한 뒤 인덱스가 k인 element를 반환하면 간단하게 구할 수 있다. 우리가 알고있는 Sort 알고리즘의 시간 복잡도는 (효율적인 알고리즘 가정) O(n logn)인데, Sort 문제를 해결하면 손쉽게 Selection문제를 해결할 수 있다(이것을 Sort에서 Selection으로의 Reduction이 가능하다고 말한다) 그러면 Selection 문제는 O(n logn)내에 해결할 수 있는데, (이론적으로) 더 빠른 알고리즘이 있을까? Divide And Conquer를 활용하고, Quick Sort와 유사하게 pivot을 지정함으로써 size가 n인 Int형 Ar..
-
시간복잡도 Big-O(빅 오) 표기법Algorithm 2020. 12. 30. 23:34
PS 사이트에서 문제를 풀 때, 알고리즘을 공부할 때 우리는 특정 알고리즘의 시간복잡도를 나타낸다. 보편적인 문제를 풀 때 시간복잡도가 O(N^3)만 넘어가도 '비효율적'인 알고리즘을 사용한다고 지적하기도 한다. 시간 복잡도를 계산할 때, 단순히 for문이 몇 번 중첩되어 있는지? 재귀함수를 몇 번 호출했는지?에 따라 계산하기도 하지만 알고리즘이 복잡해질 경우에는 제대로 된 시간복잡도를 구하지 못할 수 있다 또는 코드가 아닌 정의만 보고 시간복잡도를 분석해야할 때도 있다 그렇기 때문에 시간복잡도를 나타내는 표준적인 방법인 Big-O Notation에 대해 알아본다 시간복잡도: 알고리즘의 수행 시간을 분석하는 방법 특정 문제를 해결하는 알고리즘은 여러 개가 존재할 수 있다. 해당 포스팅에서 다룬 것 처럼,..
-
Kadane's Algorithm(카다네 알고리즘) SubArray 최대합 구하기Algorithm 2020. 12. 29. 23:15
Maximum subarray problem이라는 문제가 있다 N개의 원소를 가진 배열이 있을 때, (i,j)의 연속되는 인덱스를 선택했을 때의 원소 최대 합을 구하는 문제이다 즉 [4, -2, 5, -4, 3, -7, -6, 10, 5]라는 배열이 있을 때 maximum subarray problem의 답은 7~8번째 원소값을 더한 15가 된다. 이 때 가능한 해결법은 약 세가지가 있다 1️⃣ 모든 인덱스 (i, j)에 대해 sum을 계산한 뒤 maximum값을 구한다 for(int i=0;i maxSum)maxSum = sum; } } 구간합을 구하기 위해 앞에서 구한 값을 활용해줬다. (i,j)의 구간 합 = (i,j-1)의 구간 합 + (j)의 원소 값인 점을 이용한다. 하지만 이 경우에도 시간복..
-
Divide-and-Conquer 알고리즘과 Master TheoremAlgorithm 2020. 9. 29. 00:10
Divide and Conquer는 분할 정복이라고 한다 구체적으로는 1️⃣ 주어진 문제를 작은 subproblem으로 쪼갠다 (subproblem이란? 본 문제와 같은 로직이지만, input size가 작은 문제) -> Divide 2️⃣ 나눈 subproblem들을 Recursively하게 해결한다 3️⃣ 2번에서 푼 subproblem들의 답을 적절하게 조합(combine, merge)해서 원래의 답을 도출한다 -> Conquer 분할 정복 알고리즘의 대표적인 예시로는 Merge Sort가 있다 위의 그림은 A라는 큰 배열을 작은 subproblem으로 나눈 것이다 한 번 나눌 때마다 input size는 2분의 1배가 되므로, divide하는데에는 O(log n)이 소모된다 첫 번째 사진에서 A7..
-
Quick Sort 정의, 알고리즘 및 코드에 대해Algorithm 2020. 5. 13. 18:38
Quick Sort란, Divide And Conquer 방식을 사용하는 정렬 알고리즘이다 Merge Sort와 함께 많이 쓰이면서, 시간 복잡도가 O(nlog n)으로 실용적이고 빠르다 🤗 1️⃣ Array의 Size가 1이면 해당 Array를 return 2️⃣ Size가 2 이상이면 pivot element를 하나 정한다 3️⃣ A1을 Array에서 pivot보다 작은 element, A2를 Array에서 pivot과 크기가 같은 element, A3를 A에서 pivot보다 큰 element를 담은 Array로 Divide한다 4️⃣ A1, A2, A3를 Quick Sort한 다음 return된 A1, A2, A3 순서대로 이어 붙인다(Conquer and Merge) 위와 같이 Divide 해준 ..