알고리즘 기초 정리

목차

1. 배열 (Array)
2. 반복문과 재귀함수
3. 복잡도 (BigO, 시간, 공간)
4. 정렬 (Sorting)
5. 완전탐색 (Brute Force)

---

1. 배열 (Array)

개념

• 정의: 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 자료구조
• 특징:
  • 인덱스로 빠른 접근 가능 (O(1))
  • 크기가 고정적 (정적 배열의 경우)
  • 메모리 효율적 사용

Python에서의 배열 (리스트)

# 배열 생성
arr = [1, 2, 3, 4, 5]
arr2 = [0] * 10  # 크기 10인 0으로 채워진 배열

# 배열 접근
print(arr[0])    # 첫 번째 요소: 1
print(arr[-1])   # 마지막 요소: 5

# 배열 수정
arr[0] = 10
print(arr)       # [10, 2, 3, 4, 5]

# 배열 순회
for i in range(len(arr)):
    print(f"인덱스 {i}: {arr[i]}")

# 값으로 순회
for value in arr:
    print(value)

# 2차원 배열
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix[1][2])  # 6

---

2. 반복문과 재귀함수

반복문 (Iteration)

• 정의: 특정 조건이 만족될 때까지 코드를 반복 실행
• 종류: for문, while문

# for문 예제
def sum_array_iterative(arr):
    total = 0
    for num in arr:
        total += num
    return total

# while문 예제
def factorial_iterative(n):
    result = 1
    while n > 1:
        result *= n
        n -= 1
    return result

# 사용 예시
numbers = [1, 2, 3, 4, 5]
print(f"배열의 합: {sum_array_iterative(numbers)}")  # 15
print(f"5!: {factorial_iterative(5)}")               # 120

재귀함수 (Recursion)

• 정의: 함수가 자기 자신을 호출하는 프로그래밍 기법
• 구성요소:
  • 기저 조건 (Base Case): 재귀 호출을 멈추는 조건
  • 재귀 조건 (Recursive Case): 함수가 자신을 호출하는 부분

# 팩토리얼 재귀 구현
def factorial_recursive(n):
    # 기저 조건
    if n <= 1:
        return 1
    # 재귀 조건
    return n * factorial_recursive(n - 1)

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

# 하노이의 탑
def hanoi(n, start, end, temp):
    if n == 1:
        print(f"{start}에서 {end}로 이동")
        return
    hanoi(n-1, start, temp, end)
    print(f"{start}에서 {end}로 이동")
    hanoi(n-1, temp, end, start)

# 사용 예시
print(f"재귀 팩토리얼 5!: {factorial_recursive(5)}")
print(f"피보나치 7번째: {fibonacci(7)}")
hanoi(3, 'A', 'C', 'B')

---

3. 복잡도 (BigO, 시간, 공간)

시간 복잡도 (Time Complexity)

• 정의: 알고리즘의 실행 시간이 입력 크기에 따라 어떻게 증가하는지를 나타내는 척도

주요 시간 복잡도

• O(1): 상수 시간 - 배열 인덱스 접근
• O(log n): 로그 시간 - 이진 탐색
• O(n): 선형 시간 - 배열 순회
• O(n log n): 선형로그 시간 - 병합정렬, 퀵정렬
• O(n²): 제곱 시간 - 버블정렬, 선택정렬
• O(2ⁿ): 지수 시간 - 피보나치 재귀

# O(1) - 상수 시간
def get_first_element(arr):
    return arr[0] if arr else None

# O(n) - 선형 시간
def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

# O(log n) - 로그 시간
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# O(n²) - 제곱 시간
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

공간 복잡도 (Space Complexity)

• 정의: 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양

# O(1) 공간 복잡도 - 원본 배열을 수정
def reverse_array_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

# O(n) 공간 복잡도 - 새로운 배열 생성
def reverse_array_new(arr):
    return arr[::-1]

# O(n) 공간 복잡도 - 재귀 호출 스택
def sum_recursive(arr, index=0):
    if index >= len(arr):
        return 0
    return arr[index] + sum_recursive(arr, index + 1)

---

4. 정렬 (Sorting)

주요 정렬 알고리즘

버블 정렬 (Bubble Sort) - O(n²)

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

선택 정렬 (Selection Sort) - O(n²)

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

삽입 정렬 (Insertion Sort) - O(n²)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

병합 정렬 (Merge Sort) - O(n log n)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 0
    
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    result.extend(left[i:])
    result.extend(right[j:])
    return result

퀵 정렬 (Quick Sort) - 평균 O(n log n)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

---

5. 완전탐색 (Brute Force)

개념

• 정의: 가능한 모든 경우의 수를 체계적으로 탐색하는 알고리즘
• 특징:
  • 정확한 답을 보장
  • 구현이 간단
  • 시간 복잡도가 높음

주요 완전탐색 기법

1. 선형 탐색

def linear_search_all(arr, target):
    """배열에서 target과 같은 모든 인덱스를 찾기"""
    indices = []
    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)
    return indices

# 사용 예시
arr = [1, 3, 2, 3, 5, 3]
print(linear_search_all(arr, 3))  # [1, 3, 5]

2. 중첩 반복문을 이용한 완전탐색

def find_pair_sum(arr, target_sum):
    """배열에서 합이 target_sum인 모든 쌍 찾기"""
    pairs = []
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            if arr[i] + arr[j] == target_sum:
                pairs.append((arr[i], arr[j]))
    return pairs

# 사용 예시
numbers = [1, 2, 3, 4, 5]
print(find_pair_sum(numbers, 5))  # [(1, 4), (2, 3)]

3. 순열과 조합을 이용한 완전탐색

from itertools import permutations, combinations

def find_max_product_permutation(digits):
    """주어진 숫자들의 순열 중 가장 큰 곱을 가진 조합 찾기"""
    max_product = 0
    best_permutation = None
    
    for perm in permutations(digits):
        product = 1
        for digit in perm:
            product *= digit
        
        if product > max_product:
            max_product = product
            best_permutation = perm
    
    return best_permutation, max_product

def find_subset_sum(arr, target_sum):
    """부분집합의 합이 target_sum인 모든 조합 찾기"""
    result = []
    n = len(arr)
    
    # 모든 부분집합 생성 (2^n개)
    for i in range(1 << n):  # 2^n
        subset = []
        subset_sum = 0
        
        for j in range(n):
            if i & (1 << j):  # j번째 비트가 1인지 확인
                subset.append(arr[j])
                subset_sum += arr[j]
        
        if subset_sum == target_sum:
            result.append(subset)
    
    return result

# 사용 예시
digits = [2, 3, 4]
print(find_max_product_permutation(digits))

numbers = [1, 2, 3, 4]
print(find_subset_sum(numbers, 5))  # [[1, 4], [2, 3]]

4. 백트래킹을 이용한 완전탐색

def n_queens(n):
    """N-Queens 문제: N×N 체스판에 N개의 퀸을 서로 공격하지 않게 배치"""
    def is_safe(board, row, col):
        # 같은 열에 퀸이 있는지 확인
        for i in range(row):
            if board[i] == col:
                return False
        
        # 대각선에 퀸이 있는지 확인
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False
        
        return True
    
    def solve(board, row):
        if row == n:
            solutions.append(board[:])
            return
        
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # 백트래킹
    
    solutions = []
    solve([-1] * n, 0)
    return solutions

def generate_parentheses(n):
    """유효한 괄호 조합 생성"""
    def backtrack(current, open_count, close_count):
        if len(current) == 2 * n:
            result.append(current)
            return
        
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
    
    result = []
    backtrack("", 0, 0)
    return result

# 사용 예시
print(f"4-Queens 해의 개수: {len(n_queens(4))}")
print(f"3쌍 괄호 조합: {generate_parentheses(3)}")

완전탐색 최적화 기법

가지치기 (Pruning)

def optimized_subset_sum(arr, target_sum):
    """가지치기를 통한 부분집합 합 최적화"""
    arr.sort()  # 정렬로 가지치기 효과 증대
    result = []
    
    def backtrack(index, current_subset, current_sum):
        if current_sum == target_sum:
            result.append(current_subset[:])
            return
        
        if index >= len(arr) or current_sum > target_sum:
            return  # 가지치기
        
        # 현재 원소 포함
        current_subset.append(arr[index])
        backtrack(index + 1, current_subset, current_sum + arr[index])
        current_subset.pop()
        
        # 현재 원소 제외
        backtrack(index + 1, current_subset, current_sum)
    
    backtrack(0, [], 0)
    return result

# 사용 예시
numbers = [2, 3, 6, 7]
print(optimized_subset_sum(numbers, 9))

---

정리

언제 어떤 기법을 사용할까?

1. 배열: 순차적 데이터 저장이 필요할 때
2. 반복문: 단순하고 효율적인 반복 작업
3. 재귀함수: 문제를 작은 부분 문제로 나눌 수 있을 때
4. 정렬: 데이터를 정렬된 상태로 유지해야 할 때
5. 완전탐색: 최적해를 보장해야 하고 문제 크기가 작을 때

효율성 고려사항

• 시간 복잡도와 공간 복잡도의 trade-off 고려
• 입력 크기에 따른 알고리즘 선택
• 실제 데이터의 특성을 고려한 최적화