0/1 배낭3 Branch and Bound Method (분기 한정법) 이번에 알아볼 알고리즘 기법은 분기 한정법(Branch and Bound Method)이다. 이 글에서는 최적화 문제를 해결하기 위한 분기 한정 방법, 비슷한 기법인 역추적 기법과의 차이점을 알아볼 것이다. 그리고 어떤 문제가 분기 한정법을 사용하기에 적절한 문제인지 식별해보고, 이전 부터 계속 해왔던 0/1 배낭 문제를 해당 기법을 이용하여 해결해 볼 것이다. Introduction to Branch and Bound 역추적 알고리즘과 마찬가지로 분기 한정 알고리즘도 상태 공간을 사용하여 조합 문제를 해결한다. 그러나 분기 한정법은 방문할 다음 노드가 런타임 중에 결정되고 입력 인스턴스마다 다르기 때문에 트리 탐색 순서를 미리 결정하지 않는다. 또한 역추적 알고리즘은 최적화/비최적화 문제를 모두 해결할.. 2021. 11. 30. Backtracking Algorithm Design Method (백트래킹 알고리즘) 이번에는 백트래킹 알고리즘에 대해 알아보자. 이 글에서 알아볼 것은 다음과 같다. 백트래킹 기술 설명 백트래킹 기법이 문제 해결에 적절한 접근 방식인지 판단 주어진 문제에 대한 상태 공간 트리 정의 주어진 문제에 대한 상태 공간 트리의 노드가 유망(promising)하거나 비유망(non-promising)한 경우 정의 상태 공간 트리를 제거하는 알고리즘 생성 주어진 문제를 해결하기 위해 백트래킹 기법을 적용하는 알고리즘 생성 여기서 상태 공간 트리(state-space-tree)란 문제 해결의 중간 상태를 각각 한 노드로 나타낸 트리이다. ※ P, NP Problem 백트래킹을 살펴보기 전에 P, NP에 대해 간단히 짚고 넘어가자. 이제 막 알고리즘에 대해 배우고 있는 입장에서 명확히 이해하기 어려운 개.. 2021. 11. 22. Greedy Algorithm Design Pattern 2(탐욕 알고리즘) 이전 게시글에 이어서 Greedy Algorithm(탐욕 알고리즘, GA)의 또 하나의 예시인 허프만 이진 코드 트리(Huffman Binary Code Tree)에 대해 알아보자. 그리고 헷갈릴 수 있는 Dynamic programming(DP)과 GA의 차이점에 대해서도 살펴보자. Huffman Binary Code Tree 해당 알고리즘은 데이터 파일(텍스트, 오디오, 이미지 등)을 효율적으로 인코딩할 때 사용된다. 즉 최대한 압축률을 크게 하는 것이 목적이다. 우선 파일을 어떤 방식으로 나타내는지 부터 알아야겠다. 파일을 나타내는 일반적인 방법은 이진 코드(bit)를 사용하는 것이며 문자는 고유한 코드 워드(이진 문자열)로 표시된다. Type of Binary Code 여기서 이진 코드의 유형을 .. 2021. 11. 8. 이전 1 다음
