분할 정복

박경린·2021년 3월 30일
0

분할 정복

목록 보기
1/1

목차

  1. 분할 정복 이란?
  2. 퀵 정령
  3. 합병 정렬
  4. 이진 탐색

1. 분할 정복이란?

문제를 해결하는 데 있어 주어진 자료를 있는 그대로 사용하는 것이 비효율적이거나 불가능할 경우, 주어진 자료를 분할하여 문제를 해결하는 방식입니다.
그렇기 때문에 분할 정복 알고리즘에서는 아래와 같은 과정들을 거치게 됩니다.
1. 현제 문제 해결이 가능한가? 를 검사하는 과정
2. 불가능할 경우 자료를 분할하는 과정

2. 퀵 정렬

분할 정복 을 기반으로 하는 정렬 알고리즘 으로 아래의 과정을 통해 진행됩니다.
1. 리스트 가운데의 원소 하나를 피벗으로 지정한다.

  1. 피벗을 기준으로 작은 원소, 큰 원소로 분할한다. 이 과정 이후 피벗은 움직이지 않는다.

  2. 위 과정을 분할된 리스트에서 재귀적으로 진행한다.

이후 리스트는 오름차순으로 정렬된 것을 확인할 수 있습니다.
이 알고리즘을 사용하기 위해서는 배열 사이의 위치를 변경할 수 있어야 하고 재귀개념 역시 능숙히 다룰 수 있어야 합니다.

3. 합병 정렬

비교 기반 정렬 알고리즘 입니다.
이것 역시 분할 정복 알고리즘의 일종으로 아래와 같은 과정을 통해 진행됩니다.
1. 정렬되지 않은 리스트를 1개의 원소를 가진 N개의 부분 리스트로 분할한다.

  1. 부분리스트가 다시 1개가 될 때까지 병합한다. 병합하는 과정에서 정렬을 진행한다.

4. 이진 탐색

이진 탐색을 진행하기 위해선 주어진 리스트가 정렬되어 있어야 하는 전제가 필요합니다.
1. 리스트의 가운데를 선택합니다.
2. 찾는 값을 선택한 값과 비교합니다.
3-1. 찾는 값 > 선택한 값 의 경우 오른쪽 리스트를 기준으로 재귀합니다.

3-2. 찾는 값 < 선택한 값 의 경우 왼쪽 리스트를 기준으로 재귀합니다.

3-3. 찾는 값 == 선택한 값 의 경우 답을 찾았습니다.

이진 탐색에는 찾는 값이 리스트 안에 존재해야 합니다.
그렇기 때문에 예시와 다르게 주로 연속된 리스트에서 특정한 값을 찾습니다.

profile
개발자 취준생 입니다.

0개의 댓글