알고리즘 (기말 준비)

1강 알고리즘 소개 (1)

1. 기본 개념

• 알고리즘: 문제 해결이나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것.
• 조건:
  • 입출력: 명확히 정의된 입력과 출력.
  • 명확성: 각 단계가 명확해야 함.
  • 유한성: 한정된 시간 내에 종료.
  • 유효성: 실질적으로 실행 가능.
  • 효율성: 실용적 관점에서 중요.

2. 알고리즘 설계

• 알고리즘 생성 과정: 설계 → 표현(기술) → 정확성 분석 → 효율성 분석.
• 대표적인 설계 방법:
  • 욕심쟁이 방법: 각 단계에서 국부적으로 최선의 선택을 하는 전략.
    • 한계: 국부적 최적해가 전체 최적해를 보장하지 않음.
    • 적용 알고리즘/문제: 거스름돈 문제, 배낭 문제, 최소 신장 트리(크루스칼, 프림), 단일 출발점 최단 경로(데이크스트라).
    • 거스름돈 문제: 고객에게 최소 개수의 동전을 돌려주는 문제. 동전의 액면가가 일반적인 경우 적용 불가.
    • 배낭 문제: 배낭의 용량을 초과하지 않으면서 물체들의 이익의 합을 최대화하는 방법. '0/1 배낭 문제'는 적용 불가.
  • 분할정복 방법: 문제를 더 작은 문제들로 나누어 해결하고 결합.
    • 적용 알고리즘/문제: 이진 탐색, 퀵 정렬, 합병 정렬.
    • 단계: '분할' - 문제를 작은 부분으로 나누기. '정복' - 작은 부분을 해결. '결합' - 해결한 부분을 합쳐서 전체 문제 해결.
  • 동적 프로그래밍 방법: 작은 부분 문제부터 해결해 나가는 방법.
    • 적용 알고리즘/문제: 플로이드 알고리즘, 행렬의 연쇄적 곱셈, 최장 공통 부분 수열.
    • 상향식 접근: 작은 문제를 먼저 해결하고, 이를 이용해 더 큰 문제 해결.

---

2강 알고리즘 소개 (2)

1. 알고리즘 분석

• 정확성 분석: 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 생성하는지 수학적으로 증명.
• 효율성 분석: 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정.
  • 공간 복잡도: 알고리즘 수행에 필요한 총 메모리의 양.
  • 시간 복잡도: 알고리즘의 수행 시간.
  • 알고리즘 수행 시간: 각 단위 연산이 수행되는 횟수의 합. 입력 크기의 함수로 표현.
  • 최악의 수행 시간: 데이터의 입력 상태에 따라 달라지며, 최악의 경우를 기준으로 분석.

2. 점근성능

• 점근 성능: 입력 크기가 무한히 커짐에 따라 결정되는 성능.
  • O-표기(Big-oh): 점근적 상한, 최악의 수행 시간.
  • Ω-표기(Big-omega): 점근적 하한, 최선의 수행 시간.
  • Θ-표기(Big-theta): 점근적 상한과 하한을 동시에 표시.
• O-표기의 함수 간 크기 관계: O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ).

3. 순환 알고리즘

• 점화식: 알고리즘의 수행 과정을 점화식으로 표현하여 분석.
  • 기본 점화식과 폐쇄형:
    • T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n).
    • T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n²).
    • T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(logn).
    • T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(n).
    • T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → T(n) = Θ(n).
    • T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → T(n) = Θ(nlogn).

---

3강 정렬 (1)

1. 내부 정렬

• 비교 기반 정렬: 두 데이터의 값을 직접 비교하여 정렬.
  • 예: 선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 힙 정렬.
• 데이터 분포 기반 정렬: 데이터의 분포 정보를 활용하여 정렬.
  • 예: 계수 정렬, 기수 정렬, 버킷 정렬.
• 안정적 정렬: 같은 값을 갖는 데이터의 정렬 전 순서가 유지.
• 제자리 정렬: 입력 데이터를 저장하는 공간 외 추가 저장 공간이 거의 없음.

2. 선택 정렬

• 작동 방식: 입력 배열에서 가장 작은 값부터 선택해 나열.
• 시간 복잡도: O(n²), 불안정적.
• 특징: 입력 데이터 순서에 민감하지 않음, 언제나 동일한 시간 복잡도.

3. 버블 정렬

• 작동 방식: 인접한 두 값을 비교하여 큰 값을 오른쪽으로 이동.
• 시간 복잡도: O(n²), 안정적.
• 특징: 데이터가 정렬되어 있으면 O(n), 역순으로 정렬되면 O(n²).

4. 삽입 정렬

• 작동 방식: 데이터를 하나씩 뽑아 정렬된 상태를 유지하도록 삽입.
• 시간 복잡도: O(n²), 안정적.
• 특징: 데이터가 거의 정렬된 상태면 O(n).

5. 셸 정렬

• 작동 방식: 초기에는 멀리 떨어진 두 원소를 비교/교환, 점차 가까운 위치의 원소를 비교/교환.
• 시간 복잡도: O(n²), 불안정적.
• 특징: 사용하는 순열에 따라 성능이 달라짐.

---

4강 정렬 (2)

1. 퀵 정렬

• 작동 방식: 특정 데이터(피벗)를 기준으로 배열을 두 부분배열로 분할, 각 부분배열에 대해 퀵 정렬 적용.
• 시간 복잡도:
  • 최악: O(n²) (불균형 분할).
  • 최선: O(nlogn) (균형 분할).
  • 평균: O(nlogn).
• 특징: 불안정적, 제자리 정렬.

2. 합병 정렬

• 작동 방식: 배열을 동일한 크기의 두 부분배열로 분할, 각 부분배열을 순환적으로 합병 정렬, 정렬된 두 부분배열을 합병.
• 시간 복잡도: O(nlogn), 안정적.
• 특징: 추가 저장 공간 필요.

---

5강 정렬 (3)

1. 힙 정렬

• 작동 방식: 최대 힙을 구축하여 정렬.
  • 단계 1: 주어진 배열을 초기 힙으로 구축.
  • 단계 2: 최댓값 삭제 및 힙 재구성.
• 시간 복잡도: O(nlogn), 불안정적.

2. 계수 정렬

• 작동 방식: 데이터의 출현 횟수를 세고, 누적 값을 계산하여 정렬.
• 시간 복잡도: O(n).
• 특징: 안정적, 제자리 정렬이 아님.

3. 기수 정렬

• 작동 방식: 데이터의 자릿수별로 정렬.
• 시간 복잡도: O(n).
• 특징: 안정적, 제자리 정렬이 아님.

4. 버킷 정렬

• 작동 방식: 데이터 범위를 여러 버킷으로 나누고 각 버킷을 정렬.
• 시간 복잡도: O(n).
• 특징: 안정적, 제자리 정렬이 아님.

---

6강 탐색 (1)

1. 순차 탐색

• 작동 방식: 리스트의 원소를 처음부터 하나씩 차례로 비교.
• 시간 복잡도: O(n).
• 적용: 모든 리스트 형태의 입력에 적용 가능, 특히 비정렬 데이터 탐색에 적합.

2. 이진 탐색

• 작동 방식: 정렬된 리스트의 중앙값과 비교하여 절반씩 줄여가며 탐색.
• 시간 복잡도: O(logn).
• 적용: 정렬된 리스트에만 적용 가능.

3. 이진 탐색 트리

• 작동 방식: 각 노드의 왼쪽 서브트리의 값은 작고, 오른쪽 서브트리의 값은 큼.
• 시간 복잡도: 평균 O(logn), 최악 O(n).
• 특징: 삽입/삭제 시 기존 노드의 이동이 거의 없음, 경사 트리가 될 수 있음.

4. 2-3-4 트리

• 구성: 2-노드, 3-노드, 4-노드로 구성된 균형 탐색 트리.
• 시간 복잡도: O(logn).
• 특징: 노드의 구조가 복잡하여 느려질 가능성 있음.

---

7강 탐색 (2)

1. 레드-블랙 트리

• 특징: 이진 탐색 트리로서 균형을 유지.
  • 모든 노드는 검정 또는 빨강.
  • 루트와 리프 노드는 검정.
  • 빨강 노드의 부모는 항상 검정.
  • 경로상 검정 노드 개수는 동일.
• 시간 복잡도: O(logn).

2. B-트리

• 특징: 균형 탐색 트리.
  • 루트 노드는 1 ~ (2t-1)개의 키.
  • 내부 노드는 (t-1) ~ (2t-1)개의 키.
  • 내부 노드는 키 개수보다 하나 더 많은 자식 노드.
  • 모든 리프 노드의 레벨은 동일.
• 시간 복잡도: O(logn).

3. 해시 테이블

• 특징: 해시 함수를 통해 상수 시간 내 접근 가능.
• 충돌 해결 방법: 개방 해싱, 폐쇄 해싱.
  • 개방 해싱: 충돌된 데이터를 해시 테이블 밖에 저장(연결 리스트).
  • 폐쇄 해싱: 테이블 내 다른 슬롯에 저장(버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱).
• 시간 복잡도: O(1) (이론적으로).

---

8강 그래프 (1)

1. 그래프 구현

• 인접 행렬: |V|*|V| 행렬 사용, 조밀한 그래프에 적합.
• 인접 리스트: |V|개의 연결 리스트로 구성, 성긴 그래프에 적합.

2. 그래프 순회

• 깊이 우선 탐색(DFS): 한 정점에서 시작해 인접한 정점을 방문, 스택 사용.
• 너비 우선 탐색(BFS): 시작 정점에서 가까운 정점부터 방문, 큐 사용.

---

9강 그래프 (2)

1. 크루스칼 알고리즘

• 목적: 최소 신장 트리.
• 작동 방식: 간선 가중치 오름차순 선택, 사이클 형성 안 하면 추가.
• 시간 복잡도: O(|E|log|E|).

2. 프림 알고리즘

• 목적: 최소 신장 트리.
• 작동 방식: 임의의 시작 정점에서 연결된 정점 선택.
• 시간 복잡도:
  • 인접 행렬: O(|V|²).
  • 인접 리스트와 힙 사용: O((|V|+|E|)log|V|).

3. 데이크스트라 알고리즘

• 목적: 단일 출발점 최단 경로.
• 제약 조건: 음의 가중치 간선 없음.
• 작동 방식: 거리 d[]가 최소인 정점 선택.
• 시간 복잡도:
  • 인접 행렬: O(|V|²).
  • 인접 리스트: O((|E|+|V|)log|V|).

---

10강 그래프 (3)

1. 벨만-포드 알고리즘

• 목적: 단일 출발점 최단 경로(음의 가중치 간선 허용).
• 작동 방식: 모든 간선을 한 번씩 조사, 거리값 조정.
• 시간 복잡도: O(|V||E|).

2. 플로이드 알고리즘

• 목적: 모든 정점 쌍 간 최단 경로.
• 작동 방식: 경유할 수 있는 정점을 점차 늘려가며 경로 계산.
• 시간 복잡도: O(|V|³).

3. 포드-풀커슨 알고리즘

• 목적: 최대 플로(소스에서 싱크로).
• 작동 방식: 플로를 더 보낼 수 있는 증가 경로를 찾고, 잔여 용량을 이용해 플로 값 조정.
• 시간 복잡도: O(|E|F).

---

11강 동적 프로그래밍

1. 동적 프로그래밍

• 접근 방법: 상향식, 소문제 해를 테이블에 저장해 큰 문제 해결.
• 특징: 최적성의 원리 필요.
• 예시:
  • 피보나치 수열: 점화식 f(n) = f(n-1) + f(n-2), n>=2, f(1)=1, f(0)=0.
  • 행렬 연쇄적 곱셈: 점화식 C(i,j)=min{i<=k< j}{C(i,k)+C(k+1,j)+di-1dkdj}, i<j.
  • 최장 공통 부분 수열(LCS): 점화식 LCS(i,j)=max{LCS(i-1,j), LCS(i,j-1)}.

---

12강 스트링 알고리즘 (1)

1. 스트링 매칭

• 브루트-포스: 텍스트의 각 위치에서 패턴을 비교, O(nm).
• 라빈-카프: 패턴의 해시값으로 매치의 후보를 찾고 비교, O(n+km).
• KMP: 패턴 내의 접두부와 접미부 정보를 이용해 비교 중복 줄임, O(n).

---

13강 스트링 알고리즘 (2)

1. 보이어-무어 알고리즘

• 특징: 패턴의 뒷부분부터 비교, 불일치 시 최대 이동.
• 시간 복잡도: 최악 O(nm), 최선 O(n/m).

2. 데이터 압축

• 무손실 압축: 원래 데이터를 완벽하게 복원.
  • 예: RLE, 허프만 코딩, LZ77.
• 손실 압축: 원래 데이터를 완벽하게 복원 불가.
  • 예: JPEG, MPEG.

---

14강 스트링 알고리즘 (3)

1. 허프만 코딩

• 작동 방식: 빈도수 클수록 짧은 코드 부여.
• 시간 복잡도: O(|Σ|log|Σ| + n).

2. LZ77

• 작동 방식: 슬라이딩 윈도우 사용, 앞서 나온 문자열 위치와 길이로 압축.

---

15강  NP-완전 문제

1. NP 문제

• NP: 비결정론적 튜링 기계로 다항 시간 내 해결 가능.
• P: 결정론적 튜링 기계로 다항 시간 내 해결 가능.
• NP-완전 문제: 모든 NP 문제를 다항 시간 내 변환 가능.
  • 예: CNF 만족성 문제, 클리크 판정 문제, 버텍스 커버 문제.

2. 근사 알고리즘

• 목적: 최적화 문제에 대해 근사해를 다항 시간 내 구함.
• 예:
  • 버텍스 커버 문제: 모든 간선과 맞닿은 최소 크기의 정점 집합.
  • 외판원 문제: 최소 비용으로 모든 도시를 방문하고 돌아오는 경로.
  • 통 채우기 문제: 최소 개수의 통에 물체를 넣는 문제.