티스토리 뷰
최소값 찾기
최소값 찾기에서 알고리즘1과 알고리즘2 중에서 어떤 것이 더 효율적인가?
뒤섞인 카드에서 원하는 카드 찾기
카드를 섞어서 뒤집어 놓았다. 이 카드 중에서 K를 찾아라!
순차 탐색
순서대로 나열된 카드에서 원하는 카드 찾기
이진 탐색
알고리즘 설계 기법
문제와 제반 조건이 매우 다양 → 일반적인 기법은 없음
대표적인 설계 기법
- 분할정복 방법
- 동적 프로그래밍 방법
- 욕심쟁이 방법
분할정복 방법
- 분할
＊ 주어진 문제를 여러 개의 작은 문제로 분할
- 정복
＊ 작은 문제들을 순환적으로 분할. 만약 작은 문제의 크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해가 구해짐
- 결합
＊ 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함
- 퀵 정렬, 합병 정렬, 이진 탐색
동적 프로그래밍 방법
최적화 문제의 해를 구하기 위한 상향식 접근 방법
- 주어진 문제를 여러 개의 부분 문제로 분할
- 가장 작은 부분 문제부터 해를 구하여 테이블에 저장 테이블에 저장된 해를 이용하여 입력 크기가 큰 원래의 문제를 점진적으로 해결 모든 정점 쌍의 최단 경로를 구하는 플로이드 알고리즘
욕심쟁이 방법
해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 그 단계에서 ‘가장 최선’이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략을 취하는 방법
- 희망적 → 각 단계의 최적해를 통해 전체적인 최적해를 만들어 내지 못할 수 있음의 의미
- 거스름돈 문제, 배낭 문제
거스름돈 문제
고객에게 돌려줄 거스름돈이 T만큼 있을 때 고객이 받을 동전의 개수를 최소로 하면서 거스름돈을 돌려주는 방법을 찾는 문제
배낭 문제
배낭의 용량 M을 초과하지 않는 범위에서 배낭에 들어있는 물체의 이익의 합이 최대가 되도록 물체를 집어넣는 방법을 찾아내는 것
- 물체 Xi에는 무게 wi와 이익 pi가 부여되어 있음 (i=1, 2, …, n)
- 물체를 쪼갤 수 있음
배낭 문제
문제 정의
M = 10, n = 4
(p1, p2, p3, p4) = (15, 20, 9, 14)
(w1, w2, w3, w4) = (3, 5, 3, 4)
단위 무게당 이익이 가장 큰 물체부터 최대한 배낭에 넣는다
┌ P1 P2 P3 P4 ┐
│ ── , ── , ── , ──│
└ W1 W2 W3 W4 ┘
최대 이익
최대이익 = p1 + p2 + p4×½ = 42