JANGUN


알고리즘


이관용, 김진욱 공저



목차

제1장 알고리즘 소개
제2장 정렬
제3장 탐색
제4장 그래프
제5장 스트링 알고리즘
제6장 동적 프로그래밍
제7장 NP-완전문제
제8장 병렬 알고리즘
제9장 유전 알고리즘


제1장 알고리즘 소개

1. 컴퓨터 알고리즘이란? - 주어진 문제에 대한 하나 이상의 결과를 생성하기 위해 모호함이 없는 간단하고 컴퓨터가 수행 가능한 일련의 유한개의 명령을 순서적으로 구성한 것
- 알고리즘의 조건 → 입출력, 명확성, 유한성, 유효성

2.기본적인 자료구조
- 선형 구조 → 배열, 연결리스트, 큐, 스택
- 비선형 구조 → 트리, 그래프

3.알고리즘의 설계 방법
- 주어진 문제와 조건 등이 매우 다양하므로 알고리즘의 일반적인 설계 방법론은 존재하지 않지만, 많은 부류의 문제에 적용될 수 있는 대표적인 설계 기법으로는 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법이 있다.

4.욕심쟁이 방법
- 해를 구하는 일련의 선택 과정마다 그 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면, 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법이다. 여기서 '희망적'이라는 표현은 욕심쟁이 방법을 적용해도 최적해를 구할 수 없는 경우도 존재한다는 것을 의미한다.
- 욕심쟁이 방법이 적용 가능한 문제
▸ 거스름돈 문제 → 가게에 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
▸ 배낭 문제 → 배낭의 용량을 초과하지 않는 범위에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 배낭에 넣은 방법을 찾는 문제로서 물체를 쪼갤 수 있다고 가정한다.   물체를 쪼갤 수 없는 0/1 배낭 문제는 욕심쟁이 방법으로 해결할 수 없다.
▸ 교재 4장(그래프) → 프림 알고리즘, 크루스칼 알고리즘, 데이크스트라 알고리즘

5.분할정복 방법
- 순환적으로 문제를 푸는 방식으로 문제를 더는 쪼갤 수 없을 때까지 작은 문제로 나누고, 이렇게 나누어진 작은 문제를 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법으로, 각 순환 호출 시마다 분할, 정복, 결합의 세 단계를 거친다. → 퀵 정렬(교재 2장), 합병 정렬(교재 2장), 이진 탐색(교재 3장) 등

6.동적 프로그래밍 방법
- 주어진 문제를 여러 개의 부분 문제로 분할하고, 가장 작은 부분 문제부터 해를 구하여 테이블에 저장해 놓고 이를 이용하여 입력 크기가 더 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법이다. → 플로이드 알고리즘(교재 4장), 교재 6장

7.알고리즘 분석은 두 가지 측면에서 수행
- 정확성 분석 → 올바른 입력이 주어졌을 때 유한 시간 내에 정확한 결과를 산출하는지를 판단한다.
- 효율성 분석 → 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정, 즉 소요되는 메모리 공간의 크기(“공간 복잡도”)와 수행에 걸리는 시간(“시간 복잡도”)을 추정한다.

8.알고리즘의 수행 시간
- 수행 시간 = 각 연산의 수행 횟수의 합 - 수행 시간은 일반적으로 입력 크기(입력되는 데이터의 크기) n의 함수로 표현
- 데이터의 입력 상태에 따라 수행 시간은 달라진다.
- 알고리즘의 우열을 따질 경우에는 알고리즘의 수행 시간을 나타내는 식의 성장률 또는 차수만을 따지는 것이 일반적이며, 따라서 입력 크기 n의 최고 차수만을 따지며 하위 차수와 상수는 모두 무시한다.

9.점근 성능
- 입력의 크기 n이 충분히 커질 때 알고리즘의 수행 시간이 무엇에 의해 좌우되는가를 나타내는 것
→ 수행 시간이 다항식으로 표현되는 경우에는 입력의 크기가 커짐에 따라 상수항과 차수가 낮은 항들의 역할이 감소하게 되고, 결국 n의 최고차항에 좌우된다.
- 표기법
① “Big-oh” 점근적 상한 f(n) = O(g(n),
   ② “Big-omega” 점근적 하한 f(n)=Ω(g(n)),  
   ③ “Big-theta” 점근적 상하한 f(n)=Θ(g(n))
- 시간 복잡도 함수 간의 크기 관계 → O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!)

10.기본 점화식의 종류와 폐쇄형
► T(n) = T(n-1) + Θ(1), T(1)=Θ(1) → Θ(n)
► T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2)
► T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn)
► T(n) = T(n/2) + Θ(n), T(1)=Θ(1) → Θ(n)
► T(n) = 2T(n/2) + Θ(1), T(1)=Θ(1) → Θ(n)
► T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn)


제2장 정렬

정렬의 정의 및 관련 개념
- 정렬 → 여러 원소로 구성된 리스트에 대해서 이 원소들을 키값의 크기 순서에 따라 재배치하는 것
- 내부 정렬과 외부 정렬
▸내부 정렬 → 모든 데이터를 주기억장치에 저장한 후 정렬하는 방식
▸외부 정렬 → 모든 데이터를 주기억장치에 저장할 수 없어서 일부 데이터는 주기억장치에 있고 나머지 데이터는 보조기억장치에 저장된 채 정렬을 하는 방식
- 비교 기반 정렬과 분포 기반 정렬
▸비교 기반 정렬 → 데이터의 키값을 비교하여 정렬하는 방식   (선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬, 합병 정렬, 퀵 정렬, 히프 정렬)
▸분포 기반 정렬 → 데이터의 분포 정보를 이용하여 정렬하는 방식 (계수 정렬, 버킷 정렬, 기수 정렬)
- 안정적 정렬 → 동일한 키값을 갖는 데이터 A와 B에 대하여 정렬 전과 정렬 후의 A와 B의 상대적인 위치(앞뒤 관계)가 변하지 않는 정렬
- 제자리 정렬 → 입력 배열 이외의 필요한 별도 저장 공간의 개수가 상수 개를 넘지 않는 정렬

2.선택 정렬
- 정렬되지 않은 데이터 중에서 가장 작은 키값을 갖는 원소를 선택한 후, 이것을 미정렬 데이터의 첫 번째 원소와 교환하는 과정을 반복하여 정렬을 수행하는 방법
- O(n2) - 최선/최악/평균의 경우, 불안정, 제자리

3.버블 정렬
- 인접한 두 원소를 차례대로 비교하면서 (오름차순의 경우) 왼쪽 데이터의 키값이 오른쪽 데이터의 키값보다 큰 경우 자리바꿈을 통하여 정렬하는 방법
- 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 실행 시간 O(n2)을 가짐
- O(n2), 안정적, 제자리

4.삽입 정렬
- 미정렬 부분의 첫 번째 원소를 하나씩 꺼내어 정렬된 부분에서 바른 위치에 삽입하여 나열하는 방법
- 주어진 데이터가 이미 정렬된 경우에는 최선의 수행 시간 O(n)을 갖고, 데이터가 역순으로 정렬된 경우에는 최악의 실행 시간 O(n2)을 가짐
- O(n2), 안정적, 제자리

5.셸 정렬
- 삽입 정렬의 단점(현재 삽입하고자 하는 키가 정렬 후에 도착할 자리에서 많이 벗어나 있어도 한 번에 한 자리씩만 이동하여 접근하는 문제)을 보완
- 처음에는 멀리 떨어진 두 원소를 비교하여 위치를 교환하고 점차 가까운 위치의 원소를 비교/교환한 뒤 마지막에는 인접한 원소를 비교/교환하는 정렬 방식으로, 입력 배열을 부분배열로 나누어 삽입 정렬을 수행하는 과정을 부분배열의 크기와 개수를 변화시켜 가면서 여러 번 거치도록 한 것
- 간격의 크기, 즉 D의 계산 방식에 따라 다양한 성능을 보임
- O(n2), 불안정적, 제자리

6.합병 정렬
- 주어진 배열을 동일한 크기의 두 부분배열로 분할하고 각 부분배열을 순환적으로 정렬한 후 정렬된 부분배열을 합병하여 하나로 나열하는 방식
- 합병 함수 Merge() : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 함수, 시간 복잡도 Θ(n)
- 최악/평균적인 경우: T(n) = 2T(n/2)+Θ(n), T(1)=Θ(1) → Θ(nlogn)
- 안정적인 정렬
- 제자리 정렬이 아님: 합병 과정에서 입력 배열에 해당하는 크기만큼의 추가 공간이 필요

7.퀵 정렬
- 특정 원소를 기준으로 주어진 원소들을 두 부분배열로 분할하고, 각 부분배열에 독립적으로 퀵 정렬을 순환적으로 적용하여 정렬하는 방식
- 피벗: 배열을 두 부분배열로 분할할 때 기준이 되는 원소로서, 간단히 정렬할 배열의 첫 번째 원소를 피벗으로 지정한다.
- 분할 함수 Partition() : 퀵 정렬의 가장 핵심이 되는 부분으로, 피벗을 중심으로 두 부분배열로 분할하는 함수 → Θ(n)
- 최악의 경우: 피벗 하나만 제자리를 잡고, 나머지 모든 원소가 한쪽의 부분배열로 되는 경우 (한 번에 한 원소씩 줄이면서 n번 순환 호출하게 됨) = 피벗이 배열에서 가장 큰 값이거나 또는 가장 작은 값이 되는 경우 = 배열이 이미 제 순서로 정렬되었거나 역순으로 정렬된 경우 → 시간 복잡도 T(n) = T(n-1) + Θ(n), T(1)=Θ(1) → Θ(n2)
- 최선의 경우: 피벗을 중심으로 배열이 거의 같은 크기의 두 개의 부분배열로 나뉘는 경우 → T(n) = 2T(n/2) + Θ(n), T(1)=Θ(1) → Θ(nlogn)
- 평균 실행시간 → T(n) = Θ(nlogn)
- 안정적이지 않은 정렬, 제자리 정렬

8.퀵 정렬, 합병 정렬 → 분할정복 방법을 적용한 알고리즘
→ 분할: 주어진 문제를 여러 개의 소문제로 분할
→ 정복: 소문제들을 순환적으로 처리하여 해를 구하는 단계
→ 합병(결합): 소문제에 대한 해를 합병하여 원래 문제의 해를 구함 (퀵 정렬에서는 합병 단계가 필요 없음)

9. 히프 정렬
- 히프(heap) : 완전 이진 트리로서, 각 노드의 값이 자식 노드의 값보다 크거나 같아야 함 (“최대값 히프”) ⇎ 최소값 히프
- 두 단계로 구성
① 정렬하려는 1차원 배열을 히프로 변환(초기 히프 구축) → 두 가지의 구축 방법
② 히프에서 최대값을 제거한 후 히프를 조정하는 과정 → 데이터 개수만큼 반복
- 최악/평균 시간복잡도 : O(nlogn)
- 최악의 실행시간은 퀵 정렬보다 빠르지만, 평균적으로 퀵 정렬보다 좋지 않다.
- 안정적이지 않은 정렬, 제자리 정렬

10.데이터의 분포에 의한 정렬
- 키들의 비교가 아닌 키의 분포를 이용한 정렬 알고리즘
- 종류: 계수 정렬, 버킷 정렬, 기수 정렬
- 최악 또는 평균 실행시간이 모두 선형 시간 O(n)을 가짐

11.계수 정렬
- 우선 입력키의 범위만큼 배열을 할당하고, 각 키 값에 대한 출현 회수의 누적값을 계산한 후, 입력 배열의 끝에서부터 시작해서 해당 원소가 정렬 후 위치할 곳을 바로 찾아서 정렬하는 방법
- 안정적이지만 제자리 정렬이 아님

12.버킷 정렬
- 키 값의 범위를 n개의 버킷으로 나눈 다음, 입력 데이터를 해당 버킷에 넣는다.
데이터를 모두 버킷에 넣은 후 각 버킷에 대해서는 삽입 정렬을 적용한 후 버킷들을 차례대로 나열하면 정렬된 결과를 얻게 된다.
- 적용 조건
→ 계수 정렬과 동일한 조건으로 키 값의 범위가 작아야 함
→ 키 값의 범위 내에서 키 값이 확률적으로 균등하게 분포해야 한다.

13.기수 정렬
- 주어진 원소들의 키값을 자릿수별로 나누어서 낮은 자리부터 높은 자리로 반복해서 계수 정렬과 같은 안정적 알고리즘을 적용하여 정렬하는 방법
- 안정적 정렬, 제자리 정렬이 아님

** 정렬 알고리즘의 비교


제3장 탐색

1. 순차 탐색
- 주어진 원소들을 하나씩 차례로 탐색키와 비교하면서 원하는 키값을 갖는 원소를 찾는 방법 (일반적으로 왼쪽에서부터 하나씩 비교한다.)
- 모든 리스트에 적용 가능, 특히 비정렬 데이터의 탐색에 적합한 방법
- 시간 복잡도 O(n)

2. 이진 탐색
- 정렬된 리스트 형태로 주어진 원소들에 대해 분할정복 방법을 적용한 탐색 방법
- 탐색 방법: 탐색하려는 키와 주어진 리스트의 가운데 원소의 키를 비교하여   
→ 탐색키 = 가운데 원소의 키 ⇒ 탐색 성공   
→ 탐색키 < 가운데 원소의 키 ⇒ 주어진 리스트의 전반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출한다.  
  → 탐색키 > 가운데 원소의 키 ⇒ 주어진 리스트의 후반부를 탐색 범위로 재지정한 후 이진 탐색을 순환 호출한다.
- 탐색을 한 번 수행할 때마다 탐색 원소의 개수가 반씩 감소
- 시간 복잡도: T(n) = T(n/2) + Θ(1), T(1)=Θ(1) → Θ(logn)
- 삽입/삭제 시 정렬된 상태를 유지하기 위한 자료의 이동(평균 n/2번, 최악 n번)으로 인한 오버헤드가 발생 → 삽입/삭제가 빈번한 경우 부적합

3. 이진 탐색 트리
- 데이터가 고정되어 있지 않고 삽입과 삭제가 빈번한 경우에 적합한 구조
- 이진 탐색 트리란? 각 노드 x의 왼쪽 부분 트리의 모든 키는 x의 키보다 작고 오른쪽 부분 트리의 모든 키는 x의 키보다 크다는 조건을 만족하게 하는 이진 트리
- 탐색 연산: 루트 노드로부터 시작해서 크기 관계에 따라 트리의 경로를 따라 내려가면서 진행
- 삽입 연산: 우선 트리를 탐색한 후, 탐색이 실패한 지점에 자식 노드를 생성하여 삽입
- 삭제 연산: 삭제되는 노드의 자식 개수에 따라 3가지 경우로 나누어 수행   
① 자식이 없는 경우(리프 노드): 남은 노드의 위치 조절이 필요하지 않음   
② 자식이 하나만 있는 경우: 자식 노드를 삭제되는 노드의 위치로 올리면서 부분 트리 전체도 따라 올린다.   
③ 자식이 두 개 모두 있는 경우: successor 노드를 삭제되는 노드의 위치로 올리고, successor 노드의 자식 노드를 successor 노드의 위치로 올리면서 그 부분 트리 전체도 따라 올림
(successor 노드란? 어떤 노드의 바로 다음 키값을 갖는 노드)
- 평균적인 탐색 시간은 O(logn)이며, 최악의 경우(경사 이진 트리가 생성되는 경우)에는 O(n)이 된다.

4. 균형 탐색 트리: 왼쪽 부분 트리와 오른쪽 부분 트리의 높이가 같은 트리
- 이진 탐색 트리에서 최악의 경우에 해당하는 경사 트리가 만들어지지 않도록 트리의 균형을 유지한다면 최악의 경우에도 O(logn)을 유지할 수 있다.

5. 2-3-4 트리 : 2-노드, 3-노드, 4-노드로 구성(k-노드는 k개의 자식 노드를 가리키는 포인터와 k-1개의 키로 구성)되며, 모든 리프 노드의 높이는 동일
- 4-노드의 분할 → 삽입을 위한 탐색 과정에서 4-노드를 만나면 하나의 4-노드를 3개의 2-노드로 분할하고, 가운데 2-노드에 해당하는 키를 부모 노드로 이동시킨다.
- 2-3-4 트리를 그대로 구현하면 노드의 구조가 복잡해서 이진 탐색 트리보다 더 느려질 가능성이 많음

6. 흑적 트리 : 2-3-4 트리를 이진 탐색 트리 형태로 구현한 것
- 흑적 트리의 성질
→ 모든 노드는 흑색 노드 또는 적색 노드로 구성
→ 루트 노드는 흑색이며, 자식이 없는 경우 흑색의 널 노드를 자식으로 가진다.
→ 적색 노드의 두 자식 노드는 항상 흑색이다. 따라서 루트 노드에서 리프 노드까지의 경로 상에 두 적색 노드가 연달아 나타나지 않는다.
→ 임의의 노드로부터 리프 노드까지의 경로 상에는 동일한 개수의 흑색 노드가 존재한다.
- 노드의 삽입은 탐색이 실패한 NULL 노드에 적색 노드를 추가하면 되는데, 이 과정에서 적색 노드가 연달아 나타나게 된다.
따라서 흑적 트리의 성질을 만족하도록 다음과 같은 규칙에 따라 노드의 구조나 색깔을 변경해야 한다.
→ ① 부모의 형제 노드가 적색인 경우: 부모, 부모의 형제, 부모의 부모(조부모) 색깔을 모두 변경한다.
→ ② 부모의 형제 노드가 흑색이며, 현재 노드의 키값이 부모와 조부모의 키값 사이인 경우 : 현재 노드와 부모 노드를 회전시킨다.
→ ③ 부모의 형제 노드가 흑색이며, 현재 노드의 키값보다 부모와 조부모의 키값이 큰 경우(혹은 작은 경우) : 부모 노드와 조부모 노드를 회전시키고 색깔을 변경한다.

7. 해싱
- 배열에서 인덱스를 줬을 때 이를 이용하여 원하는 원소를 상수 시간에 찾듯이, 원소의 키값을 이용하여 데이터 저장을 위한 테이블의 주소를 직접 계산하여 상수 시간 내에 접근탐색방법
- 해시 함수 : 키 값을 해시 테이블 주소로 변환하는 함수 → 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 해시 함수
- 충돌 해결 방법 : → 충돌: 서로 다른 키값 x, y에 대하여 h(x)=h(y)인 경우
→ 개방 해싱(연쇄법): 동일한 주소로 해시 되는 모든 원소를 연결 리스트 형태로 구성하여 관리
→ 폐쇄 해싱(개방 주소법): 테이블 내의 다른 슬롯에 충돌된 데이터를 저장/관리하기 위해서 정해진 방법에 따라 테이블의 다른 위치를 탐사하는 방법
(종류: 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱)


제4장 그래프

1. 그래프 G=(V,E) : 정점의 집합 V와 간선의 집합 E의 집합
- 주요 용어: 가중 그래프, 무방향 그래프, 방향 그래프, 인접, 부수, 부분 그래프, 경로, 경로의 길이, 차수(진입차수, 진출차수), 단순경로, 사이클, 루프, 연결, 강력 연결

2.그래프의 구현 방법
- 정점들의 관계를 나타내는 간선의 집합 E를 표현하는 것
- 인접 행렬에 의한 구현 → |V|*|V| 행렬 사용, 조밀한 그래프에 적합
- 인접 리스트에 의한 구현 → 연결 리스트 사용, 성긴 그래프 표현에 적합

3.그래프 순회
- 그래프의 모든 정점을 체계적으로 방문하는 것 → 깊이 우선 탐색, 너비 우선 탐색
- 깊이 우선 탐색
→ 최근의 주변 정점을 우선적으로 방문하는 방법 → 스택으로 구현하는 것이 적절 → 시간 복잡도 O(|V|+|E|)
- 너비 우선 탐색
→ 주변 정점 중에서 가장 오래된 것부터 먼저 방문하는 방법 → 큐로 구현하면 적절 → 시간 복잡도 O(|V|+|E|)

4.그래프 순회의 응용
- 위상 정렬
→ 무사이클 방향 그래프(dag)의 방향 간선이 한 방향으로만 향하도록 정점을 나열하는 것
→ 깊이 우선 탐색을 수행하다가 더 이상 인접한 정점이 없어서 되돌아갈 때, 즉 스택에서 탑이 삭제될 때 그 제거한 정점을 순서대로 나열하면 된다.
- 그래프의 연결성
→ 연결 성분: 모든 정점쌍 간에 경로가 존재하는 최대의 부분 그래프
→ 강연결 성분: 강연결 성분은 방향 그래프에 대하여 성립하는 것으로서, 방향 그래프에서 서로 접근할 수 있는 방향 경로가 모든 정점쌍 간에 존재하는 최대의 부분 그래프이다. 깊이 우선 탐색을 활용하여 구함.

5. 최소 신장 트리
- 신장 트리 중에서 간선의 가중치 합이 작은 것 → 신장 트리: 연결된 가중 무방향 그래프에서 주어진 정점을 모두 포함하는 트리
→ 크루스칼 방법과 프림의 방법 ⟹ 두 방법 모두 욕심쟁이 방법이 적용됨
- 크루스칼 알고리즘 → 간선이 하나도 없는 상태에서 시작하여 사이클을 만들지 않는 최소 간선들을 하나씩 추가해 나가는 방법 → 시간 복잡도 O(|E|log|E|)
- 프림 알고리즘 → 이미 선택된 정점에 부수된 최소 간선을 추가해 나가는 방법 ⟹ 이미 선택된 정점 집합 S와 V-S를 잇는 최소의 간선을 선택해서 추가하는 방법
→ 시간 복잡도: 인접 행렬의 경우 O(|V|2), 인접 리스트의 경우 O((|V|+|E|)lg|V|)

6.단일 출발점 최단 경로
- 가중 방향 그래프에서 한 출발 정점에서 다른 모든 정점까지 가중치 합이 최소인 경로 (가정: 음의 가중치를 갖는 간선이 없다.)
- 데이크스트라 알고리즘 → 욕심쟁이 방법 적용
→ 출발점에서 시작하여 거리가 최소인 정점을 선택해 나감으로 최단 경로를 구하는 방법
→ 정점 v의 거리 d[v]는 시작 정점 s로부터 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이를 의미
→ 적용 방법:
ⓐ 미선택 정점 집합 V-S에서 거리 d가 최소인 정점 u를 선택
ⓑ u의 인접 정점들에 대하여 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새 거리 값으로 조정
→ 시간 복잡도: 인접 행렬의 경우 O(|V|2), 인접 리스트의 경우 O((|E|+|V|)lg|V|)

7.모든 쌍 최단 경로
- 모든 정점쌍 간의 최단 경로를 구하는 문제 (가정: 경로의 길이가 음인 사이클이 그래프에 존재하지 않는다.)
→ 단일 출발점 최단 경로를 구하는 데이크스트라 알고리즘을 각 정점을 출발점으로 하여 반복적으로 적용해서 구할 수도 있다 → O(|V|3)
- 플로이드 알고리즘 → 동적 프로그래밍 방법 적용 → dij(k): 정점 번호가 k 이하인 정점만을 경유하여 정점 i에서 정점 j까지의 최단 경로 길이 → 점화식:
→ 시간 복잡도 O(|V|3)


제5장 스트링 알고리즘

1. 스트링 매칭
- 스트링 매칭이란 텍스트 T[1..n]에서 패턴 P[1..m]과 일치하는 모든 부분 스트링의 위치를 찾아내는 문제
- 패턴을 전처리하는 접근 방식과 텍스트를 전처리하는 접근 방식으로 구분 가능

2.브루트-포스 알고리즘
- 가장 간단한 방법으로, 텍스트의 매 위치에서 패턴 일치가 발생하는지를 조사하는 방법
- 최악의 경우는 텍스트의 매 위치에서 패턴의 모든 문자를 비교하는 경우 → 예: T=00000...000001, P=00001
- 시간복잡도: O(m(n-m+1)) → O(mn)

3.라빈-카프 알고리즘
- 스트링을 |Σ|=d진법의 숫자로 바꾸어, 즉 해시값을 계산하여 매치의 후보를 찾고, 후보에 대해서만 문자별로 비교해서 매치를 찾는 방법
- 스트링을 숫자로 바꾸는 과정에서 p, ts, dm-1를 그대로 계산하면 이 값이 너무 커져서 오버플로가 발생하는 것을 피하기 위해서 modulo 연산을 사용
- 최악의 실행시간: O(m(n-m+1) → O(mn) → 패턴의 해시값과 텍스트의 해시값이 모두 일치하여 다시 일일이 문자를 비교해야 하는 경우 (예, T=an, P=am)
- 최선의 경우: O(m+n) ← 패턴의 해시값과 텍스트의 해시값이 모두 불일치하는 경우
- 실제로 대부분의 경우 해시값이 불일치하는 경우가 많으므로 실행시간의 기대치는 O(m+n)

4.KMP 알고리즘
- 패턴의 최대 접미부-접두부 쌍을 구하여 불일치 발생 시 텍스트의 앞부분으로 돌아감이 없이 패턴 매칭을 하는 방법
→ KMP 알고리즘의 경우 이미 비교한 텍스트의 앞부분을 다시 비교하는 일이 없다.
→ 패턴을 전처리하여 접미부와 최대로 일치하는 진접두부를 구하여 이를 최대 접두부 배열 F에 저장해 놓는다.
- 텍스트의 위치 i와 패턴의 위치 j를 비교하여 불일치가 발생하였다면 다음에 비교할 위치는 T[i]와 P[F[j-1]+1]이다.
- 시간 복잡도 O(m+n) ← 패턴 전처리 O(m) + 매칭 O(n)

5. 보이어-무어 알고리즘
- 패턴이 텍스트에 정렬된 각 위치에서 문자의 비교를 우측에서 좌측으로 행해나가면서 일치 접미부 방법과 불일치 문자방법을 사용하여 빠른 패턴 매칭을 수행 방법
- 각 위치에서 불일치가 발생하면 불일치 문자 방법과 일치 접미부 방법에 의한 이동 거리를 계산하고 그중에서 큰 값을 사용하여 패턴을 오른쪽으로 이동시킨다.
- 최악의 시간 복잡도는 O(m(n-m+1))이지만, 최선의 경우는 O(m+n/m)이며 이렇게 수행될 가능성이 매우 높은 알고리즘이다.

6.RLE(Run-Length Encoding)
- 동일 문자가 인접해서 반복되어 나타나는 것을 그 문자와 반복개수를 이용하여 압축하는 방법
- 이 방법은 반복 문자의 개수가 일정 개수 이상이어야 실제 효과가 있으며, 일반 문서보다 영상 데이터 압축에 효과적

7.허프만 코딩
- 문자가 텍스트에 나오는 빈도에 따라 다른 길이의 부호를 부여한다. 즉, 자주 나타나는 문자에 짧은 부호를 부여하고 드물게 나타나는 문자에는 긴 부호를 부여하여 전체 메시지의 길이를 줄이려는 방법
- 코드워드 → 알파벳의 각 문자에 대응하는 부호, 코드 → 코드워드의 집합
- 접두부 코드 → 어떠한 코드워드도 다른 코드워드의 접두부와 일치하지 않는 코드, 접두부 코드는 최적 코드(인코딩된 메시지의 길이가 가장 짧은 코드)가 된다.
- 허프만 코드
→ 최적 접두부 코드이며, 문자의 출현 빈도에 따라 허프만 트리를 상향식으로 만들어 코드를 부여
→ 허프만 트리(욕심쟁이 방법을 사용해서 생성) : 전 이진 트리로서, 알파벳의 각 문자는 잎 노드에 나타나며 각 노드는 빈도수로 레이블된다.
좌우의 두 간선은 각각 0과 1로 레이블되며, 노드의 빈도수가 작은 두 노드를 합쳐 부모 노드를 만들어 나가는데 이때 부모 노드는 자식 노드 레이블의 합으로 레이블됨.
→ 허프만 트리는 유일하지 않다. 즉 레이블이 작은 노드를 합치는 과정에서 같은 빈도수를 가진 여러 노드 중에서 어떤 순서로 두 개의 노드를 택하느냐에 따라 여러 개의 최적 코드가 만들어질 수 있다.
- 문자의 빈도수를 모르면 텍스트를 두 번 읽어야 한다.
디코딩을 위해 허프만 트리와 원래 코드 정보를 메시지의 헤더로써 함께 보내주어야 하며, 이것이 압축률을 떨어뜨린다.

8. LZ77 알고리즘
- 사전법에 속하는 방법으로, 가장 널리 사용되는 압축 방법이다. → 사전법 : 실제의 사전처럼 단어의 사전을 이용하는 방법
- 슬라이딩 윈도 사용 : LZ77, 슬라이딩 윈도 미사용 : LZ78 → LZW
- 한 번 나왔던 문자열이 다시 나오는 경우에는 문자열 대신 앞에서 나온 해당 문자열의 위치와 길이 정보를 이용하여 압축하는 방법
→ 슬라이딩 윈도 (탐색 버퍼와 전향 버퍼로 구성)가 좌에서 우로 한 문자씩 이동하면서 인코딩 과정을 수행
→ 탐색 버퍼를 우에서 좌로 조사하면서 전향 버퍼의 접두부와 최대로 일치하는 부분을 찾아서 토큰 형식으로 인코딩
→ 토큰 형식 : (오프셋, 일치 길이, 다음 입력 문자)
→ 탐색 버퍼에서 전향 버퍼의 첫 글자도 찾지 못한 경우에는 (0, 0, 전향 버퍼의 첫 글자)와 같이 인코딩
- 디코딩은 인코딩보다 훨씬 간단
→ 각 토큰에 대해서 탐색 버퍼에서 일치된 부분과 토큰에 기록된 다음 입력 문자를 출력해서 탐색 버퍼의 마지막에 추가하고, 탐색 버퍼를 디코딩된 문자의 길이만큼 이동
- 가까운 부분에 문자가 반복될 때에는 좋은 성능을 보이지만, (0, 0, α) 형태와 같이 탐색 버퍼 내에 일치하는 문자가 많으면 오히려 코드 길이가 확장되어 압축률이 저하

9. JPEG
- 2차원 이미지 데이터를 단위 블록으로 나눈 뒤 블록별로 압축하는 방법 → 대개의 경우 인접한 부분에서는 색상이 급격하게 변하지 않는다는 특성을 이용
- 처리 과정 : 블록화 → DCT → 양자화 → 엔트로피 코딩
→ 블록화 : 2차원 데이터를 n개의 8✕8 크기의 블록으로 분할 → DCT : 각 블록의 값을 변환한 후 DCT 변환을 적용
→ 양자화 : 큰 값을 작은 값으로 표현해 주는 과정으로, 이때 데이터의 손실이 발생한다. → 엔트로피 코딩 : 양자화된 블록을 지그재그와 같은 순서로 방문하여 1차원 스트링으로 표현
→ 1차원 스트링에 허프만 코딩을 적용하여 최종의 압축된 이미지를 생성한다.
- 디코딩은 인코딩의 역순으로 진행한다.

10. MPEG
- 시간순으로 나열된 2차원 데이터를 연속된 시간의 특성을 이용하여 압축하는 방법 → 대개의 경우 연속된 시간의 2차원 이미지들은 급격하게 변하지 않는다는 특성을 이용
- 움직임 보정 : 현재의 화면은 이전 화면과 이전 화면에 대한 움직임 벡터를 이용하여 생성할 수 있다.
- MPEG은 하나 이상의 JPEG 압축 이미지와 여러 개의 움직임 벡터가 반복해서 나타나는 방식으로 압축을 수행한다.


제6장 동적 프로그래밍

1. 동적 프로그래밍 방법이란?
- 최적성의 원리가 성립하는 문제에 분할정복 방법과 유사하게 작은 문제로 반복적으로 분할하여 작은 문제의 해를 구해 테이블에 저장해놓고, 이를 이용하여 입력의 크기가 더욱 큰 문제의 해를 점진적으로 만들어나가는 방법
- 점진적으로 해를 구하기 위해서 점화식을 세우고 이를 이용한다.
- 분할정복 방법에서는 → 분할되는 작은 문제가 서로 독립적이고, 작은 문제를 순환적으로 풀어 결과를 합친다.
- 동적 프로그래밍에서는 → 분할된 작은 문제가 독립적이지 않고, 작은 문제 간에 중복된 부분이 존재
2.최적성의 원리
- 주어진 문제에 대한 최적해가 분할된 작은 문제에 대한 최적해로 구성된다.
- 욕심쟁이 방법에서는 → 국부적인 최적해들이 전체적인 최적해를 구성하며, 각 단계에서 하나의 최적해만을 고려하여 전체적인 최적해를 구하지 못할 수도 있다.
- 동적 프로그래밍에서는 → 분할된 작은 문제에 대한 가능한 모든 최적해를 고려하여 다음 크기의 부분 문제에 대한 최적해가 결정  항상 최적의 결과를 얻을 수 있다.

3.동적 프로그래밍 적용 단계
① 문제의 특성을 분석하여 최적성의 원리가 성립되는지 확인한다.
② 주어진 문제에 대해서 최적해를 제공하는 점화식을 도출한다.
③ 가장 작은 부분 문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장한다.
④ 테이블에 저장된 해를 이용하여 점차 입력 크기가 더욱 큰 문제의 해를 구한다.

4.동적 프로그래밍 방법이 적용된 문제
- 모든 쌍 최단 경로 문제 → 플로이드 알고리즘, O(|V|3)
- 연쇄 행렬 곱셈
→ n개의 행렬을 연속해서 곱할 때 곱셈 회수를 최소로 하는 행렬 곱셈 순서를 구하는 문제. O(n3)
→ 최소 곱셈 횟수를 구하기 위한 점화식:
- 스트링 편집 거리
→ 스트링 X를 스트링 Y로 변환하는데 필요한 전체 편집 연산에 대한 최소 비용을 구하는 문제. O(nm)
→ 정리하기 수식과 정리하기 수식 간의 편집 거리 정리하기 수식 에 대한 점화식


제7장 NP-완전문제

1. 기본 개념
- 다항식 시간 알고리즘이 존재하는 문제를 '쉬운(tractable) 문제'라고 하고, 다항식 시간보다 더 많은 수행 시간을 요구하는 문제를 '어려운(intractable) 문제'라고 한다.
- 비결정론적(non deterministic) 튜링 기계: 하나 이상의 상태로 바뀔 수 있거나 혹은 바뀔 상태가 없을 수 있는 방식으로, 연산 결과 상황에 따라 달라질 수 있는 연산을 허용한다.
- 판정(decision) 문제와 최적화(optimization) 문제
→ 판정 문제: 문제의 해가 "예"/"아니오" 형태로 나오는 문제
→ 최적화 문제: 최소치나 최대치를 구하는 형태의 문제
- 클래스 P와 클래스 NP의 정의
→ 클래스 P: 결정론적 튜링 기계에 의하여 다항식 시간에 풀릴 수 있는 모든 판정 문제의 집합
→ 클래스 NP: 비결정론적 튜링 기계에 의하여 다항식 시간에 풀릴 수 있는 모든 판정 문제의 집합

- 문제 B에 대한 알고리즘으로 문제 A를 풀 수 있을 때, 문제 A를 문제 B로 변환(reduction)할 수 있다고 하고, 이러한 변환에 다항식 시간이 소요되면 다항식 시간 변환이라 한다.
- 어떤 부류에 속하는 모든 문제가 그 부류에 속하는 어떤 문제 R로 다항식 시간 변환 가능하다면 문제 R은 그 부류의 완전(complete) 문제이다.
완전인 문제는 그 부류의 가장 어려운 문제인 것으로 생각할 수 있다.
- 어떤 부류의 모든 문제가 문제 R로 다항식 시간 변환될 수 있지만, R이 그 부류에 속한다는 조건이 없다면 R은 그 부류에 대한 하드(hard)인 문제이다.
어떤 부류의 하드인 문제는 그 부류에 속하는 어떤 문제보다도 풀기 어렵거나 비슷한 정도로 풀기 어렵다.
- NP-하드, NP-완전 문제: NP의 모든 문제가 어떤 문제 A로 다항식 시간 변환된다면 문제 A는 NP-하드(hard) 문제이며, 여기에 A가 NP에 속한다는 조건이 함께 만족되면 그 문제는 NP-완전 문제이다.
→ NP-완전 문제는 쉬운 문제인가 어려운 문제인가? 아직 증명은 되지 않았으나 대부분의 학자는 어려운 문제일 것으로 믿고 있다.

2.NP-완전 문제의 종류
- 0/1 배낭 문제, CNF 만족성 문제, 해밀토니언 사이클 문제, 클리크 판정 문제, 버텍스 커버 문제, 파티션 문제, 3-CNF 만족성 문제, 궤 채우기 문제, TSP (외판원 문제) 등

3.NP-완전성 문제
- 어떤 문제가 NP-완전 문제인지를 보이기 위해서는 우선 알려진 하나의 NP-완전 문제가 해당 문제로 다항식 변환됨을 보이고, 해당 문제를 푸는 비결정론적 튜링 기계가 존재함을 보인다.

4.근사 알고리즘
- NP-완전 문제에 대하여 근사해를 구하는 결정론적 다항식 시간 알고리즘
- 외판원 문제의 근사 알고리즘
→ 주어진 그래프의 최소 신장 트리를 구하고, 트리에서 임의의 정점 하나를 루트로 선정한 후 깊이 우선 탐색 순서대로 정점을 나열하고 마지막에 첫(루트) 정점을 한 번 더 추가한다.
→ 근사 알고리즘으로 찾은 해는 최적해의 두 배를 넘지 않는다.
- 궤 채우기 문제의 근사 알고리즘 → 최초법, 최선법, 감소순 최초법, 감소순 최선법


제8장 병렬 알고리즘

1. 병렬 알고리즘
- 병렬 컴퓨터에서 수행되도록 작성된 알고리즘
→ 병렬 컴퓨터? 복수 개의 프로세서를 사용하여 여러 개의 명령을 동시에 처리할 수 있는 컴퓨터
- 병렬 컴퓨터의 분류 기준 → 공유 메모리 모델 vs 연결망 모델, 프로세서의 연결 형태, SIMD 모델 vs MIMD 모델

2.PRAM(Parallel Random Access Machine)
- p개의 프로세서 P0, P1, …, Pp-1과 모든 프로세서가 동등하게 접근할 수 있는 무제한의 공유 메모리로 구성된 병렬 계산 모델
- 메모리 접근 방식에 두는 제약에 따른 분류 → CRCW, CREW, ERCW, EREW
병렬 알고리즘의 성능 평가 척도
→ 속도향상률=S(n)/P(n), 시간효율성=S(n)/(p * P(n)), 작업량=p * P(n)
여기서, S(n): 입력 크기 n에 대한 최선의 순차 알고리즘의 수행시간, P(n): 입력 크기 n에 대한 병렬 알고리즘의 수행시간, p: 프로세서의 개수

3.최소값 찾기 문제에 대한 병렬 알고리즘
- n/2개의 프로세서로 O(logn) 시간에 최소값을 계산하는 CREW PRAM 방법 → 토너먼트 방식으로 최소값을 구함
- n/logn개의 프로세서로 O(logn) 시간에 최소값을 계산하는 최적화된 CREW PRAM 방법 → 블록화 방법을 써서 n개의 숫자를 logn개씩 n/logn개의 블록으로 나누어 계산
- n2개의 프로세서를 사용하는 CRCW PRAM 방법에서는 O(1) 시간에 최소값을 구할 수 있음.


제9장 유전 알고리즘

1. 유전 알고리즘(genetic algorithm)
- 자연계의 진화를 통해 관찰된 메커니즘을 모방하여 최적화 문제를 해결하기 위한 탐색 방법
- 주요 용어 → 개체, 염색체, 유전자, 개체군, 세대, 적합도 등
- 주요 연산자 → 선택, 교차, 변이

2.기본 처리 과정
1. 난수를 사용해 n개 염색체로 구성된 개체군을 형성
2. 각 염색체의 적합도 계산
3. while (새로운 개체군이 형성될 동안)
4. 선택 → 교차 → 변이 연산을 수행하여 자손 염색체 생성
5. 종료조건 검사 또는 단계2부터 반복
- 처리 시 주요 고려 사항 및 매개변수 → 염색체의 인코딩 방법, 선택 방법, 적합도 계산 방법, 교차 위치 및 교차 확률, 변이확률, 개체군의 크기

3.주요 연산자
- 염색체의 인코딩 (표현하려는 해에 대한 정보를 염색체의 형태로 표현하는 방법
→ 인코딩 방법의 선정은 교차 및 변이연산의 유형에 영향을 미침)
→ 이진 인코딩 : 각 염색체를 0/1의 나열로 표현
→ 순열 인코딩 : 각 염색체의 값들이 순서를 나타내는 값을 가짐
→ 값 인코딩 : 직접 값(숫자, 문자 등)을 사용
→ 트리 인코딩 : 각 염색체가 객체의 트리 형태로 표현

- 선택(개체군으로부터 부모가 되어 교차를 수행할 염색체를 선택)
→ 룰렛 힐 선택 : 염색체의 적합도에 비례하여 선택
→ 순위 선택 : 각 개체에 대해 순위를 지정한 후, 이 순위를 기준으로 적합도 점수를 할당
→ 토너먼트 선택 : 0~1 사이의 난수와 기준값의 비교를 통해서 부모 염색체를 선정
→ 엘리티즘 : 몇 개의 가장 좋은 염색체에 대해서는 이후의 연산 없이 새로운 개체군으로 그대로 전달하는 방법

- 교차(선택된 두 염색체의 특징을 부분 결합하여 하나의 새로운 특징을 가진 자손 염색체를 생성)
→ 단일점 교차 : 하나의 교차 위치를 기준으로 교차
→ 두 점 교차 : 두 개의 교차 위치를 기준으로 교차
→ 균등 교차 : if 각 유전자에 대한 난수 > 기준값 then 첫 번째 부모 염색체의 해당 유전자를 가짐
else 두 번째 부모 염색체의 해당 유전자를 가짐
→ 산술 교차 : AND, 평균과 같은 특정 산술 연산을 적용
- 변이(새로 생성된 자손 염색체의 일부분의 유전자를 임의로 변경 → 부모 염색체에는 없는 속성을 부여)
→ if 각 유전자에 대한 난수(0~1) < 변이확률 then 해당 유전자의 값을 임의로 변경