[알고리즘]중간고사 대비 정리
[알고리즘]중간고사 대비 정리
중간고사 요약
[시험 예상 정리 요약집]
알고리즘의 특성
- 정확성
- 수행성
- 유한성
- 효율성
알고리즘의 표현
- 의사코드
- 흐름도
문제해결 방식에 따른 분류
- 분할정복 알고리즘 → 주어진 문제의 입력을 분할하여 문제를 해결하는 방식
- 탐욕 알고리즘 → 매 선택에서 해당 순간에 가장 최적인 답을 선택하여 문제를 해결하는방식
- 동적계획 알고리즘
- 근사 알고리즘
- 백트래킹 기법
- 분기한정기법
문제에 기반한 분류
- 정렬 알고리즘
- 그래프 알고리즘
- 기하 알고리즘
특정 환경에 따른 분류
- 병렬 알고리즘
- 분산 알고리즘
- 양자 알고리즘
시간복잡도의 정의
- 시간 복잡도는 알고리즘이 수행하는 기본적인 단위 연산의 횟수를입력 크기에 대한 함수로 표현
복잡도를 표현하는 방법
- 최악 경우 분석
- 평균 경우 분석
- 최선경우 분석
→ 보통은 worst case 분석으로 복잡도를 표현
점근적 표기법
- 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
빅오-표기법 - 상한(upper bound)
다항식에서 최고 차수 항만을 취한뒤, 그 항의 계수를 제거하여 g(n)을 정한다.
- 세타 표기법 - 하한 표기
- 빅 오메가 표기법
Ⅰ. 알고리즘의 효율성
시간복잡도 (Time Complexity)
- 연산 횟수가 입력 크기 n에 따라 얼마나 증가하는지 측정
- 최악 (Worst-case): 항상 보장해야 함
- 평균 (Average-case): 확률 기반
- 최선 (Best-case): 가장 이상적 상황
공간복잡도 (Space Complexity)
- 알고리즘 수행에 필요한 메모리 공간의 양
O-표기법 (Big-O)
- 최악의 수행시간 표현
- 차수가 높은 항만 남김
빅세타(Θ), 빅오메가(Ω)
- Θ: 평균 또는 정확한 성장률
- Ω: 최선의 경우 하한
자주 사용되는 수행 시간
| 표현 | 의미 |
|---|---|
| O(1) | 상수 시간 - 매우 빠름 |
| O(log n) | 로그 시간 - 이진 탐색 |
| O(n) | 선형 시간 |
| O(n log n) | 대표적인 효율적 정렬 |
| O(n²) | 이중 루프 |
| O(2ⁿ), O(n!) | 비효율적인 알고리즘 |
Ⅱ. 루프 시간복잡도
| 구조 | 복잡도 예시 |
|---|---|
| 단일 루프 | O(n) |
| 중첩 루프 | O(n²), O(n³) |
| 이진 나누기 루프 | O(log n) |
| 분할정복 루프 | O(n log n) |
Ⅲ. 분할정복 알고리즘
정의
- 문제를 작게 나눠서 푼 후 합치는 알고리즘
특성
- 재귀적
- 정복 단계에서 결합 필요
문제 해결 단계
- 분할(Divide)
- 정복(Conquer)
- 결합(Combine)
기본 아이디어
- 더 이상 나눌 수 없을 때까지 나눠서 각각 해결하고 다시 합친다.
점화식 예시
- T(n) = 2T(n/2) + O(n) → O(n log n)
합병정렬(Merge Sort)
- 알고리즘: 반씩 나눠 재귀정렬 후 병합
- 시간복잡도: O(n log n)
- 장점: 안정정렬, 시간 보장
- 단점: 추가 메모리 O(n) 필요
- 응용: 외부정렬, 연결리스트 정렬
Ⅳ. 퀵정렬(Quick Sort)
기본 아이디어
- 피봇을 중심으로 작고 큰 값을 양쪽으로 분할
- 재귀적으로 정렬
특징
- 불안정 정렬
- 평균적으로 매우 빠름
시간복잡도
- 최악: O(n²) (편향된 분할 시)
- 평균: O(n log n)
피봇의 선정 방법
- 랜덤
- 중간값
- Median-of-Medians (정확도 높음)
Ⅴ. 선택 정렬(Selection Sort)
기본 개념
- 전체 중 최솟값을 골라서 교환
시간복잡도
- 항상 O(n²)
- 입력 상태에 무관함
제자리 정렬
- O(1) 공간 → 인덱스만 바꿔가며 정렬
장점
- 구현이 간단함
- 부가 메모리 없음
Ⅵ. 버블정렬(Bubble Sort)
의미
- 인접 원소를 비교하여 swap
정렬방식
- 오름차순: 큰 값을 뒤로 보냄
- 내림차순: 작은 값을 뒤로 보냄
시간복잡도
- 최악/평균: O(n²)
- 최선: O(n) (이미 정렬된 경우)
Ⅶ. 삽입 정렬(Insertion Sort)
의미
- 정렬된 부분에 새 원소를 적절한 위치에 삽입
시간복잡도
- 최악: O(n²)
- 최선: O(n) (거의 정렬된 경우)
Ⅷ. 쉘 정렬(Shell Sort)
의미
- 삽입 정렬의 개량
- 간격을 둔 삽입 정렬
동작 방식
- 일정 간격(h)만큼 떨어진 원소끼리 삽입 정렬
- h → 1이 되면 전체 삽입정렬 수행
시간복잡도
- 최악: O(n²)
- 평균: O(n^1.3)
- 간격 수열 선택이 중요
Ⅸ. 힙 정렬(Heap Sort)
의미
- 최대 힙/최소 힙을 구성하여 정렬
이진 힙 구조
- 완전이진트리
- 부모 ≥ 자식 (최대 힙)
정렬방식
- 최대값을 루트로 보내고 맨 뒤와 교환 → 반복
시간복잡도
- 항상 O(n log n)
특징
- 불안정, 제자리 정렬(in-place)
Ⅹ. 기수 정렬(Radix Sort)
의미
- 자릿수별로 정렬 (비교 X)
정렬 방법
- 1의 자리 → 10의 자리 → … 반복
속도
- 매우 빠름 (비교 연산 없음)
시간복잡도
- O(k·n), k는 자릿수
- 제한: 정수 또는 고정 길이 문자열
Ⅺ. 외부 정렬
의미
- 너무 큰 데이터를 보조기억장치에서 정렬
방식
- 메모리에 수용 가능한 만큼 나눠서 정렬
- 정렬된 블록들을 병합
시간복잡도
- O(log(N/M)), N: 전체 크기, M: 메모리 크기
특징
- 외장 디스크 활용
- IO 비용 최소화
Ⅻ. 이진 탐색(Binary Search)
의미
- 정렬된 배열에서 반씩 나누어 탐색
탐색방식
- 중앙값 확인
- 값과 비교 후 절반으로 축소
- 반복
특징
- 정렬 필요
- 빠른 탐색: O(log n)
ⅩⅢ. 선택 문제 (k번째 원소 찾기)
문제 정의
- 전체 n개 숫자 중 k번째로 작은 수 찾기
해결 방법
- 퀵정렬 방식으로 피봇 선택
- 피봇보다 작은 그룹과 비교하여 재귀적으로 탐색
기본 Idea
- 분할정복 + 한쪽만 재귀호출
시간복잡도
- 평균: O(n)
- 최악: O(n²)
This post is licensed under CC BY 4.0 by the author.