정렬

1. 정렬(Sort)

2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 순서 또는 그 반대 순서로 재배열하는 것이다.

오름차순(ascending)
= 작은 값 → 큰 값

내림차순(descending)
= 큰 값 → 작은 값

교재에서 소개하는 대표적인 정렬:

• 버블 정렬(Bubble Sort)
• 카운팅 정렬(Counting Sort)
• 선택 정렬(Selection Sort)
• 퀵 정렬(Quick Sort)
• 삽입 정렬(Insertion Sort)
• 병합 정렬(Merge Sort)

---

2. 버블 정렬

인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식이다.

1. 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다.
2. 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다.
3. 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.

시간 복잡도

O(n²)

---

정렬 과정 예시

55  7  78  12  42

첫 번째 패스
55와 7 비교  → 교환
55와 78 비교 → 유지
78과 12 비교 → 교환
78과 42 비교 → 교환

결과
7  55  12  42  78

한 번의 패스가 끝나면 가장 큰 값이 맨 뒤에 위치한다.

---

정렬 과정의 의사코드

BubbleSort(a, N)             # 정렬할 배열과 배열의 크기
    for i : N - 1 -> 1       # 정렬할 구간의 끝
        for j : 0 -> i - 1   # 비교할 왼쪽 원소의 인덱스
            if a[j] > a[j + 1]
                a[j] <-> a[j + 1]

---

정렬 과정의 코드

def bubble_sort(a, N):                       # 정렬할 List, N 원소의 수
    for i in range(N - 1, 0, -1):            # 정렬할 구간의 끝
        for j in range(i):                   # 비교할 왼쪽 원소 인덱스
            if a[j] > a[j + 1]:              # 왼쪽 값이 더 크면
                a[j], a[j + 1] = a[j + 1], a[j]  # 자리 교환

핵심

if a[j] > a[j + 1]:

인접한 두 값을 비교한다.

a[j], a[j + 1] = a[j + 1], a[j]

왼쪽 값이 더 크면 서로 자리를 바꾼다.

---

3. 카운팅 정렬

항목들의 순서를 결정하기 위해 각 항목이 몇 개씩 있는지 세는 작업을 하여 정렬하는 방식이다.

비교와 교환을 반복하는 버블 정렬과 달리, 각 값의 등장 횟수를 이용한다.

시간 복잡도

O(n + k)

• n : 리스트의 길이
• k : 정수의 최댓값

---

카운팅 정렬의 제한 사항

1. 정수나 정수로 표현할 수 있는 자료에 대해서만 적용할 수 있다.
2. 정수 항목을 인덱스로 사용하는 카운트 배열이 필요하다.
3. 카운트 배열을 위한 충분한 공간을 확보하려면 집합 내의 가장 큰 정수를 알아야 한다.

---

4. 카운팅 정렬 과정

예:

DATA = [0, 4, 1, 3, 1, 2, 4, 1]

1. 각 숫자의 발생 횟수 세기

처음:

INDEX   0  1  2  3  4
COUNTS  0  0  0  0  0

개수를 세면:

INDEX   0  1  2  3  4
COUNTS  1  3  1  1  2

코드:

COUNTS = [0] * 5

for x in DATA:
    COUNTS[x] += 1

핵심:

COUNTS[x] += 1

= 숫자 x가 등장할 때마다 x번 인덱스의 값을 1 증가시킨다.

---

2. COUNTS 누적

기존 COUNTS
1  3  1  1  2

누적 후
1  4  5  6  8

코드:

for i in range(1, k + 1):
    COUNTS[i] += COUNTS[i - 1]

누적값을 이용하면 해당 숫자가 정렬된 배열에서 어느 위치까지 들어가는지 알 수 있다.

---

3. TEMP에 실제 위치대로 저장

DATA를 뒤에서부터 확인하면서:

1. 해당 숫자의 COUNTS 값을 1 감소시킨다.
2. 감소한 값을 TEMP의 인덱스로 사용한다.
3. 해당 위치에 숫자를 저장한다.

for i in range(len(DATA) - 1, -1, -1):
    COUNTS[DATA[i]] -= 1
    TEMP[COUNTS[DATA[i]]] = DATA[i]
    

최종 결과:

TEMP = [0, 1, 1, 1, 2, 3, 4, 4]

---

5. 카운팅 정렬 의사코드

CountingSort(DATA, TEMP, k)

    COUNTS = [0] * (k + 1)

    # 1. 각 숫자의 등장 횟수 기록
    for i : 0 -> len(DATA) - 1
        COUNTS[DATA[i]] += 1

    # 2. 누적
    for i : 1 -> k
        COUNTS[i] += COUNTS[i - 1]

    # 3. 정렬된 위치에 저장
    for i : len(DATA) - 1 -> 0
        COUNTS[DATA[i]] -= 1
        TEMP[COUNTS[DATA[i]]] = DATA[i]

---

6. 카운팅 정렬 코드

def counting_sort(DATA, TEMP, k):
    # DATA   : 입력 배열
    # TEMP   : 정렬된 배열
    # COUNTS : 카운트 배열

    COUNTS = [0] * (k + 1)

    # 1. 각 숫자의 등장 횟수 기록
    for i in range(len(DATA)):
        COUNTS[DATA[i]] += 1

    # 2. COUNTS 누적
    for i in range(1, k + 1):
        COUNTS[i] += COUNTS[i - 1]

    # 3. TEMP에 정렬된 위치대로 저장
    for i in range(len(DATA) - 1, -1, -1):
        COUNTS[DATA[i]] -= 1
        TEMP[COUNTS[DATA[i]]] = DATA[i]

---

7. 카운팅 정렬 간단한 코드

정렬된 숫자만 필요하다면, 각 숫자의 개수를 센 뒤 그 개수만큼 append()하는 방식으로 이해할 수 있다.

def counting_sort(arr):
    max_value = max(arr)

    count = [0] * (max_value + 1)

    # 숫자별 등장 횟수
    for num in arr:
        count[num] += 1

    result = []

    # 작은 숫자부터 개수만큼 추가
    for i in range(len(count)):
        for _ in range(count[i]):
            result.append(i)

    return result

예:

arr = [0, 4, 1, 3, 1, 2, 4, 1]

결과:

[0, 1, 1, 1, 2, 3, 4, 4]

---

8. 버블 정렬 vs 카운팅 정렬

알고리즘	평균 수행시간	최악 수행시간	기본 방식
버블 정렬	O(n²)	O(n²)	비교와 교환
카운팅 정렬	O(n+k)	O(n+k)	비교환 방식, 등장 횟수 사용

구분

버블 정렬
= 옆의 값을 비교해서 자리 바꿈

카운팅 정렬
= 각 숫자가 몇 개인지 먼저 셈

---

완전 검색

9. 완전 검색(Exhaustive Search)

문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해 보고 확인하는 기법이다.

다른 표현:

Brute-force
Generate-and-test

특징

• 모든 경우를 확인하기 때문에 해답을 찾을 가능성이 높다.
• 경우의 수가 많아질수록 수행 속도가 느려질 수 있다.
• 문제를 처음 접했을 때 우선 완전 검색으로 접근한 뒤, 필요하면 더 효율적인 알고리즘을 고민할 수 있다.

---

10. Baby-gin과 완전 검색

6장의 카드가 주어질 때:

run

연속된 번호 3장이 존재하는 경우

예:

2 3 4

triplet

같은 번호 3장이 존재하는 경우

예:

7 7 7

6장의 카드가 run과 triplet만으로 구성된 경우 Baby-gin이라고 한다.

완전 검색 방식에서는:

가능한 순열 모두 생성
↓
앞 3장 검사
↓
뒤 3장 검사
↓
run / triplet 여부 확인

---

11. 순열(Permutation)

서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것이다.

표현:

nPr

계산:

nPr = n × (n-1) × (n-2) × ... × (n-r+1)

모두 뽑는 경우:

n! = n × (n-1) × ... × 2 × 1

---

12. 1, 2, 3의 모든 순열 만들기

for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1:
            for i3 in range(1, 4):
                if i3 != i1 and i3 != i2:
                    print(i1, i2, i3)

핵심은 이미 선택한 숫자를 다시 선택하지 않도록 조건을 검사하는 것이다.

---

탐욕 알고리즘

13. 탐욕 알고리즘(Greedy)

여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식이다.

각 단계에서 당장 가장 좋아 보이는 선택을 계속 이어가 최종 해답을 만든다.

---

14. 탐욕 알고리즘의 특징

1. 해를 구하는 데 사용되는 근시안적인 방법이다.
2. 각 선택 시점에서는 지역적으로 최적인 선택을 한다.
3. 이러한 선택을 계속 모아 최종 해답을 만든다.
4. 각 순간의 최적 선택이 항상 전체 문제의 최적해를 보장하는 것은 아니다.

---

15. 탐욕 알고리즘 과정

1. 해 선택

현재 상태에서 부분 문제의 최적해를 구하고 이를 부분 해 집합에 추가한다.

2. 실행 가능성 검사

새로운 부분 해 집합이 실행 가능한지 확인한다.

문제의 제약 조건을 위반하면 해당 선택을 버린다.

3. 해 검사

새로운 부분 해 집합이 문제의 해가 되는지 확인한다.

아직 전체 해가 완성되지 않았다면 다시 선택 단계부터 반복한다.

---

16. Baby-gin을 카운트 배열로 접근

6자리 숫자를 하나씩 분리해 COUNTS 배열에 개수를 저장한다.

num = 456789
c = [0] * 12

for i in range(6):
    c[num % 10] += 1
    num //= 10

핵심

num % 10

가장 오른쪽 숫자 하나를 가져온다.

num //= 10

가장 오른쪽 숫자를 제거한다.

---

17. triplet / run 검사

i = 0
tri = 0
run = 0

while i < 10:

    # triplet 확인
    if c[i] >= 3:
        c[i] -= 3
        tri += 1
        continue

    # run 확인
    if c[i] >= 1 and c[i + 1] >= 1 and c[i + 2] >= 1:
        c[i] -= 1
        c[i + 1] -= 1
        c[i + 2] -= 1
        run += 1
        continue

    i += 1

if run + tri == 2:
    print("Baby Gin")
else:
    print("Lose")

흐름

숫자별 개수 기록
↓
triplet이 있으면 3개 제거
↓
run이 있으면 연속된 3개 제거
↓
run + triplet 개수가 2인지 확인

---

18. Baby-gin에서 주의할 점

정렬한 뒤 앞의 3자리와 뒤의 3자리만 단순하게 잘라 확인하면 모든 경우를 해결하지 못할 수 있다.

따라서:

• 완전 검색으로 가능한 모든 경우를 확인하거나
• 카운트 배열을 활용하여 run과 triplet을 직접 검사하는 방법을 사용할 수 있다.