J's tistory

🔎 문제선택 문제는 n개의 숫자들 중에서 k번째로 작은 수를 찾는 문제이다.이를 위해 몇 가지 간단한 해결 방법을 생각해 볼 수 있다.최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 해당 숫자를 제거한다.숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는다.하지만 위 경우는, 최악의 경우 $O(kn)$과 $O(nlogn)$ 수행 시간이 걸린다. 🔎 핵심 아이디어선택 문제는 숫자 찾기 문제이므로, 임의의 숫자를 효율적으로 찾을 수 있는 이진 탐색(Binary Search)에서 아이디어를 얻을 수 있다.📌 이진 탐색 (Binary Search) 이란?정렬된 입력의 중간에 있는 숫자와 찾고자 하는 숫자를 비교하여, 입력을 1/2로 나눈 두 부분 중에서 한 부분만 이어서 탐색한다. Sm..

🔎 퀵 정렬이란?퀵 정렬은 분할 정복 알고리즘으로 분류되지만, 사실은 정복 후 분할하는 과정이다.또한, 부분 문제의 수는 2개로, 각 부분 문제의 크기는 일정하지 않다. 💡 정렬 과정퀵 정렬은 피봇(pivot)이라고 하는 배열의 한 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 가운데 위치시킨다. 그다음 분할된 부분 문제들에 대해서도 똑같은 과정을 순환적으로 반복한다. ⚠️ 주의할 점이때 피봇은 분할된 왼편이나 오른편, 그 어느 부분에도 해당되지 않는다.  🔽 그림으로 이해하기위 그림을 보면 60이 피봇으로 선정되어, 60보다 작은 숫자들은 왼편으로, 60보다 큰 숫자들은 오른편으로 이동하였다. 이제 퀵 정렬 알고리즘에 대해 ..

🔎 합병 정렬이란?합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다. 즉, $n$개의 숫자들을 $n/2$개 씩 2개의 부분문제로 분할하고, 각각의 부분문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 다시 합병하여 정렬한다. 합병 과정이 문제를 정복하는 것이다. 합병(Merge)이란?합병은 2개의 각각 정렬된 숫자들을 하나의 정렬된 숫자들로 합치는 것이다. 🔽 다음은 각각 원소들이 정렬되어 있는 배열 A와 B를 합병하여 배열 C에 저장되어 있는 것을 보여준다. 🔎 합병 정렬 알고리즘MergeSort(A, p, q){ // 입력: A[p] ~ A[q] if(p  Line 3 : 정렬할 부분의 원소의 수가 2개 이상인 경우에만 ..

🔎 분할 정복 알고리즘이란?분할 정복 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하고, 이들의 해를 취합하여 원래 문제의 해를 얻는 방식이다.이때, 분할된 입력에 대한 문제를 부분문제(subproblem)라고 하고, 부분문제의 해를 부분해라고 한다.부분문제는 더 이상 분할할 수 없을 때까지 분할한다. 🔽 크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분문제의 크기가 $\frac{n}{2}$인 예시분할 과정은 다음과 같다.처음에 주어진 문제가 3개의 부분문제로 분할되고, 각 부분문제의 입력의 크기는 $\frac{n}{2}$이다.분할이 두 번 진행되면 부분 문제의 크기는 다시 각각 3개로 분할(총 ..