C2C Dev

정렬 알고리즘

 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

목차

1. 기본 정렬

1-(1) 버블 정렬 (Bubble Sort)

1-(2) 선택 정렬 (Selection Sort)

1-(3) 삽입 정렬 (Insertion Sort)

2. 심화 정렬

2-(1) 퀵 정렬 (Quick Sort)

2-(2) 병합 정렬 (Merge Sort)

2-(3) 기수 정렬 (Radix Sort)

3. 이진 탐색(Binary search)

1. 기본 정렬

• 1-(1) 버블 정렬 (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

print(bubble_sort([5, 3, 8, 4, 2]))

• 1-(2) 선택 정렬 (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

print(selection_sort([5, 3, 8, 4, 2]))

• 1-(3) 삽입 정렬 (Insertion Sort)

앞에서부터 차례로, 적절한 위치에 삽입하면서 정렬.

특징: 거의 정렬된 배열에 매우 빠름.  [시간 복잡도 : 평균 O(n²), 최선 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:  # key보다 큰 원소들을 뒤로 민다
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 3, 8, 4, 2]))

2. 심화 정렬

• 2-(1) 퀵 정렬 (Quick Sort)

*피벗(Pivot)을 기준으로 작은 값과 큰 값으로 분할하여 재귀적으로 정렬 ( *피벗 : 배열을 두 그룹으로 나누는 기준 값 )

특징: 평균적으로 가장 빠른 정렬 중 하나.  [시간 복잡도 : 평균 O(n log n), 최악 O(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)

print(quick_sort([5, 3, 8, 4, 2]))

• 2-(2) 병합 정렬 (Merge Sort)

배열을 반으로 나누고 각각 정렬 후 합병(Merge)

특징: 안정 정렬(Stable Sort). 항상 O(n log n)  [시간 복잡도 : 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
    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

print(merge_sort([5, 3, 8, 4, 2]))

• 2-(3) 기수 정렬 (Radix Sort)

자릿수를 기준으로 차례로 정렬 (보통 큐나 안정 정렬을 이용).

특징: 비교 기반이 아님. 특정 경우 매우 빠름.  [시간 복잡도 : O(d·n) ,d=자릿수 ]

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        index = num // exp
        count[index % 10] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

3. 이진 탐색(Binary search)

정렬된 배열에서 중앙값과 비교하며 절반씩 범위를 줄여 탐색.

조건: 반드시 정렬된 배열이어야 함. [시간복잡도 : 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  # 없는 경우

arr = [2, 3, 4, 5, 8]
print(binary_search(arr, 4))  # 2 (인덱스)
print(binary_search(arr, 7))  # -1 (없음)

마치며

다양한 정렬 들이 있다는 것을 정리하고

안정성과 시간복잡도가 적은 것은 병렬 정렬인 점을 알게 되었다. 

자료구조?

데이터를 효율적으로 저장하고, 관리하고, 처리하기 위한 구조

어떻게 담고, 꺼내고, 수정할지를 설계

필요한 이유?

▶ 효율성 : 같은 연산이라도 자료구조에 따라 속도가 다르다.

▶ 편리성 : 상황에 맞는 자료구조를 쓰면 코드가 단순해진다.

분류

선형 자료구조 (Linear)

1. 배열(Array)

• 인덱스를 이용해 O(1)로 접근 가능
• 하지만 크기가 고정되어 있고, 중간 삽입/삭제는 O(n)

1 - (1) 구간합 (= 누적합, Prefix Sum)

• 배열의 구간 합을 빠르게 계산하는 방법
• 미리 누적합 배열을 만들어두면 O(1)로 구간 합 계산 가능

1 - (2) 투 포인터 (Two Pointers)

• 두 개의 포인터(인덱스)를 움직이면서 문제 해결
• 정렬된 배열에서 두 수의 합, 부분 배열 문제 등에 자주 사용

1 - (3) 슬라이딩 윈도우 (Sliding Window)

• 일정한 크기의 창(윈도우)을 이동시키면서 연속된 부분 구간을 다루는 방식
• 예: 연속된 K개 원소의 최대합

2. 연결 리스트 (Linked List)

• 각 원소가 데이터 + 다음 노드 주소를 저장하는 구조
• 장점: 삽입/삭제 O(1) (포인터 변경만 하면 됨)
• 단점: 인덱스로 접근 불가 → 탐색 O(n)

3. 스택 (Stack)

• LIFO (Last In First Out) 구조 → 나중에 들어온 게 먼저 나감
• 주요 연산: push, pop, peek
• 주로 괄호 검사, DFS, 실행 취소 기능(Undo)

4. 큐 (Queue)

• FIFO (First In First Out) 구조 → 먼저 들어온 게 먼저 나감
• 주요 연산: enqueue, dequeue
• 주로 프로세스 스케줄링, BFS 탐색

5. 덱, 디큐 (Deque, Double-Ended Queue)

• 양쪽 끝에서 삽입/삭제 가능한 큐
• 스택+큐 기능을 모두 가짐
• 주로 슬라이딩 윈도우 최댓값 문제, 양방향 탐색

마치며

정처산기를 준비하면서 스택과 큐는 많이 본 것도 있고,

배열에서, 구간합이나, 투포인터, 슬라이딩 윈도우는 새롭게 느껴졌다.

다음에는 비선형도 이해하지

시간 복잡도

▶ 문제를 해결하는데 걸리는 시간과 입력의 함수 관계, 알고리즘이 입력 크기(n)에 따라 실행되는 데 걸리는 시간을 수학적으로 표현한 것

필요한 이유?

▶ 같은 문제를 풀더라도 알고리즘마다 속도가 다르다.

▶ 입력 데이터가 커질수록 실행 속도 차이가 커진다.

∴ 처리속도와 효율성, 최적화를 위해서 필요하다.

표기법

▶ 시간 복잡도는 빅오(Big-O) 표기법으로 표현

가장 빠르게 증가하는 항만 남기고 상수 계수는 무시합니다.

ex) 2n² + 6n + 10 → O(n²) 으로 표현

복잡도 이름 예시

배열 [1, 2, 3, ..., n]이 있다고 할 때:

• arr[0] 접근 → O(1) => n은 arr[0] 단 한개를 의미하므로 = 1
• arr 전체 순회 → O(n) => (1~n까지) n 전체를 의미
• 이중 for문으로 모든 쌍 확인 → O(n²) => 1~n * 1~n = n²
• 정렬 후 이진 탐색 → O(n log n) + O(log n) ≈ O(n log n)

위에 그래프만 봐도 O(n)까지는 서서히 올라가지만, 그 이상 부터는 급격하게 올라가는 것을 알 수 있다.

마치며

스터디를 위해서 시간복잡도에 대해서 개념을 알아봤다.

일단, 이러한 것이 있다는 걸 알고 스터디 진행하면서 다시 이해하자