계산 복잡도 이론3 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. 이전 1 다음
