📕Huffman code 란?압축은 자료의 크기를 줄이기 위해서 사용된다. 그리고 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 알고리즘이다. Huffman code도 그리디 알고리즘의 일종이다. 허프만코드는 데이터를 매우 효율적으로 압축하는데, 20~90%의 용량을 아낄 수 있다. 허프만 코드는 prefix-free* codes로 표현된다. prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장한다. (*prefix codes가 표준 표기이긴 하지만, prefix-free codes가 좀 더 맞는 이름이기 때문에 여기에서는 prefix-free codes로 표기하겠다) ..

📕그리디 알고리즘이란 ? 그리디 알고리즘은 코딩테스트에 자주 나오는 단골 문제이면서, 알고리즘 문제에 널리 사용되는 알고리즘이다. 그리디 알고리즘은 무엇일까? 그리디 알고리즘의 정의는 다음과 같이 말할 수 있다. "A greedy algorithm always makes the choice that looks best at the moment" 그리디 알고리즘은 '지금 당장 좋은 것을 고르는 방법'이다. 즉, 선택의 순간이 왔을 그때, 가장 좋은 것을 선택하는 것이다. ('Greedy'라는 이름을 보더라도 탐욕적인 것을 알 수 있다.) 📕 Greedy algorithm vs Dynamic programming 그리디 알고리즘과 다이나믹 프로그래밍을 언뜻 보면 비슷하다고 생각할 수 있다. 절차적으로 해결법..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 자료구조, 알고리즘 포스팅 📕Findings(배운 것) 그리디 알고리즘, huffman code, backtracking에 관해 블로그에 포스팅을 하면서 새로운 사실 몇가지를 알게 되었다. huffman code에서 트리를 구성할때 값을 Queue에서 꺼내서 트리를 구성하는데 그때의 queue는 min_heap 구조의 우선순위 큐이다. dp와 그리디의 구분은 bottom-up 과 top-down 방식으로 구분하는 것이 아니라 subproblem에 의존성이 있냐 없냐로 구분한다. 📕Feeling(느낀 점) 알고리즘 포스팅은 생각한 것 보다 시간이 많이 걸렸다. 공부를 다시 함과 동시에 정보전달을 위해서 내 생각을 글로 표현해야 ..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) huffman code관련해서 복습을 진행했다. 복습을 하던 도중 heap관련 내용이 나왔는데, 공부도 너무 지겨워서 프로그래머스 heap관련 문제를 풀었다. '더 맵게' 라는 문제인데, 우선순위큐를 이용해서 풀 수 있다. 우선순위 큐에 대해서 간략히 얘기하자면, 우선순위 큐는 힙의 성질과 큐의 성질을 합쳐놓았다고 보면 된다. 힙에는 max heap과 min heap 두 종류가 있다. max heap은 트리 가장 상단의 노드가 즉, 루트노드가 그 트리에서 가장 큰 값이고 부모 노드의 자식 노드는 부모 노드보다 작아야 한다. min heap은 정반대이다. 가장 산단의 노드가 그 트리에서 가장 작은 값..

📕Facts(한 것) 알고리즘 복습 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) 그리디 알고리즘을 복습하면서 어제 풀다만 프로그래머스 문제가 생각나서 다시 시도해봤다. 큰 수 만들기라는 문제인데, 첫번째 시도는 문자열을 오름차순으로 정렬한 후 인덱스 0부터 k까지 큐에 저장한 후 원래 문자열에서 빼는 방식이었다. 이런 방식은 테스트 케이스 1, 2번은 통과하지만 3번 케이스는 통과하지 못하는데, 작은 수를 빼내어도 가장 큰 수가 되지 못했기 때문이었다. 두번째 시도는 C++ string 라이브러리 메서드인 str.erase()를 활용한 풀이방법이었다. 문자열 인덱스 i와 i+1을 비교한 후, i가 더 작다면 i를 erase()함수를 통해서 지우는 방식이다. 이러한 방식은 테스트..

📕Facts(한 것) 알고리즘 복습(DP, Floyd) 프로그래머스 문제 풀기 수업듣기 학교 과제 📕Findings(배운 것) knapsack problem(배낭문제) 을 다이나믹 프로그래밍을 통해 구현했다. 보통 knapsack problem은 그리디 알고리즘을 통해 나오는 문제들이 많지만 큰 무게가 작은 무게의 배수가 아니거나, 그 수량이 1개로 한정되어 있을때는 그리디 알고리즘 적용이 불가능하다. 그렇기 때문에 recursion + memoization 방식인 DP로 푸는게 적합하다. 이 문제를 DP로 풀 경우, 시간복잡도는 O(N*W) (w는 weight)이다. Floyd 알고리즘의 기본적인 개념을 이러하다 "If V(k)is a node on an optimal path from Vi to Vj..