알고리즘/탐욕 알고리즘(Greedy) (2) 썸네일형 리스트형 [알고리즘] 허프만 코딩 - 코딩밥상 허프만 코딩이란? 음악 저장 파일 포맷인 mp3와 이미지 저장 파일 포맷인 JPEG의 공통점은 바로 이 허프만 코딩을 이용하는 압축 데이터 포맷이라는 점입니다. 즉 이 알고리즘은 성능이 가장 우수한 압축 알고리즘 중 하나입니다. 고정 길이 코드와 접두어 코드 허프만 코딩을 이해하려면 먼저 몇가지 기본 지식을 알아야 합니다. 우선 고정 길이 코드(Fixed Length Code)는 말 그대로 모든 코드의 길이가 똑같은 값을 갖는 코드 체계를 말합니다. 코딩을 하면서 자주 사용하는 ASCII가 대표적인 예 입니다. 고정 길이 코드가 연산의 편의를 위한 것이라면 가변 길이 코드(Variable Length Code)는 저장 공간 절약을 위해 사용됩니다. 그만큼 데이터 처리는 상당히 번거롭겠네요. 접두어 코드(.. [알고리즘] 탐욕(Greedy) 알고리즘 - 코딩밥상 탐욕(Greedy) 알고리즘이란? 탐욕 알고리즘 또한 전에 봐왔던 알고리즘과 동일하게 최적화 문제의 답을 얻기 위해 사용됩니다. 즉 DP 또는 Greedy 알고리즘으로 풀 수 있는 문제들이 정해져 있다는 뜻입니다. '탐욕'이라는 이름은 각 단계의 부분 문제를 풀 때 근시안적으로 최적해를 구한다고 해서 붙여졌습니다. 탐욕 알고리즘은 DP보다 효율적(대부분 연산 횟수가 DP보다 적음)이긴 하지만 DP처럼 반드시 최적해를 구해준다는 보장은 하지 못합니다. 최적해가 나오기를 기대할 수 밖에 없는것이죠. 탐욕 알고리즘이 DP와 다른 점만 있는 것은 아닙니다. 탐욕 알고리즘으로 풀 수 있는 문제는 동적 계획법과 같이 대상 문제가 최적 부분 구조를 갖고 있어야 합니다. 탐욕(Greedy) 알고리즘은 다음과 같은 과정.. 이전 1 다음
