26일차 알고리즘 기초4

정렬 알고리즘

1️⃣ 버블 정렬 (Bubble Sort)

• 정의: 인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 방식으로 정렬하는 알고리즘입니다.
• 동작 방식: 한 번 순회할 때마다 가장 큰 원소가 뒤로 이동하며, 이를 반복하여 전체 정렬을 수행합니다.
• 시간 복잡도:
  • 최선: O(n)
  • 평균: O(n²)
  • 최악: O(n²)
• 공간 복잡도: O(1)
• 특징:
  • 구현이 매우 단순함
  • 제자리 정렬(in-place), 안정 정렬(stable)

---

2️⃣ 선택 정렬 (Selection Sort)

• 정의: 전체에서 가장 작은 값을 선택해 맨 앞과 교환하는 방식으로 정렬하는 알고리즘입니다.
• 동작 방식: i번째 인덱스에 가장 작은 값을 찾아 교환 → 전체 n번 반복
• 시간 복잡도:
  • 최선: O(n²)
  • 평균: O(n²)
  • 최악: O(n²)
• 공간 복잡도: O(1)
• 특징:
  • 불안정 정렬
  • 간단하지만 비효율적

---

3️⃣ 삽입 정렬 (Insertion Sort)

• 정의: 이미 정렬된 부분과 비교하여 새로운 값을 적절한 위치에 삽입하는 방식입니다.
• 동작 방식: 두 번째 요소부터 시작해 앞쪽과 비교하며 적절한 위치로 삽입
• 시간 복잡도:
  • 최선: O(n)
  • 평균: O(n²)
  • 최악: O(n²)
• 공간 복잡도: O(1)
• 특징:
  • 안정 정렬
  • 거의 정렬된 배열에 매우 효율적

---

4️⃣ 힙 정렬 (Heap Sort)

• 정의: 힙 자료구조(최대 힙 또는 최소 힙)를 기반으로 한 정렬 알고리즘입니다.
• 동작 방식: 힙을 구성한 후 루트 노드를 추출하면서 정렬
• 시간 복잡도:
  • 최선: O(n log n)
  • 평균: O(n log n)
  • 최악: O(n log n)
• 공간 복잡도: O(1)
• 특징:
  • 불안정 정렬
  • 제자리 정렬
  • 우선순위 큐 구조 활용

---

5️⃣ 퀵 정렬 (Quick Sort)

• 정의: 피벗을 기준으로 분할 정복하여 정렬하는 효율적인 정렬 알고리즘입니다.
• 동작 방식: 피벗보다 작은 값/큰 값으로 분할 → 재귀적으로 정렬
• 시간 복잡도:
  • 최선: O(n log n)
  • 평균: O(n log n)
  • 최악: O(n²)
• 공간 복잡도: O(log n)
• 특징:
  • 매우 빠른 정렬
  • 불안정 정렬
  • 제자리 정렬

---

6️⃣ 병합 정렬 (Merge Sort)

• 정의: 배열을 반씩 나누고 정렬한 뒤 병합하는 분할 정복 기반의 정렬 알고리즘입니다.
• 동작 방식: 분할 → 정렬 → 병합
• 시간 복잡도:
  • 최선: O(n log n)
  • 평균: O(n log n)
  • 최악: O(n log n)
• 공간 복잡도: O(n)
• 특징:
  • 안정 정렬
  • 대량 데이터 처리에 적합
  • 외부 정렬로 자주 사용

---

7️⃣ 기수 정렬 (Radix Sort)

• 정의: 숫자의 자릿수를 기준으로 정렬하는 비교 기반이 아닌 정렬 알고리즘입니다.
• 동작 방식: LSD 방식(하위 자릿수부터 정렬) 또는 MSD 방식 사용
• 시간 복잡도: O(kN) (k: 자릿수, N: 데이터 개수)
• 공간 복잡도: O(n + k)
• 특징:
  • 안정 정렬
  • 정수/문자열 등 자릿수 기반 데이터에 유리
  • 비교 연산을 하지 않음

---

8️⃣ 계수 정렬 (Counting Sort)

• 정의: 각 숫자의 개수를 세어 그 순서를 결정하는 정렬 방법
• 동작 방식: 등장 횟수를 배열에 기록 → 누적합 계산 → 결과 배열에 삽입
• 시간 복잡도: O(n + k) (k: 값의 범위)
• 공간 복잡도: O(k)
• 특징:
  • 안정 정렬
  • 정수 데이터에 한정
  • 매우 빠르지만 메모리를 많이 사용

---

📊 정렬 알고리즘 비교 요약표

정렬 알고리즘	시간복잡도(평균)	공간복잡도	안정성	주요 특징
버블 정렬	O(n²)	O(1)	✅	구현 간단, 느림
선택 정렬	O(n²)	O(1)	❌	불안정, 직관적
삽입 정렬	O(n²)	O(1)	✅	거의 정렬된 경우 빠름
힙 정렬	O(n log n)	O(1)	❌	우선순위 큐 기반
퀵 정렬	O(n log n)	O(log n)	❌	평균 성능 우수
병합 정렬	O(n log n)	O(n)	✅	안정 정렬, 외부 정렬
기수 정렬	O(kN)	O(n + k)	✅	자릿수 기반, 매우 빠름
계수 정렬	O(n + k)	O(k)	✅	범위 좁은 정수에 유리

• ✅ : 안정 정렬 (Stable Sort) → 동일한 값의 원소 순서가 유지됨
• ❌ : 불안정 정렬 (Unstable Sort)

---

sort() vs sorted() 차이점

항목	sort()	sorted()
형태	리스트의 메서드	내장 함수
반환값	None 반환 (리스트를 직접 정렬)	정렬된 새 리스트 반환
원본 변경	✅ 원본 리스트가 변경됨	❌ 원본은 그대로, 새 리스트 생성
사용 대상	리스트만 사용 가능 (list.sort())	모든 iterable 사용 가능 (tuple, str 등)
속도	약간 더 빠름 (원본 정렬)	약간 느림 (새 객체 생성 비용 있음)

sort() 예시

nums = [3, 1, 4, 2]
nums.sort()
print(nums)  # 출력: [1, 2, 3, 4]

sorted() 예시

nums = [3, 1, 4, 2]
sorted_nums = sorted(nums)
print(sorted_nums)  # 출력: [1, 2, 3, 4]
print(nums)         # 출력: [3, 1, 4, 2]

---

브루트포스 알고리즘 (Brute Force)

• 정의: 가능한 모든 경우의 수를 전부 시도해보며 답을 찾는 방식
• 대표 예시: 완전 탐색, 순열, 조합, 비밀번호 대입, 부분집합 등
• 시간복잡도: 매우 높음 (보통 O(n!), O(2ⁿ) 등)
• 특징:
  • 가장 단순한 접근법
  • 구현은 쉬움
  • 작은 문제에 적합, 입력 크기가 커지면 급격히 비효율적
• 예시 문제:
  • 비밀번호 맞추기 (0000 ~ 9999 다 시도)
  • N명의 사람 중 3명 뽑는 모든 경우 확인

---

다익스트라 알고리즘 (Dijkstra)

• 정의: 가중치가 있는 그래프에서 출발 노드로부터 다른 모든 노드까지의 최단 거리를 구하는 알고리즘
• 전제 조건: 음의 가중치가 없는 그래프에서만 사용 가능
• 동작 방식:
  1. 출발 노드를 기준으로 거리 배열을 초기화
  2. 방문하지 않은 노드 중 최단 거리 노드를 선택
  3. 해당 노드를 거쳐 다른 노드로 가는 거리 갱신
  4. 모든 노드를 방문할 때까지 반복
• 자료구조: 우선순위 큐 (heapq)
• 시간복잡도:
  • 배열 구현: O(V²)
  • 우선순위 큐(힙) 사용: O(E log V)
• 특징:
  • 양의 간선 가중치만 가능
  • 빠르고 효율적
• 대표 문제: GPS 경로, 네트워크 지연 시간

---

벨만-포드 알고리즘 (Bellman-Ford)

• 정의: 음의 가중치가 존재할 수 있는 그래프에서의 최단 거리 계산 알고리즘
• 동작 방식:
  1. 모든 간선을 V-1번 반복하며 relax(완화) 연산 수행
  2. 마지막 반복 이후에도 업데이트가 일어나면 음의 사이클 존재
• 시간복잡도: O(V × E)
• 특징:
  • 음수 간선 허용
  • 음의 사이클도 탐지 가능
  • 다익스트라보다 느리지만 범용성은 더 높음
• 대표 문제:
  • 환율 차익(음의 사이클)
  • 도로 비용이 음수일 수 있는 지도

---

다이나믹 프로그래밍 (Dynamic Programming, DP)

• 정의: 큰 문제를 여러 작은 하위 문제로 나누고, 이전 결과를 저장하여 반복 계산을 줄이는 최적화 기법
• 전제 조건:
  • 중복되는 하위 문제가 존재해야 함
  • 최적 부분 구조가 있어야 함 (작은 문제의 최적해로 큰 문제의 최적해를 구할 수 있어야 함)
• 방식:
  • Top-Down (재귀 + 메모이제이션)
  • Bottom-Up (반복문으로 테이블 채우기)
• 시간복잡도: 문제에 따라 O(N) 또는 O(N×K) 등 다양
• 공간복잡도: 저장 테이블 크기만큼
• 특징:
  • 한 번 계산한 값을 재사용
  • 피보나치, 동전 교환, 배낭 문제 등에서 사용
• 대표 문제:
  • 피보나치 수열
  • 최소 비용 경로
  • 최장 공통 부분 수열 (LCS)

---

유니온-파인드 알고리즘 (Union-Find, Disjoint Set)

• 정의: 여러 개의 원소가 있을 때 서로 같은 집합에 속하는지 판별하고, 두 집합을 합치는 자료구조 및 알고리즘
• 주요 연산:
  • Find(x): x가 속한 집합의 대표(루트) 원소 찾기
  • Union(x, y): x와 y가 속한 두 집합을 합치기
• 활용:
  • 서로소 집합 관리
  • 사이클 판별, 네트워크 연결 여부
• 시간복잡도:
  • 일반적 구현: O(N)
  • 경로 압축(Path Compression) + 랭크 사용 시: O(α(N)) (거의 O(1))
• 특징:
  • 트리 기반의 빠른 집합 연산
  • 그래프 연결성, 크루스칼 알고리즘에 필수
• 대표 문제:
  • 친구 네트워크
  • 팀 결성
  • 최소 신장 트리 (MST)

---

📌 요약 표

알고리즘	목적/기능	장점	시간복잡도
브루트포스	모든 경우 탐색	단순 구현	O(n!), O(2ⁿ) 등
다익스트라	양의 가중치 최단 경로	빠름, 힙 사용 시 효율적	O(E log V)
벨만-포드	음의 가중치, 음의 사이클 탐지 가능	다익스트라보다 범용적	O(V × E)
다이나믹 프로그래밍	중복 문제 최적화	시간 절약, 재사용 가능	문제마다 다름
유니온-파인드	집합 판별, 병합	거의 O(1), MST에 필수	O(α(N))

자세한 코드는 깃허브