🗒️ 분할 정복 (5)

1. 2022.06.29 [Python] 탐색(Search)

   탐색(Search) 탐색의 기본 개념 탐색(Search) : 어떤 집합에서 원하는 것을 찾는 것으로 검색이라고 한다. 탐색의 종류 순차 탐색(Sequential Search) 이진 탐색(Binary Search) 트리 탐색(Tree Search) 검색 결과로 특정 집합의 위치인 인덱스를 알려 준다. 검색에 실패하면(찾는 데이터가 집합에 없다면) -1을 반환하는 것이 일반적이다. 탐색 알고리즘의 종류 탐색은 데이터 상태에 따라 다양한 알고리즘을 사용할 수 있다. 탐색할 집합이 정렬되어 있지 않은 상태라면 순차 탐색을 해야 한다. 순차 탐색(Sequential Search) 순차 탐색은 처음부터 끝까지 차례대로 찾아보는 것으로, 쉽지만 비효율적인 탐색 방법이다. 하지만, 집합의 데이터가 정렬되어 있지 않다면..
2. 2021.06.07 선형 시간 선택(Linear Time Selection)

   선형 시간 선택(Linear Time Selection) 각 단계에서 문제를 2개 이상 분할하여 문제를 해결하는 알고리즘 ① 벡터 $V$가 주어지면, 여기서 i번째로 작은 원소를 찾으려고 함. ② 입력 벡터 $V$를 $V_{1}, V_{2}, V_{3}, ..., V_{n/5}$ 으로 분할함. 각각의 부분 벡터 $V_{i}$ 는 5개의 원소를 가지고 있음. 마지막 $V_{n/5}$ 는 5개 이하의 원소를 가질 수 있음. ③ 각각의 $V_{i}$ 를 정렬함. ④ 각각의 $V_{i}$ 에서 중앙값 $m_{i}$ 를 구하고, 이를 모아서 집합 M을 생성함. ⑤ 집합 M에서 중앙값 q를 찾음. ⑥ q를 피벗으로 삼아 전체 벡터 V를 L과 R의 두 벡터로 분할함. ⑦ 이러한 방식으로 분할하면 부분 벡터 L은 q보..
3. 2021.06.02 [C++] 퀵 정렬(Quick Sort)

   퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 정렬과 퀵 정렬의 비교 병합 정렬(Merge Sort) 대용량의 데이터 정렬 퀵 정렬(Quick Sort) 평균 실행 시간을 줄이는 것 기본 아이디어는 병합 정렬과 같음. 원본 입력 배열을 작은 크기의 부분 배열로 나눔. 각 부분 배열을 정렬함. 그 결과를 합쳐서 전체 정렬 배열을 생성함. 핵심 병합(Combine)이 아니라 분할(Split) 입력 배열이 주어지고, 입력 배열 중 피벗(Pivot) 원소 P를 선택했을 경우, 퀵 정렬을 위한 분할 연산 은 다음의 2단계로 이루어짐. ① 입력 배열을 2개의 부분 배열 R과 L로 나눔. L 입력 배열에서 P 보다 작거나 같은 원소를 포함하..
4. 2021.06.02 [C++] 병합 정렬(Merge Sort)

   병합 정렬(Merge Sort) 병합 정렬은 분할 정복(Divide and Conquer) 알고리즘 을 이용하여 구현됨. 병합 알고리즘은 다음과 같은 과정으로 정렬을 수행함. ① 많은 원소로 구성된 전체 집합을 작은 크기의 부분 집합 으로 나눔. ② 각각의 부분 집합을 정렬함. ③ 정렬된 부분 집합을 오름차순 또는 내림차순 순서를 유지함. ④ 각각의 부분 집합을 합침. 그림) 병합 정렬을 사용하여 정수 배열을 정렬하는 예 전체 배열을 여러 개의 부분 배열로 나누는 작업을 반복함. 각 부분 배열이 하나의 원소를 가질 때 멈춤. (1단계 ~ 4단계) 이후에는 다시 배열을 합치는 작업을 반복함. 합쳐진 배열의 원소 순서가 오름차순을 유지하도록 조정함. 코드 템플릿을 사용하여 정렬할 데이터 타입에 의존적이지 않..
5. 2021.05.29 [C++] 선형 탐색(Linear Search), 이진 탐색(Binary Search)

   선형 탐색(Linear Search), 이진 탐색(Binary Search) 선형 탐색(Linear Search) 시퀀스 전체 원소를 방문하면서 해당 원소가 N과 같은지 확인 다음과 같은 코드로 구현할 수 있음. bool linear_search(int N, std::vector& sequence) { for (auto i : sequence) { if (i == N) { return true; // 찾음! } } return false; } 장점 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작함. 단점 효율적이지 않음. 주어진 배열이 정렬되어 있다는 점을 전혀 이용하지 못함. 시간 복잡도 : O(N) 이진 탐색(Binary Search) 주어진 시퀀스가 정렬되어 있다는 사실을 이용하여 검색하는 방법 ..