05 - 1. 그리디 알고리즘
그리디 알고리즘? 그리디 알고리즘(greedy algorithm) 또는 탐욕 알고리즘은 매 단계에서 가능한 가장 최선의 선택을 하는 알고리즘이다. 예를 들면, 지도에서 전체 최단 경로를 구하려 하는 경우, 출발 지점부터 아직 방문하지 않은 지점 중 가장 가까운 지점까지의 경로를 찾는 것을 목적 지점에 다다를 때까지 반복하는 것이다. 이러한 방법이 구글 맵같은 상용 소프트웨어에서 사용되는 다익스트라 최단 경로 알고리즘의 기본 개념이 된다. 그리디 접근 방식은 너무 단순하기 때문에 최적 부분 구조 속성과 그리디 선택 속성이라는 두 속성을 만족하는 문제에 대해서만 사용할 수 있다. (통신, 상수도관 네트워크, 전력 네트워크, 회로 설계 등 => MST) 그리디 알고리즘의 요구 조건 - 최적 부분 구조(opti..
04 - 3. 맵리듀스: 더 높은 추상화 레벨의 분할 정복 기법
이 절에서는 약간 다른 관점에서 분할 정복을 다룬다. 소프트웨어를 단일 컴퓨터 계산 능력 이상으로 확장하고 컴퓨터 군집(cluster)를 이용하여 문제를 해결하고자 할 때 맵리듀스를 이용한 분할 정복 기법을 적용한다. 맵리듀스는 대규모 데이터셋을 생성하고 처리하기 위한 프로그래밍 모델 및 구현이다. 사용자는 키와 값의 쌍을 처리하여 중간 단계의 키/값 쌍을 생성하는 맵 함수와 같은 중간 단계 키에 해당하는 모든 중간 단계 값을 병합하는 리듀스 함수를 지정한다. 맵리듀스 프로그래밍 모델에 대한 오픈 소스 구현 코드 중 가장 대표적인 것은 하둡(Hadoop)이다. 하둡은 하둡 분산 파일 시스템(HDFS, Hadoop Distributed File System)에 저장된 데이터를 다루는 맵과 리듀스 함수를 작..
04 - 2. 선형 시간 선택, 분할 정복 기법 C++ 표준 라이브러리 함수
04 - 1에서 살펴본 분할 정복 알고리즘은 문제를 정확하게 두개의 부분 문제로 나누었다. 그러나 각 단계에서 문제를 두개 이상으로 분할하는 것이 더 유리한 경우도 있다. 이러한 문제 중 하나인 선형 시간 선택(Linear Time Selection)에 대해 알아보도록 하자. 예를 들어 정렬되지 않은 원소의 집합 S가 주어졌을 때, 여기서 i번째로 작은 원소를 찾으려 한다. 가장 단순한 해법은 전체 S를 정렬하고, 이 중 i번째 원소를 선택하는 것이다. 이 경우 시간 복잡도는 O(nlogn)이다. 반면, 분할 정복 방법을 사용하면 O(n)의 시간 복잡도로 구할 수 있다. 선형 시간 선택 a. 입력 벡터 V가 주어지면 여기서 i번째로 작은 원소를 찾으려고 한다. b. 입력 벡터 V를 V1, V2, ... ..