All about Programming Theories/NP problems (1) 썸네일형 리스트형 결정 문제(Decision Problem)와 결정적 알고리즘(Deterministic Algorithm) 그리고 최적화 문제 ※ 이 글은 chatGPT를 기반으로 작성한 글입니다. 결정 문제와 비결정 문제 ① 결정 문제(Decision Problem)는 주어진 문제에 대해 '예' 또는 '아니오'로 답할 수 있는 문제를 의미한다. ② 결정 문제에 대한 예시는 다음과 같다. ㉠ 소수 결정 문제(Prime Decision Problem) ⓐ 질문: n=7은 소수인가? ⓑ 답: yes ㉡ 그래프 연결성 결정 문제(Graph Connectivity Decision Problem) ⓐ 질문: 주어진 그래프가 연결되어 있는가? ⓑ 답: yes or no ㉢ 해밀턴 경로 문제(Hamiltonian Path Problem) ⓐ 질문: 주어진 그래프 내에서 모든 정점을 정확히 한 번씩 방문하는 경로가 존재하는가? ⓑ 답: yes or no ㉣ .. 이전 1 다음