SW역량강화3 [허프만 코드] Huffman Code의 이해 및 구현 "허프만 코드" 문자 빈도 수를 이용해 통계적으로 압축하는 알고리즘 이론 허프만 코드는 압축 알고리즘 중 하나로, 입력 데이터를 더 적은 용량으로 만드는 것입니다. 허프만 코드의 요점은 자주 나오는 문자에는 짧은 비트를, 조금 나오는 문자에는 긴 비트를 할당하는 것입니다. 예를 들어 AABBAC라는 문자열을 살펴보면, 각 문자의 빈도수는 아래와 같습니다. A : 3번 B : 2번 C : 1번 이에 따라, 가장 자주 나오는 문자 A에는 0, B는 10, C는 11을 부여하면 001010011로 나타내어집니다. 원래의 문자열 AABBAC는 6글자 이므로 48 bit가 사용되지만, 압축된 코드 001010011은 9bit만 사용되어 표현할 수 있습니다. 1. 주.. 2020. 12. 19. [문자열 문제] 가장 긴 '반복 부분 문자열' 길이 구하기 참고 문제 출처 www.acmicpc.net/problem/1605 1605번: 반복 부분문자열 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분문자열을 '반복 부분문자열' www.acmicpc.net 문제 알파벳 소문자로 이루어진 길이 L인 문자열이 있다. 이 문자열의 부분 문자열 중, 적어도 한 번은 반복되는 (다시 말해서, 전체 문자열에서 두 번 이상 나타나는) 부분 문자열을 '반복 부분 문자열'이라고 부르자. 문자열이 주어지면, 가장 긴 '반복 부분 문자열'의 길이를 구하는 프로그램을 작성하시오. 입력 (+테스트 케이스 추가, -문자열의 길이 제공X) 첫째 줄에 테스트 케이스의 수 .. 2020. 12. 17. [파라메트릭 서치] Parametric Search의 이해 및 구현 "파라메트릭 서치" 최적화 문제를 결정 문제로 바꾸어 푸는 것 이론 파라메트릭 서치 (Parametric search)는 이분 탐색(binary search)의 일종으로 선형 탐색에 비해 효율적인 시간 복잡도를 가집니다. 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정문제 로 바꾸어 푸는 것이라고도 할 수 있습니다. 어떤 명제 에 대해 True와 False의 경곗값 v0를 찾아야 할 경우 파라메트릭 서치를 이용하게 됩니다. 중간 위치는 (0+8)/2 =4 이므로, p(4)를 확인해보니 True -> 4는 v0의 후보군이 되고, 5~8은 탈락. 다음 중간 위치는 (0+3)/2 =1 이므로,p(1)을 확인해보니 False -> 0~1은 탈락. 다음 중간 위치는 (2+3.. 2020. 12. 16. 이전 1 다음
