[C++ - TIL] 분할 정복의 원리와 효율적인 알고리즘 설계 전략

🎮 주제 : 분할 정복의 원리와 효율적인 알고리즘 설계 전략

태그 : #C++ #알고리즘 #분할정복 #에라토스테네스의체 #계수정렬 #재귀함수

---

📌 학습 요약

• 에라토스테네스의 체 고도화 : 2부터 $n$까지의 수 중 소수만을 남기기 위해 배수를 지워나가는 알고리즘을 구현하고, sqrt(n)까지의 검사만으로 충분한 최적화 원리 복습
• 계수 정렬(Counting Sort)의 간소화 : 수많은 if 조건문 대신 배열의 인덱스 연산(countList[list[i] - 1]++)을 활용하여 코드의 가독성과 처리 속도를 비약적으로 향상
• 분할 정복(Divide & Conquer) : 큰 문제를 작은 단위로 쪼개어 각각 해결한 후 결과를 합치는 전략을 이해하고, 이를 재귀 함수를 통해 배열의 최댓값을 찾는 로직에 적용
• 재귀적 범위 분할 : 중간값(mid)을 기준으로 범위를 [left, mid]와 [mid + 1, right]와 같이 명확히 나누어 중복이나 누락 없이 탐색하는 정교한 인덱스 관리 기법 습득

---

🛠 주요 코드 및 구현 상세

1. 계수 정렬의 인덱스 최적화

// 중복된 if문 대신 입력값을 인덱스로 직접 활용하여 빈도수 계산
for (int i = 0; i < size; i++) {
    countList[list[i] - 1]++; 
}

2. 분할 정복 기반 최댓값 찾기 (재귀)

int find(int list[], int left, int right) {
    // 기저 조건: 범위 내 원소가 하나뿐일 때
    if (left == right) return list[left];
    
    // 1. 분할(Divide): 중간 지점 계산
    int mid = (left + right) / 2;
    
    // 2. 정복(Conquer): 왼쪽과 오른쪽에서 각각 최댓값 탐색 (재귀 호출)
    int leftValue = find(list, left, mid);
    int rightValue = find(list, mid + 1, right);
    
    // 3. 결합(Combine): 두 값 중 큰 것을 선택하여 반환
    return (leftValue > rightValue) ? leftValue : rightValue;
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

에라토스테네스의 체	소수의 배수를 지워나가는 방식	0과 1은 소수가 아님을 반드시 처리
분할 정복	문제를 쪼개어 재귀적으로 해결	기저 조건(Base Case)이 없으면 무한 루프
정수 나눗셈	(left + right) / 2 수행 시 소수점 버림	원소 개수가 홀수여도 범위가 안전하게 나뉨
배열 초기화	int arr[5]{0};	모든 원소를 기본값(0)으로 초기화함

💡 재귀의 핵심 : 범위 설정

• 오른쪽 범위 탐색 시 mid가 아닌 **mid + 1*부터 시작해야 합니다.
• 이는 mid까지 이미 왼쪽 탐색 범위에 포함되었기 때문이며, 이를 통해 모든 원소를 빠짐없이 한 번씩만 검사하게 됩니다.

---

✨ 느낀 점

• 재귀 호출 시 변수 관리와 인덱스 범위 설정이 로직의 성패를 가르는 핵심임을 깊이 깨달음
• 소수 판별이나 계수 정렬처럼 최적화 여부에 따라 코드의 효율성이 극적으로 변하는 과정을 보며 설계의 중요성을 배움
• 복잡해 보이는 최댓값 찾기도 "반으로 나누어 각각 찾은 뒤 비교한다"는 단순한 분할 정복 논리로 명쾌하게 해결됨이 흥미로웠음
• 설명과 코드를 나란히 두고 단계별 실행 흐름(Stack Trace)을 추적하는 습관이 논리적 오류를 찾는 데 큰 도움이 됨을 느낌