허프만 코드 소개허프만 코드는 greedy 접근 방식을 기반으로 한 데이터 압축 방식이다.그러면 어떻게 데이터를 압축하는지 방법을 알아보자. 우선 임의의 문자열을 각각의 문자로 구분해둔다.그리고 각 문자의 빈도와 그 문자를 이진수로 구분하기 위한 binary character code를 표시한다. 여기에서 fixed length라는 뜻은 6개의 문자를 나타내기 위해선 항상 3개의 고정된 비트가 필요하다는 의미이다. 위와 같이 설정한 경우, 필요한 메모리 공간은 ( 45,000 + 13,000 +12,000+16,000+9,000+5,000) ∗ 3 으로, 30만 비트가 필요하다. 이와 같은 방법을 개선하기 위해서 우리는빈도가 높은 문자에는 크기가 작은 이진수를, 빈도가 낮은 문자에는 크기가 ..
이전에 배운 최적화 문제에 대한 Dynamic-programming의 접근 방식은하위 문제를 해결하고 다음 문제를 마주하는 것으로, 하위 문제보다 더 작은 하위 문제에 대한 최선의 선택을 했다. 이렇게 모든 subproblem에 대한 문제가 해결된 후 main problem에 대한 접근이 이루어졌다.그렇다면 문제를 최적화하기 위한 다른 방법인 greedy란 어떤 방법일까 Greedy Algorithm 소개 지금 당장에 가장 좋아보이는 선택을 하는 알고리즘인 dp는 너무 과한 면이 있다. 각각의 subproblem 먼저 해결하여 local적으로 최적의 선택을 하는 것은 항상 최상의 결과만 얻는 것이 아니다.이를 보완하기 위해서 그리디 알고리즘이 나왔는데, 그리디 알고리즘은 subproblem이 해결되기..
Longest Common Subsequence 소개(가장 긴 공통 부분 수열) LCS는 수열 X와 Y가 주어졌을 때, 이 두 개의 수열에서 순서가 서로 같은 부분을 찾는 문제이다.예를들어 수열 X가 일때 Y 에서 LCS는 ABCBDAB 이다. 이런 문제는 DNA같은 생물학적 분야에 응용하여 적용될 수 있다.예를들어 DNA 분자 구성이 주어지고X = ACCGGTCGAGTGCGCGGAAGCCGGCCGAAY = GTCGTTCGGAATGCCGTTGCTCTGTAAA일때 X와 Y 중 DNA와 더 비슷한 수열을 찾는 경우가 있다. LCS 문제를 간단하게 생각해보자면 brute-force가 먼저 떠오른다.그냥 X의 모든 순열들을 열거하고, 이게 순열 Y에도 있는지 없는지 일일이 확인해서그 중 가장 긴 순열을 찾는 ..
https://guhonga.tistory.com/116 Dynamic Programming (Fibonacci, Rod-Cutting Problem)동적 프로그래밍이란, 복잡한 문제를 더 작은 하위 문제 단위로 나눠서 해결하는 알고리즘 설계를 말한다.이렇게 보면 DP랑 분할 정복 divide and conquer랑 다를것이 없어 보이는데분할 정복의 sub proguhonga.tistory.comRod-Cutting 이전에 Rod-Cutting 문제에 대해 다뤄봤었다.여기서 구한 Rod-Cutting 에 대한 bottom up 알고리즘은 최적의 값만 계산해줄 뿐이지, 밧줄의 어떤 부분을 잘라야 할지는 알려주지 않았다. 그래서 이번에는 maximum revenue 값, r[j] 뿐만 아니라처음 자를 때의 ..
동적 프로그래밍이란, 복잡한 문제를 더 작은 하위 문제 단위로 나눠서 해결하는 알고리즘 설계를 말한다.이렇게 보면 DP랑 분할 정복 divide and conquer랑 다를것이 없어 보이는데분할 정복의 sub problem은 각각이 독립적이고,DP의 sub problem은 서로 독립이 아니다.DP는 sub problem을 한 번만 풀고, 해당 솔루션을 저장한 다음 재사용하여 중복 계산을 피한다. 해결하기 어려운 하나의 문제를 하위 문제로 나눠서 접근하는 것은 분할 정복으로 충분한데 DP를 배워야 하는 이유는최적화 문제에 적용하기 위해서 이러한 개념이 필요하기 때문이다.(물론 최적화 해법이 dp 하나만은 아니다. 여러가지 방법 중 하나) 동적 프로그램이 작동하는 방법하위 문제를 식별한다. 여기서 ..
꼬리 재귀 알고리즘을 알아보기에 앞서, 재귀 알고리즘이란 하위 문제에 대해 자신을 호출하는 알고리즘을 말한다. 일반적으로 유명한 예시인 factorial이 재귀로 많이 표현된다. 이렇게 재귀 호출 알고리즘은 스택 메모리 내에서 이루어지는데, 보다싶이 보조해주는 추가 공간이 O(n)만큼 필요하다보니 스택 메모리가 전부 차버리는 stack overflow가 발생할 위험이 있다. 그래서 이 문제를 극복하기 위해 꼬리 재귀 Tail Recursion 방법이 고안되었다.꼬리 재귀란, 함수로부터 실행되는 재귀 호출의 그 문장이 마지막 statement에 있는 알고리즘을 말한다. 함수가 한번 호출되면, 스택에는 함수의 input, return, return 후 돌아갈 포인터가 저장된다.일반적인 재귀의 경우를 보면,..