알고리즘 정리 및 재귀 호출

정렬 알고리즘(Sorting Algorithms)

컴퓨터 과학에서 정렬 알고리즘은 목록의 요소를 순서대로 배열하는 알고리즘입니다. 가장 자주 사용되는 순서는 숫자 순서, 사전 순서, 그리고 오름차순 또는 내림차순입니다. 효율적인 정렬은 입력 데이터가 정렬된 목록에 있어야 하는 다른 알고리즘의 효율성을 최적화하는 데 중효합니다. 또한 정렬은 데이터를 정규화하고 사람이 읽을 수 있는 출력을 생성하는 데에도 유용합니다.

 

두 가지 조건 만족(모든 정렬 알고리즘)

1. 출력은 단조로운 순서로 출력됩니다.(각 요소는 요구되는 순서에 따라 이전 요소보다 작서나 크지 않습니다.)
2. 출력은 입력의 순열(원래 요소는 모두 유지하면서 순서를 바꾸는 것)입니다.

일부 알고리즘은 순차적 접근을 위해 설계되었지만, 가장 성능이 좋은 알고리즘은 데이터가 임의 접근을 허용하는 데이터 구조에 저장되어 있다고 가정합니다.

 

버블 정렬 (Bobble Sort)

정의

인접한 두 원소를 비교하여 정렬하는 방식으로, 가장 큰 값이 배열 끝으로 "거품처럼" 올라가는 알고리즘

동작원리

배열을 순회하면서 인접한 원소들을 비교하고, 순서가 잘못되어 있으면 교환합니다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 각 패스마다 가장 큰 원소가 맨 뒤로 이동
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 예제
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"정렬 전: {numbers}")
sorted_numbers = bubble_sort(numbers.copy())
print(f"정렬 후: {sorted_numbers}")

 

삽입 정렬 (Inserrtion Sort)

정의

배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 부분의 원소를 정렬된 부분의 적절한 위치에 삽입하는 알고리즘

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # key보다 큰 원소들을 한 칸씩 뒤로 이동
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 예제
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"삽입 정렬 결과: {insertion_sort(numbers.copy())}")

 

선택 정렬(Selection Sort)

정의

 

배열에서 최솟값을 찾아 맨 앞의 원소와 교환하는 과정을 반복하는 알고리즘

def selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        # 최솟값의 인덱스를 찾기
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 최솟값과 현재 위치 교환
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# 예제
numbers = [64, 34, 25, 12, 22, 11, 90]
print(f"선택 정렬 결과: {selection_sort(numbers.copy())}")

---

재귀 호출(Recursion)

정의

함수가 자기 자신을 호출하는 프로그래밍 기법

동작 원리

기저 조건(base case)과 재귀 조건(recursive case)으로 구성되며, 문제를 더 작은 하위 문제로 분해하여 해결합니다.

# 팩토리얼 계산
def factorial(n):
    # 기저 조건
    if n <= 1:
        return 1
    # 재귀 조건
    return n * factorial(n - 1)

# 피보나치 수열
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# 재귀 호출 1000번 예제 (스택 깊이 증가)
import sys
sys.setrecursionlimit(1500)  # 재귀 한계 설정

def recursive_count(n):
    if n <= 0:
        return "완료!"
    print(f"재귀 호출 {n}번째")
    return recursive_count(n - 1)

# 예제
print(f"5! = {factorial(5)}")
print(f"피보나치 7번째: {fibonacci(7)}")
# recursive_count(1000)  # 1000번 재귀 호출