728x90 알고리즘/NP-hard1 Subset sum problem 개요 NP-complete 집합 내 원소의 합으로 S를 구성하는 방법의 수 구하기 P, NP문제는 너무 어려워서 이해하는 데에도 시간이 꽤 오래걸렸다. 막 작성해보는 중인데 NP-hard, NP-complete나 "deterministic"에 대한 이해가 어려워서 일단 SSP부터 정리하고 가려고 한다. 접근 SSP는 NP-complete 문제이다. 다항 시간 내에 검증이 가능하고, 다항시간 내에 해결이 불가능하다. SSP의 해결방법은 크게 세 가지를 소개하려 하는데, Bruteforce, Meet in the middle, Knapsack이다. Bruteforce Meet in the middle Knapsack $O(2^n)$ $O(2\times 2^{n\over 2})$ $O(nS)$ 1. Brute.. 2023. 3. 31. 다음 728x90