알고리즘 과제 범위 요약

2020학년도 1학기 출석수업대체과제물

---

                             ① 알고리즘의 대표적인 설계기법인

                             분할정복 방법(2장),

                             동적 프로그래밍 방법(3장),

                             욕심쟁이 방법(4장)의 원리 및 특징을 비교 설명하고,

                           

 

                            ② 각 방법들이 적용된 알고리즘(또는 문제)의 종류와

                             각각의 특징 / 성능을 간단히 정리하시오.

 

                                 교재 2~4장 (강의 3~8강)

                                 

 

                                  A4 2~3매 (표지제외)

                                  제출파일: 아래한글 또는 MS-word 파일

                                  제출방법: 온라인 제출

 

---

분할정복 방법

1. 분할정복 방법
- 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법
- 분할된 작은 문제는 서로 독립적이며, 단지 크기만 작아진 원래 문제와 동일한 문제임
- 각 순환 호출마다 분할, 정복, 결합의 단계를 거침

2. 이진 탐색
- 정렬된 상태로 주어진 원소들을 절반씩 줄여가면서 원하는 키값을 찾는 문제 

→ 탐색을 수행할 때마다 탐색 대상이 되는 원소의 개수가 1/2씩 감소

 

- 성능 : T(n)=T(n/2)+Θ(1), T(1)=Θ(1) → Θ(logn)

 

- 정렬된 리스트에 대해서만 적용 가능 

→ 삽입/삭제 시 정렬 상태의 유지를 위해 자료의 이동이 발생 

→ 삽입/삭제 연산이 빈번한 응용에는 부적합

3. 퀵 정렬
- 특정 원소(‘피벗’)를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 정렬 방식 → 피벗이 제자리를 잡도록 정렬하는 방식
- 분할 함수 Partition() : 피벗을 기준으로 주어진 배열을 두 부분배열로 나누는 함수 → Θ(n)
- 최악의 경우 : 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열로 분할되는 경우 → 피벗이 항상 최솟값/최댓값이 되는 경우 → 입력 데이터가 정렬되어 있고 피벗을 첫 번째로 원소로 사용하는 경우 → T(n)=T(n-1)+Θ(n), T(1)=Θ(1) → O(n^2)
- 최선의 경우 : 피벗을 중심으로 항상 동일한 크기의 부분배열로 분할되는 경우 → 피벗이 항상 중간값이 되는 경우 → T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
- 평균적인 경우 : 부분배열의 모든 분할 비율에 따른 수행시간의 평균 → O(nlogn)
- 피벗 선정에 임의성만 보장되면 최악의 성능 O(n^2)이 아닌 평균적인 성능 O(nlogn)을 보일 가능성이 매우 높은 정렬 알고리즘


4. 합병 정렬
- 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할하고, 각각의 부분배열을 순환적으로 정렬한 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 정렬 방식
- 합병 함수 Merge() : 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만드는 함수 → Θ(n)
- 성능 : T(n)=2T(n/2)+Θ(n), T(1)=Θ(1) → O(nlogn)
- 입력 크기 n 만큼의 추가적인 저장 장소가 필요

5. 선택 문제
- 임의의 순서로 주어진 n개의 원소에 i번째로 작은 원소를 찾는 문제 

→ i=1이면 최솟값, i=n/2이면 중간값, i=n이면 최댓값을 찾는 문제가 됨

 

- 최소값(또는 최댓값) 찾기 : n개의 숫자에 대해서 최솟값/최댓값을 찾기 위해서는 최소한 (n-1)번의 비교가 필요 → O(n)

 

- 최소값과 최댓값 모두 찾기 : 모든 원소를 두 개씩 짝을 이루어 큰 값과 작은 값을 찾고, 큰 값과 최댓값 그리고 작은 값과 최솟값의 비교를 수행 → (3n)/2-2번의 비교

 

- 퀵 정렬의 분할 함수를 이용한 선택 문제 → 최악 O(n^2), 평균 O(n)

 

- 중간값들의 중간값을 이용한 선택 문제 

→ 크기 n인 배열의 원소를 5개씩 묶어 ⌊n/5⌋개의 그룹을 형성한 후, 각 그룹에 대해서 중간값을 찾고, 다시 각 그룹의 중간값들을 대상으로 다시 중간값을 취해서 사용 

→ 한 번 분할할 때마다 3×⌈⌊n/5⌋/2⌉개의 원소가 탐색 대상에서 제외 

→ 최악 O(n), 평균 O(n)

 

동적 프로그래밍

 1. 동적 프로그래밍 방법

- 문제의 크기가 작은 소문제에 대한 해를 테이블에 저장해 놓고, 

이를 이용하여 크 기가 보다 큰 문제의 해를 점진적으로 만들어가는 상향식 접근 방법 

- 분할정복 방법과 달리 소문제들은 서로 독립일 필요가 없음 

- 최적화 문제(최솟값 또는 최댓값을 구하는 문제)에 주로 사용 

- 최적성의 원리(“주어진 문제에 대한 최적해는 소문제에 대한 최적해로 구성된다”)가 반드시 만족되어야만 적용 가능 

 

- 적용 단계 : 

① 최적해를 제공하는 점화식 도출 → 

② 가장 작은 소문제부터 점화 식의 해를 구한 뒤 테이블에 저장 → 

③ 테이블에 저장된 해를 이용하여 점차적으 로 큰 상위 문제의 해를 구함

 

2. 피보나치 수열 - 피보나치 수열의 순번에 해당하는 수를 찾는 문제
- 점화식 : f(n) = { 

f ( n - 1 ) + f (n - 2 )  n>=2인 경우

                      1       n = 1 인 경우

                                    0       n=0 인경우               }

 

- 성능 : O(n) 

- 피보나치 수열의 소문제는 독립이 아니므로 분할정복 방법을 적용하면 비효율적

 

 

 

1.  스트링 편집 거리 문제

 

- i 또는 j가 0인 경우에 대해 E(i,j)를 테이블에 저장 

→ i를 1부터 n까지, j를 1부터 m까지 하나씩 증가시키며 테이블에 저장된 E(i-1,j), E(i,j-1), E(i-1,j-1)의 해와 연 산 비용을 이용하여 E(i,j)를 구해 테이블에 저장하는 과정을 반복 → 최적해는 E(n, m) 

 

- 성능 : O(nm)

 - 테이블 E와 동일한 크기의 테이블 P(i,j)에 E(i,j)를 결정한 연산이 삭제, 삽입, 변경 중 어느 것인지 저장해두면 편집 거리에 해당하는 실제 편집 연산을 구할 수 있음

 

 

 

2. 모든 정점 간의 최단 경로 

- 가중 방향 그래프 G=(V,E)에서 모든 조합의 두 정점 간의 최단 경로(“두 정점을 연 결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로”)를 구하는 문제 

 

- 플로이드 알고리즘 : 간선의 인접 행렬 표현을 활용하여 경유할 수 있는 정점의 범 위를 1인 경로부터 시작해서 |V|인 경로까지 단계적으로 범위를 늘려 가면서 최단 경로를 구하는 알고리즘 

 

→ 가중치의 합이 음수인 사이클이 없는 경우에 적용 가능

- D ( i, j, k ) : 정점 1부터 k까지의 정점만 경유할 수 있는 정점 i에서 j까지의 최단 경로

 

- k=0인 경우, 즉 간선의 인접행렬로 테이블을 초기화 

→ k를 1부터 n까지 하나씩 증가시키며 1 <= i, j <= |V| 인 i, j에 대해 테이블에 저장된 D(i,j), D(i,k), D(k,j)를 이용하여 새로운 D(i,j)를 구해 테이블에 저장하는 과정을 반복 

→ 최적해는 D( i , j , n ) 

 

- 성능 :  O ( |V|^3)

 

- |V| X |V| 크기의 테이블 P(i,j)에 D(i,j)를 결정한 값이 정점 k를 경유하는 경로인 경 우 k를 저장해두면 정점 i에서 j까지의 최단 경로 자체를 구할 수 있음

 

3. 저울 문제 

- 무게 M인 물체를 n개의 추를 이용하여 양팔 저울로 달 수 있는지 확인하는 문제 

→  추는 저울의 한쪽 팔에만 올릴 수 있으며, 추의 무게 Wi ( 1 <= i <= n 와 물체의 무게 M은 모두 정수라고 가정

 

- S (i, k ) : 1번부터 i번까지의 추를 이용하여 무게 k인 물체를 달 수 있으면 1, 없으 면 0

 

 

- i=0인 경우와 k=0인 경우의 S(i,k)를 테이블에 저장 

→ i를 1부터 n까지, k를 1부 터 M까지 하나씩 증가시키며 테이블에 저장된 S(i-1,k) 와  S(i-1, K-Wi)를 이용하여 S(i, k)를 구해 테이블에 저장하는 과정을 반복 → 최적해는 S ( n , M )

 

- 성능 : O(nM)

 

- k를 1씩 증가시키는 대신 추의 무게의 최대공약수 단위로 증가시키면 더 효율적

 

- S ( n ,M ) = 1 인 경우 테이블 S와 Wi를 이용하면 M을 만드는데 사용된 추를 구할 수 있음

 

- M > 2^n 이면 추의 조합 가능한 모든 경우를 따져보는 직관적인 방법보다 비효율적

 

- 추의 무게와 물체의 무게가 정수가 아닌 경우 → 동적 프로그래밍 방법 적용 불가

 

 

 

욕심쟁이 알고리즘

 

1. 욕심쟁이 방법
- 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 여겨지는 국부적인 최적해를 선택하므로써 전체적인 최적해를 구하는 방법
- 소문제(각 단계)에서 하나의 최적해만을 고려하므로 항상 전체적인 최적해를 구한다는 것을 보장하지 못함

 

2. 동전 거스름돈 문제
- 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하여 거스름돈을 돌려주는 방법을 찾는 문제 → 단순히 액면가가 가장 큰 동전부터 최대한 사용해서 거스름돈을 만듦
- 성능(n: 동전의 종류) : O(n)
- 동전의 액면가가 임의로 주어지는 일반적인 경우는 욕심쟁이 방법으로 해결 불가

 

3. 배낭 문제
- 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체의 이익의 합이 최대가 되도록 물체를 넣은 방법을 찾는 문제 → 물체를 쪼개서 넣을 수 있다고 가정 → 단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣음
- 성능(n: 물체의 개수) : O(n), 그러나 물체의 무게/이익이 단위 무게당 이익에 따라 정렬하는 경우까지 고려하면 O(nlogn)
- 물체를 쪼갤 수 없는 형태의 0/1 배낭 문제는 욕심쟁이 방법으로 해결 불가

 

4. 최소 신장 트리
- 신장 트리(주어진 그래프에서 모든 정점을 포함하는 연결된 트리) 중에서 가중치의 합이 가장 작은 트리 → 욕심쟁이 방법을 적용한 크루스칼 알고리즘과 프림 알고리즘으로 구함
- 크루스칼 알고리즘 : 간선이 하나도 없는 상태에서 시작해서 가중치가 가장 작은 간선부터 하나씩 사이클을 형성하지 않으면 추가시키는 방법 → 사이클을 형성하지 않으려면 서로 다른 연결 성분에 속하는 간선을 선택해야 함 → 성능 : O( |E| log |E| )
- 프림 알고리즘 : 임의의 한 점에서 시작해서 연결된 정점을 하나씩 선택해서 추가시키는 방법 → 이미 선택된 정점 집합 S와 미선택 정점 집합 V-S를 잇는 간선 중에서 가중치가 가장 작은 간선을 선택해서 추가 → 성능 : 인접 행렬로 구현하면 O(|V|^2), 인접 리스트로 구현하고 힙을 사용하면 O( ( |V| + |E| ) log |V|)


5. 단일 출발점 최단 경로
- 특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 → 욕심쟁이 방법을 적용한 데이크스트라 알고리즘으로 구함
- 데이크스트라 알고리즘 : 

음의 가중치를 갖는 간선이 없는 경우에 적용 가능 

→ 거리 d[v] : 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이 

→ 출발점에서 시작해서 미선택 정점 집합 V-S에서 거리 d[]가 최소인 정점 u를 선택하고, 

u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리를 비교해서 작은 값을 새로운 거리값으로 조정하는 과정을 반복
- 성능 : 인접 행렬로 구현하면 O(|V|^2), 인접 리스트로 구현하고 힙을 사용하면 O(( |V| + |E| ) log |V|)

 

6. 작업 스케줄링 문제
- 가장 적은 개수의 기계를 사용하여 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제 

→ 각 단계에서 시작 시간이 빠른 작업을 우선적으로 선택해서, 충돌이 발생하지 않으면 해당 기계에 할당하고 충돌이 발생하면 새로운 기계에 할당하는 과정을 반복
- 성능(n : 작업의 개수) : O(nlogn)

 

7. 작업 선택 문제
- 하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제 

→ 각 단계에서 완료 시간이 빠른 작업을 우선적으로 선택해서, 충돌이 발생하지 않으면 기계에 할당하고 충돌이 발생하면 해당 작업을 버리는 과정을 반복
- 성능(n : 작업의 개수) : O(nlogn)

 

8. 허프만 코딩
- 문자가 텍스트에서 출현하는 빈도수를 이용하여 출현 빈도수가 높은 문자는 짧은 코드를 부여하고, 출현 빈도수가 낮은 문자는 상대적으로 긴 코드를 부여해서 전체 텍스트의 길이를 줄이는 방법 → 접두부 코드, 최적 코드
- 인코딩 과정 :

 ① 주어진 텍스트에서 각 문자의 출현 빈도수를 계산, 

② 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여, 

③ 주어진 텍스트의 각 문자를 이진 코드로 변환하여 인코딩된 텍스트를 생성
- 허프만 트리 : 

 각 문자에 이진 코드를 부여하기 위해서 욕심쟁이 방법을 적용하여 상향식으로 만들어지는 전 이진 트리

→ 각 문자는 리프 노드에 나타나며, 각 노드는 빈도수로 표시하고, 좌우의 두 간선에는 각각 0과 1로 레이블함 

→ 각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 큰 트리를 생성(합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성, 부모 노드의 빈도수는 두 자식 노드의 빈도수의 합으로 표시)하는 과정을 반복

→ 허프만 트리는 유일하지 않음

 

- 디코딩 : 압축된 텍스트를 1비트씩 읽으면서 허프만 트리의 루트 노드로부터 따라 내려오다가 리프 노드에 도착하면 리프 노드에 해당하는 문자를 출력하고, 루트 노드로부터 반복

- 성능(n: 문자 집합의 크기, m: 텍스트의 길이) : O( nlogn + m )

- 각 문자의 빈도수를 모르면 텍스트를 두 번 읽어야 함 → 실용성 결여
- 디코딩을 위해 필요한 정보를 인코딩 메시지의 헤더에 포함시켜야 함 → 실제 압축률 저하

 

 

 

 

 

내용 요약 이제.............

 

줄여서 과제해야지...........