알고리즘 이론32 허프만 코드(Huffman code) 허프만 코드는 데이터를 효율적으로 압축하는데 사용하는 방법으로 탐욕 알고리즘 중 하나입니다. 압축하고자 하는 문자열에서 자주 등장하는 문자는 짧은 비트로 표현하고 거의 등장하지 않는 문자는 긴 비트로 표현합니다. (가변 길이 코드) 즉, 문자의 빈도수를 이용합니다. 예시를 들어 설명하겠습니다. EX) 압축하고자 하는 문자열 : ABBCCCDDDDEEEEEFFFFFF -> 고정 길이 코드 : A ~F. 6개의 문자를 구분하기 위해 3bit 필요. (2^2(4) 가변 길이 코드 : 허프만 코드를 이용해서 나온 값. [표 1] 고정 길이 코드 : 00000100101001001001101101101110010010010010010110110110110.. 2018. 10. 29. 깊이 우선 탐색(DFS: Depth First Search) 트리나 그래프를 탐색하는 방법엔 여러가지가 있습니다. 그 중 가장 보편적인 방법이 깊이 우선 탐색과 너비 우선 탐색입니다.이번에는 두 가지 탐색 방법 중 깊이 우선 탐색에 대해 알아보겠습니다. 깊이 우선 탐색에 대해 말해보자면 말 그대로 깊숙이 탐색하는 방법입니다. 예를 들어서 살펴보겠습니다. [예시 그래프]깊이 우선 탐색 알고리즘은 간단하게, 1. 노드와 연결된 탐색하지 않은 이웃 노드 중 하나를 탐색한다. 2. 탐색하지 않은 이웃 노드가 없는 경우 이전 노드로 돌아간다. 3. 1번으로 돌아간다. 입니다. 이를 모든 노드가 탐색될 때까지 실행합니다. 위의 그래프를 1번 노드 부터 깊이 우선 탐색(DFS)으로 탐색해 보겠습니다. 일단 1번 노드가 시작 노드이므로 1번 노드를 탐색합니다. 그리고 1번 노드.. 2018. 10. 27. 이전 1 ··· 3 4 5 6 다음
