반응형 NP-complete1 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. 이전 1 다음 반응형
