알고리즘/수업 복습11 An Introduction to Theory of NP and Intractability 탐욕 알고리즘, 역추적 알고리즘, 분기 한정법을 다뤄오면서 공통적으로 나왔던 0-1 배낭 문제를 기억하는지 모르겠다. 역추적 알고리즘 글에서 이 문제가 NP 문제라고 했다. 본인도 이해하기 굉장히 어려운 개념이었는데(아직도 제대로 이해한 것 같지는 않다 ㅠㅠ😥) 이번 글에서는 이 NP 문제에 대해 다뤄볼 것이다. 이번 글에서 알아볼 사항들은 다음과 같다. tractable/intractable(다루기 쉬운/다루기 어려운) 문제 분류 결정 문제 정의 class P 정의 비결정적 문제 정의 class NP 정의 다항식 변환 정의 NP-Complete class 정의 Polynomial Time Algorithm? 우선 다항 시간 알고리즘에 대해 이해해보자. 이는 worst-case 시간 복잡도가 입력 크기 .. 2021. 12. 22. More Computational Complexity theory of a problem :The searching Algorithm 저번 게시글에서는 계산 복잡도 이론에 대해 간단히 알아보고 이에 대한 개념을 일부 정렬 문제에 적용해보았다. 이번에는 탐색 문제에 계산 복잡도 이론을 적용해보자. 다음과 같은 사항들을 이번에는 알아볼 것이다. 키 비교를 이용하는 배열 탐색에 대한 하한 선택 문제: Adversary Arguments 소개 K번째 가장 작은 키 찾기 선택 문제에 대한 확률적 알고리즘 The Searching Problem 탐색 문제는 일부 키 필드의 값을 기준으로 전체 레코드를 검색하는 것을 말한다. 예를 들어보자. 레코드는 개인 정보로 구성되고 키 필드는 주민등록번호라고 할 수 있다. 그렇다면 우리는 해당 키 필드를 이용하여 레코드를 탐색할 수 있는 것이다. 이전에 다뤄본 정렬 문제와 마찬가지로 탐색 문제에서도 하한을 계.. 2021. 12. 21. Introduction to Computational Complexity theory of a Problem: The sorting Algorithm Problem 이전까지는 주어진 문제를 해결하는 알고리즘 분석에 중점을 뒀었다. 즉 문제 자체의 속성보다는 특정 알고리즘의 속성에 초점을 맟췄었다. 예를 들어 순차 탐색 알고리즘의 시간 복잡도를 분석할 때 시간 복잡도는 \(\theta(n)\)이다. 이것은 당연히 탐색 문제에 \(\theta(n)\) 알고리즘이 필요하다는 의미가 아니다. \(T(n)=n\) 함수는 탐색 문제의 속성이 아닌 문제에 대한 탐색 알고리즘의 속성이다. 이 장에서는 계산 복잡도 이론(computational complexity theory)이라는 이론적인 컴퓨터 과학 분야에 대해 알아볼 것이다. 알고리즘 분석에서는 문제를 해결하기 위해 특정 알고리즘이 필요로 하는 리소스 양을 분석하는데 전념했지만 계산 복잡성 이론은 동일한 문제를 해결하는데 사.. 2021. 12. 13. Branch and Bound Method (분기 한정법) 이번에 알아볼 알고리즘 기법은 분기 한정법(Branch and Bound Method)이다. 이 글에서는 최적화 문제를 해결하기 위한 분기 한정 방법, 비슷한 기법인 역추적 기법과의 차이점을 알아볼 것이다. 그리고 어떤 문제가 분기 한정법을 사용하기에 적절한 문제인지 식별해보고, 이전 부터 계속 해왔던 0/1 배낭 문제를 해당 기법을 이용하여 해결해 볼 것이다. Introduction to Branch and Bound 역추적 알고리즘과 마찬가지로 분기 한정 알고리즘도 상태 공간을 사용하여 조합 문제를 해결한다. 그러나 분기 한정법은 방문할 다음 노드가 런타임 중에 결정되고 입력 인스턴스마다 다르기 때문에 트리 탐색 순서를 미리 결정하지 않는다. 또한 역추적 알고리즘은 최적화/비최적화 문제를 모두 해결할.. 2021. 11. 30. 이전 1 2 3 다음
