[C++ - TIL] 삽입 정렬의 메커니즘과 유클리드 호제법의 재귀적 구현

🎮 주제 : 삽입 정렬의 메커니즘과 유클리드 호제법의 재귀적 구현

태그 : #C++ #알고리즘 #삽입정렬 #최대공약수 #유클리드호제법 #재귀함수

---

📌 학습 요약

• 삽입 정렬(Insertion Sort) : 두 번째 원소부터 시작하여 앞쪽의 정렬된 부분과 비교하며 자신의 위치를 찾아 "삽입"하는 정렬 방식으로, 거의 정렬된 데이터에서 매우 효율적인 성능 발휘
• 데이터 이동(Shifting) : 값을 교환(Swap)하는 대신 적절한 자리가 나올 때까지 기존 원소들을 한 칸씩 뒤로 밀어내는(Shift) 과정을 통해 연산 횟수 최적화
• 최대공약수(GCD) : 두 수 이상의 공통된 약수 중 최대값을 구하는 원리를 파악하고, 약수와 서로소의 개념 정립
• 유클리드 호제법 : $x$를 $y$로 나눈 나머지 $r$이 있을 때, $GCD(x, y) = GCD(y, r)$이라는 성질을 이용해 재귀적으로 해를 구하는 알고리즘 습득

---

🛠 주요 코드 및 구현 상세

1. 삽입 정렬(Insertion Sort) 핵심 구현

// i는 현재 정렬할 'key'를 선택하고, j는 정렬된 왼쪽 구간을 탐색
for (int i = 1; i < size; i++) {
    int key = list[i]; // 삽입할 대상 값 보관
    int j = i - 1;

    // key보다 큰 값들을 오른쪽으로 한 칸씩 밀어냄
    while (j >= 0 && list[j] > key) {
        list[j + 1] = list[j]; 
        j--;
    }
    // 적절한 위치를 찾으면 보관했던 key를 삽입
    list[j + 1] = key; 
}

2. 유클리드 호제법 (재귀 함수)

int Max(int x, int y) {
    int r = x % y;
    // 나머지가 0이면 나누는 수인 y가 최대공약수
    if (r == 0) return y;
    
    // (작은 수, 나머지)로 다시 함수 호출
    return Max(y, r);
}

---

✅ 주요 문법 및 개념 정리

개념 특징 주의 사항

삽입 정렬	최선의 경우 $O(n)$, 평균 $O(n^2)$	이미 정렬된 데이터에 매우 빠름
재귀 함수	자기 자신을 호출하여 문제를 분할함	종료 조건 누락 시 스택 오버플로우 발생
유클리드 호제법	나눗셈만으로 최대공약수를 빠르게 도출	큰 수를 $x$, 작은 수를 $y$로 두는 것이 기본
Shifting	list[j + 1] = list[j]	key를 덮어쓰지 않도록 미리 백업 필수

💡 알고리즘 인사이트 : 왜 j + 1인가?

• while 루프가 끝나는 시점에 j는 key보다 작거나 같은 값의 인덱스를 가리키거나 1이 됩니다.
• 따라서 key가 들어갈 자리는 그 바로 오른쪽인 j + 1이 됩니다.

---

✨ 느낀 점

• 삽입 정렬에서 변수 j의 변화에 따라 배열의 원소들이 옆으로 밀려나는 과정을 시뮬레이션하며 반복문의 정밀한 제어법을 익힘
• 복잡할 수 있는 최대공약수 계산을 유클리드 호제법과 재귀 함수를 결합해 단 몇 줄로 해결하는 논리의 간결함에 감탄함
• 재귀 함수를 작성할 때 종료 조건(r == 0)의 설정이 프로그램의 생존을 결정짓는 핵심임을 다시금 확인함
• 단순히 암기하는 것이 아니라 key라는 임시 저장소와 while문의 종료 조건을 연결하여 사고하는 훈련의 중요성을 느낌