알고리즘 1강 (알고리즘 소개)

 학습개요

1. 알고리즘의 첫 번째 강의 시간으로서 알고리즘 전반에 걸친 기본적인 개념을 소개한다. 우선 알고리즘의 필요성과 정의를 간단히 살펴본 후, 알고리즘의 대표적인 설계 기법들에 대해서 중점적으로 학습한다.

학습목표

1. 알고리즘의 중요성과 개념을 이해할 수 있다.
2. 대표적인 알고리즘 설계 기법들의 종류와 개념을 이해할 수 있다.
3. 거스름돈 문제와 배낭 문제의 개념, 동작 원리 및 특성을 이해할 수 있다.

 주요용어

1. 알고리즘(algorithm)
   주어진 문제에 대해 하나 이상의 결과를 생성하기 위해 모호하지 않고 단순 명확하며 컴퓨터가 수행할 수 있는 유한개의 일련의 명령을 순서에 따라 구성한 것
2. 욕심쟁이 방법(greedy method)
   해를 구하는 일련의 선택 과정마다 해당 단계에서 ‘가장 최선‘이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
3. 거스름돈 문제(coin change problem)
   가게에게 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
4. 배낭 문제(knapsack problem)
   배낭의 용량을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 배낭에 물체를 넣는 방법을 찾아내는 문제
   * 0/1 배낭 문제 : 배낭에 넣는 물체를 쪼갤 수 없다는 가정이 있는 배낭 문제로서, 이 경우에는 욕심쟁이 방법으로 해결할 수 없는 NP-완전문제가 된다.
5. 분할정복 방법(divide-and-conquer method)
   순환적으로 문제를 푸는 하향식 접근 방식으로, 주어진 문제의 입력을 더 이상 쪼갤 수 없을 때까지 2개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방법
6. 동적 프로그래밍 방법(dynamic programming method)
   주어진 문제의 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 저장해 놓고 이를 이용하여 입력 크기가 보다 큰 원래의 문제를 점진적으로 해결하는 상향식 접근 방법

 

 

 

정리하기

1. 1. 기본 개념
   ⦁ 알고리즘 → 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야 할 명령어들을 단계적으로 나열한 것
   - 만족해야 할 조건 → (입출력, 명확성, 유한성, 유효성) + (실용적 관점에서는 ‘효율성’도 중요)
2. 2. 알고리즘 설계
   ⦁ 알고리즘 생성 과정: 설계 → 표현(기술) → 정확성 분석 → 효율성 분석
   ⦁ 많은 부류의 문제에 적용될 수 있는 대표적인 설계 방법 → 욕심쟁이 방법, 분할정복 방법, 동적 프로그래밍 방법
   ⦁ 욕심쟁이 방법
   - 해를 구하는 일련의 선택 단계마다 전후 단계의 선택과는 무관하게 해당 단계에서 가장 최선이라고 볼 수 있는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
   - 한계 → 국부적인 최적해가 항상 전체적인 최적해를 구성하지 못하는 경우도 있음
   - 적용 알고리즘/문제 → 거스름돈 문제, 배낭 문제, 최소 신장 트리(크루스칼 알고리즘, 프림 알고리즘), 단일 출발점 최단 경로(데이크스트라 알고리즘)
   - 거스름돈 문제 → 가게에서 고객에게 돌려줄 거스름돈이 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제 → 동전의 액면가가 일반적인 경우에는 욕심쟁이 방법 적용 불가
   - 배낭 문제 → 배낭의 용량을 초과하지 않는 범위 내에서 배낭에 들어 있는 물체들의 이익의 합이 최대가 되도록 물체를 넣는 방법을 찾는 문제 → 물체를 쪼개서 넣을 수 없는 ‘0/1 배낭 문제’는 욕심쟁이 방법 적용 불가
   ⦁ 분할정복 방법
   - 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방식
   - 분할된 문제는 입력 크기만 작아졌을 뿐 원래 문제와 동일하며 서로 독립적
   - ‘분할’-‘정복’-‘결합’의 단계로 구성
   - 적용 알고리즘/문제 → 이진 탐색, 퀵 정렬, 합병 정렬
   ⦁ 동적 프로그래밍 방법
   - 입력의 크기가 가장 작은 부분 문제부터 해를 구하여 저장해 놓고 이를 이용해서 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법
   - 분할된 문제는 입력 크기만 작아졌을 뿐 원래 문제와 동일하며 서로 독립적일 필요는 없음
   - 적용 알고리즘/문제 → 모든 정점 쌍 간의 최단 경로를 구하는 플로이드 알고리즘, 교재 5장(행렬의 연쇄적 곱셈 문제, 최장 공통 부분 수열 문제)