본문 바로가기

그리디 알고리즘

 (3)
Chap 4-7. 허프만 압축 파일을 저장할 때 최대한 작게 저장하는 것이 효율적일 것이다. 데이터 압축 문제는 데이터를 코드화하는 효율적인 방법을 찾는 것이다. (1) 허프만 코드라고 하는 코드화 방식 (2) 주어진 파일을 허프만 코드화하는 탐욕적인 알고리즘 파일은 기본적으로 이진코드를 사용해서 표현한다. 코드화 방식에서 각각의 문자는 코드워드라고 하는 유일한 이진 문자열로 각 문자를 표현한다. 이 중 길이가 고정된 이진 코드는 각각의 문자를 표현하는 bps가 일정하다. 예를 들어 a, b, c를 코드화한다. a : 00, b: 01, c:11 ababcbbbc ⇒ 000100011101010111 (18비트가 필요함) 그러나 길이가 변하는 이진 코드를 사용하면 좀 더 효율적인 코드화 방식을 사용할 수 있다. → 각 문자를 다른 길..
Chap4-4. 부분 배낭 문제 배낭 문제란? 배경 = 물건 n개의 집합 S = {1, 2, 3, 4, ..., n}이 있고 물건 무게 W = {W1, W2, W3..., Wn}, 물건을 팔았을 때의 가치(이윤) P = {P1, P2, P3, ..., Pn }가 있다고 하자. 조건 = W은 물건 무게 이므로 Wi > 0이어야 한다. P도 Pi > 0이어야 한다. 자신이 배낭에 물건을 가지고 가서 시장에서 판다고 가정하자 배낭에 넣을 수 있는 무게는 제한되었다. 최대 무게를 M이라고 하자 1 ~ n까지의 Wi * Xi ≤ M 이면서 (x= 물건의 개수) 1 ~ n 까지의 Pi * Xi 를 최대화하는 방향을 찾아야 한다. • n개의 물건이 각각 1개씩 있고, • 각 물건은 무게와 가치를 가지고 있으며, • 배낭이 한정된 무게의 물건들을 담..
Chap 4. 그리디 알고리즘 그리디 알고리즘 그리디 알고리즘은 "최적화 문제를 해결하는 알고리즘" 최적화 (optimization) 문제 가능한 해들 중에서 가장 좋은 (최대 또는 최소) 해를 찾는 문제 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림 그리디 알고리즘은 (입력) 데이터 간의 관계를 고려하지 않고 수행 과정에서 매 순간 ‘욕심내어’ 최소값 또는 최대값을 가진 데이터를 선택 이러한 선택을 ‘근시안적’인 선택이라고 말하기도 함 전체를 끝까지 보는 것이 아니라 해당 시점에서 최적의 선택을 계속적으로 누적하여 마지막 결과까지 진행하는 방법이므로 "근시안적" 이라고 표현함 그리디 알고리즘 방법 = 근시안적인 선택으로 부분적인 최적해를 찾고, 이들을 모아서(축적하여) 문제의 최적해(전역 해)를 얻는다. [특징] (1) ..

티스토리툴바