소파와 바보개의 블로그

정규 허프만 코딩 (Canonical Huffman Coding)?허프만 코딩은 그리디 알고리즘을 이용해 자주 이용되는 문자는 짧은 코드를 가지고, 덜 이용되는 문자는 긴 코드를 가지는 효율적인 압축 알고리즘입니다. 2025.02.21 - [Competitive Programming] - 11. 허프만 코딩 (Huffman Coding, c++) - Greedy Algorithms 11. 허프만 코딩 (Huffman Coding, c++) - Greedy, Compression허프만 코딩 (Huffman Coding)?Huffman Coding은 무손실 데이터 압축 알고리즘으로, 주어진 string을 압축하기 위한 최적의 codeword를 그리디 알고리즘을 이용해서 만들어 냅니다. 자주 사용되는 문자가 ..

허프만 코딩 (Huffman Coding)?Huffman Coding은 무손실 데이터 압축 알고리즘으로, 주어진 string을 압축하기 위한 최적의 codeword를 그리디 알고리즘을 이용해서 만들어 냅니다. 자주 사용되는 문자가 더 짧은 codeword를 갖도록 구현됩니다. 이렇게 생성된 binary codeword는 다음 특징을 갖습니다. 1) 문자에 대한 binary codeword는 다른 문자의 prefix가 될 수 없습니다. 이를 통해 구분자(seperator)없이도 encoding, decoding을 수행할 수 있습니다. 2) 주어진 string에서의 문자 등장빈도 기반으로 구성하기 때문에 encoding 문자열의 길이가 최적화 됩니다. 자주 등장하는 문자가 짧은 codeword를 갖습니다.I..

[백준/BOJ] 1931 회의실 배정 (c++)https://www.acmicpc.net/problem/19312025.02.21 - [Competitive Programming] - 10. 그리디 알고리즘 (Greedy Algorithms, c++) 10. 그리디 알고리즘 (Greedy Algorithms, c++)그리디 알고리즘 (Greedy Algorithms)?그리디 알고리즘은 항상 그 순간에 할 수 있는 최고의 선택을 하면서 문제를 해결하는 방식입니다. 선택을 되돌리는 것은 없고 최고의 선택만을 하면서 바로 결dnsldprp.tistory.com 그리디 알고리즘으로 해결할 수 있는 스케쥴링 문제입니다. 회의의 시작시간과 종료시간이 주어졌을때 참석할 수 있는 회의의 최대 갯수를 출력하는 문제입니다..

그리디 알고리즘 (Greedy Algorithms)?그리디 알고리즘은 항상 그 순간에 할 수 있는 최고의 선택을 하면서 문제를 해결하는 방식입니다. 선택을 되돌리는 것은 없고 최고의 선택만을 하면서 바로 결과를 도출합니다. 그러므로 매우 효과적이기는 합니다. 그러나 항상 모든 문제에 대한 최적의 답을 구해주지는 않습니다. 동전 문제(Coin Problem)그리디 알고리즘을 적용할 수 있는 예시로는 동전의 단위가 주어졌을 때, K원을 만들기 위한 최소 동전 갯수를 찾는 문제가 있습니다. 예를 들어 {1, 5, 10, 20, 50, 100, 200} 단위의 동전을 가지고 540원을 만드는 최소 동전 갯수를 찾는 문제입니다. 이 경우 가능한 큰 동전부터 금액이 모두 차감될 때까지 다 사용해보는 greedy한 ..