알고리즘 기초 : 분할정복, 병합정렬, 이진 탐색, 퀵 정렬 쉽게 이해하기

 

 

🦖 분할정복(Divide and Conquer)

오늘은 분할정복이라는 알고리즘에 대해 공부한 내용을 정리해보려 합니다. 분할정복은 문제를 작은 문제로 나누어 해결하는 방식인데, 어떻게 작동하는지, 그리고 이 방식이 어떤 장단점을 갖는지 공부해보겠습니다.

개념 정리

분할정복이란, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법입니다. 각 부분 문제의 답을 재귀 호출로 계산하고, 이 답을 모아 전체 문제의 답을 계산합니다. 쉽게 말해, 큰 문제를 작게 쪼개고, 이 작은 문제들을 해결해서 전체 문제를 해결하는 것이죠.

Divide and Conquer의 단계

• 분할(Divide): 문제를 더 이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눕니다.
• 정복(Conquer): 가장 작은 단위의 하위 문제를 해결합니다.
• 조합(Combine): 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합합니다.

💡 중요한 포인트는 분할(Divide)을 잘 설계하는 것이 전체적인 알고리즘의 효율성을 크게 향상시킨다는 것입니다.

🦖 장단점

장점

• 복잡한 문제를 작은 부분 문제로 나누어 쉽게 해결할 수 있습니다.
• 부분 문제들을 병렬 처리할 수 있어 시간 절약이 가능합니다.
• 코드가 간결하고 이해하기 쉽습니다.

단점

• 적합하지 않은 문제도 있어 활용 범위가 제한적입니다.
• 문제를 분할하고 결과를 합치는 과정에서 추가적인 시간과 메모리가 소요됩니다.
• 재귀 호출로 인해 스택 오버플로우의 위험성이 있습니다.

🦖 예시

1. 분할 (Divide)

예를 들어, 일주일 동안의 운동 계획을 분할정복 방식으로 나누어 봅시다. 운동을 한 번에 모두 계획하기보다, 요일별로 나눠서 계획하는 것입니다.

• 월요일: 유산소 운동
• 화요일: 등, 어깨 운동
• 수요일: 휴식
• 목요일: 하체 운동
• 금요일: 가슴, 팔 운동
• 토요일: 유산소 운동
• 일요일: 휴식

2. 정복 (Conquer)

이제 각각의 운동 요일에 해당하는 운동을 집중적으로 수행합니다. 예를 들어, 월요일에는 유산소 운동에 집중하여 최대한 빠르고 효과적으로 운동을 수행합니다.

3. 조합 (Combine)

일주일 동안 다양한 운동 부위를 균형 있게 다루면서 최상의 운동 효과를 얻을 수 있습니다.

---

🦖 병합정렬 (Merge Sort)

병합정렬은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열을 두 개로 만든 뒤, 각각을 정렬하고 합치는 방식으로 전체 수열을 정렬하는 알고리즘입니다.

병합정렬의 단계

1. 리스트를 두 개의 리스트로 분할합니다.
2. 분할된 리스트를 정렬합니다.
3. 정렬된 두 개의 리스트를 하나의 정렬된 리스트로 결합합니다.

일상 예시: 옷장 정리

• 분할 (Divide): 옷장 속의 옷을 상의와 하의로 나눕니다.
• 정복 (Conquer): 각 그룹 내에서 옷을 정리합니다. 상의 그룹에서는 티셔츠, 셔츠 등을 정리하고, 하의 그룹에서는 바지, 스커트 등을 정리합니다.
• 결합 (Combine): 정리된 옷들을 다시 합쳐서 옷장에 정리합니다.

---

🦖 이진 탐색 (Binary Search)

이진 탐색은 ‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘입니다. 탐색 범위를 절반씩 줄여나가기 때문에 선형 탐색에 비해 빠른 속도를 보장합니다.

 

 

이진 탐색 수행 과정

1. 배열의 ‘중간 값’을 선택하여 찾고자 하는 값과 비교합니다.
2. 만약 중간 값이 찾고자 하는 값보다 크면 ‘배열 왼쪽 부분'에서, 값보다 작으면 ‘배열 오른쪽 부분'에서 탐색을 진행합니다.
3. 이 과정에서 찾고자 하는 값이 나올 때까지 반복합니다.

일상 예시: 전화번호부 정렬

• 전화번호부 정렬 (Sort): 먼저 전화번호부의 번호들을 숫자 크기 순으로 정렬합니다.
• 중앙값 선택 (Choose Midpoint): 전화번호부를 반으로 나누고, 중앙에 있는 번호를 선택합니다.
• 비교 (Compare): 선택한 번호와 찾으려는 번호를 비교합니다.
• 탐색 (Search): 찾으려는 번호가 중앙값과 같은지 확인하고, 같지 않다면 선택한 부분의 절반을 버리고, 남은 부분에 대해 다시 중앙값을 선택하고 비교를 반복합니다.

---

🦖 퀵 정렬(Quick Sort)

퀵 정렬은 배열을 피벗을 중심으로 두 부분으로 나눠서 정렬하는 알고리즘입니다. 이 알고리즘은 피벗을 기준으로 배열을 두 개의 서브 배열로 분할하고, 각각을 정렬한 후 결합하는 방식으로 작동합니다.

퀵 정렬 수행 과정

1. 배열에서 피벗(pivot, 특정한 값)을 선택합니다.
2. 피벗을 기준으로 배열을 두 개의 서브 배열로 분할합니다. 피벗보다 작은 값은 왼쪽 서브 배열에, 큰 값은 오른쪽 서브 배열에 위치시킵니다.
3. 각 서브 배열을 재귀적으로 퀵 정렬합니다.
4. 정렬된 서브 배열들을 합칩니다.

일상 예시: 할 일 목록

• 분할 (Divide): 할 일 목록을 우선적으로 처리해야 할 일과 나중에 처리할 일로 나눕니다.
• 정렬 (Conquer): 나눈 두 그룹 내에서 할 일을 빠르게 정렬합니다. 높은 우선순위의 할 일 그룹에서는 급한 일부터 우선순위가 높은 순서대로 정렬하고, 낮은 우선순위의 할 일 그룹에서는 순서대로 정렬합니다.
• 결합 (Combine): 정렬된 높은 우선순위의 할 일 그룹과 정렬된 낮은 우선순위의 할 일 그룹을 합쳐서 하나의 정렬된 할 일 목록으로 만듭니다.