목록P (1)

밤 늦게까지 여는 카페

P, NP, NP hard 문제란

안녕하세요. 이번에는 P, NP, NP hard 문제가 무엇인지 정리해보려고 합니다.제가 많이 공부했던 MAPF 문제가 NP hard인데 정작 NP hard 문제가 무엇인지는 모르고 있더라고요.다항 시간에 풀리지 않는 문제가 NP 문제이고, NP hard는 NP보다 어려운 문제였니...?이번 기회에 정리해보겠습니다.1. P 문제가 무엇일까요?P 문제는 결정론적 튜링머신으로 다항 시간 안에 해결할 수 있는 문제입니다.복잡도로 표현하면 입력 크기 n에 대해서 문제 해결에 걸리는 시간이 O(n^k)와 같이 다항식으로 표현되는 문제들을 의미합니다.정렬 문제, 경로 계획 문제(SAPF) 등이 있습니다.2. NP 문제는 무엇일까요?일단 다항 시간에 풀리지 않는 문제라는 정의는 틀렸습니다. NP 문제의 올바른 정의는..
For Fun/잡학 지식 2025. 7. 3. 02:27
이전 Prev 1 Next 다음