탐욕 알고리듬
그 순간 최적(locally optimal) 의 해법을 찾는 방법
최종적으로 최적(globally optimal) 해법이 안나올 수 있음
근사(approximation) 알고리듬
장점
최종적으로 최적인 해법을 못 찾을 수 있으나 충분히 훌륭한 결정을 빠르게 내림
사용하기 적합한 경우
제대로 된 해법을 구하는 알고리듬의 복잡도가 너무 높은 경우
적당히 좋은 해법도 상관없는 경우
동적 계획법을 사용할 수 없는 경우(중복되는 하위 문제가 없음)
사용할 수 있는 경우
최적 부분구조
그리디 선택 속성으로 한번 내린 결정은 다시 돌아보지 않음
사용 팁
보통 최소/최대화 문제에 사용
그리디의 다양한 선택지가 있는 경우 모두 시도하거나 반례를 통해 제거
정렬을 해야 속도가 빨라질 수도 있음
그리디 접근법으로 풀 수 있는 문제
인터벌 파티셔닝(interval partitioning)
지연 시간 최소화(minimizing lateness)
다익스트라의 최단 경로(Dijikstra's shortest path)
운영체제의 job 스케줄링
k-센터 문제(k-center problem)
결정 트리 학습법(decision tree learning)
허프만 코딩(Huffman coding)
등...
허프만 (Huffman)
허프만 코딩
입력 문자들에 적합한 가변 부호(code) 를 선택하는 알고리듬
최적 접두어 코드(optimal prefix code) 를 사용
ㄴ 헷갈리지 않고 각 코드를 제대로 된 문자로 디코딩 가능
ㄴ 어떤 문자에 할당된 코드는 다른 문자에 할당된 코드의 접두어가 아님
자주 등장하는 문자에 비트 수를 조금, 가끔 등장하는 문자에 비트 수 많이 사용
허프만 트리
이진 트리
문자는 리프 노드에 위치
빈도가 높은 문자일수록 루트에 가까움(자주, 가끔 등장 문자를 구분하여 비트를 적용하는 이유)
루트부터 리프까지의 경로가 그 문자의 비트 패턴
0 왼쪽 자식으로 이동, 1 오른쪽 자식으로 이동
허프만 트리 만드는 과정
빈도가 가장 낮은 두 행을 선택
두 문자가 리프가 되도록 트리를 만듦
트리를 원래 표에 다시 넣고 재정렬
모두 트리로 합쳐질 때 까지 위 순서대로 반복
허프만 디코딩 - 의사 코드
인코딩 된 메시지의 비트를 순서대로 고려
1.트리에서 비트 값과 일치하는 변(edge) 을 따라감
2.리프 노드에 도달하지 않았다면 1로 돌아감
3.리프 노드에 있는 문자를 출력 후 루트 노드로 복귀
4.모든 비트를 읽지 않았다면 1로 돌아감
전제 조건으로 인코딩에 사용한 허프만 트리를 알고 있는 경우
문자 빈도 표 또는 허프만 트리를 같이 보내어 디코딩할 때 사용
데이터 압축
원본 데이터보다 적은 비트 수로 정보를 표현하는 방법
주 용도는 저장공간 절약, 전송속도 단축
압축 알고리듬 및 파일 포멧
무손실 압축 : ZIP, RLE(Run-Length Encoding)
원본 데이터를 완전 복구 가능
비교적 압축 파일 크기가 큼
데이터 분석을 통한 알고리듬 개발
손실 압축 : JPEG, MP3
원본 데이터와 비슷하게만 복구(사람은 차이를 못느낄 수 있음)
비교적 압축 파일 크기가 작음
데이터 분석을 통한 알고리듬 개발
인간의 이해를 통한 알고리듬 개발
이미지 품질 손상 최소화 과정
JPEG 파일에 용량을 많이 줄여도 이미지에 큰 차이가 없는 이유는 양자화가 사용되는데
JPEG 압축은 이미지 주파수를 데이터로 변형하여 비슷한 주파수끼리 합치고 양자화 후
시각적인 색상 정보로 변환하여 사람이 확인할 때 차이를 느끼지 못한다
양자화(quantization)
원본에서 비슷한 값들을 합쳐 값의 개수를 줄이는 방법
따라서 값 표현에 사용하는 비트 수를 줄일 수 있음
연산 자체는 매우 간단
품질 손상을 최소화할 수 있는 방법 고안이 중요
ㄴ JPG 는 주파수 데이터로 바꾼 뒤(DCT) 양자화
ㄴ DXT1 이미지(게임) 는 4x4 블록마다 16비트 RGB 5:6:5 색상 둘을 사용
ㄴ 보간
문자열 전송하기
| b | a | n | a | n | a | | b | a | b |
위와 같은 문자열을 전송하기 위해 ASCII 를 통해 이진수로 인코딩 필요
문자열 (등장 횟수) = 이진수
a(4) = 1, b(3) = 01, n(2) = 001, (1) = 000
위 이진수로 허프만 생성 규칙에 의한 트리를 만들어서 전송 문제 해결
