2020년 1학기 출석수업대체과제물 [알고리즘]

소개

2020년 1학기 알고리즘 출석대체 과제입니다.

1. 알고리즘의 대표적인 설계기법인 분할정복 방법, 동적 프로그래밍 방법, 욕심쟁이 방법의 원리 및 특징을 비교 설명하고,
2. 각 방법들이 적용된 알고리즘(또는 문제)의 종류와 각각의 특징/성능을 간단히 정리 하시오.

목차

1) 분할정복 알고리즘
① 이진 탐색
② 퀵 정렬
③ 합병 정렬
④ 선택 문제

2) 동적 프로그래밍 알고리즘
① 연쇄 행렬 곱셈
② 스트링 편집 거리
③ 모든 정점 간의 최단 경로
④ 저울 문제

3) 욕심쟁이 알고리즘
① 동전 거스름돈 문제
② 배낭 문제
③ 최소 신장 트리
④ 최단 경로
⑤ 작업 스케줄링 문제
⑥ 작업 선택 문제
⑦ 허프만 코딩

본문내용

1) 분할정복 알고리즘
주어진 문제를 나눌 수 없을 때 까지 순환적으로 분할해 답를 구하고 그 답을 결합하여 문제를 해결하는 하향식접근 방법이다. 각 순환 호출마다 분할과 정복, 결합 단계를 거치며 분할된 작은 문제는 원래 문제와 동일하며 크키만 작아지고 독립적이다.
① 이진 탐색
정렬된 상태로 원소들을 절반씩 나누어 가운데 원소부터 탐색 범위를 반씩 줄이면서 원하는 키값을 찾는 방식으로 탐색을 수행할 때마다 대상원소의 개수가 1/2씩 감소한다. 삽입/삭제가 빈번하여 응용에 부적합하고 정렬된 리스트에만 적용이 가능하다.
- 성능: T(n)=T(n/2)+Θ(1), T(1)=Θ(1) → Θ(logn)
② 퀵 정렬
배열을 피벗을 기준으로 두 부분배열로 분할 후 각 부분배열에 대해 퀵 정렬을 순환적으로 적용하는 방식.
- 최악의 경우 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열로 분할
T(n)=T(n-1)+Θ(n), T(1)=Θ()1 → O(n^2)

참고자료

· 없음