분류 전체보기2 결정 문제 (Decision Problem) 우선 계산 문제는 정말 다양하지만, 대표적으로 결정 문제, 탐색 문제, 최적화 문제가 있다. 결정 문제 (Decision)길이가 10 이하인 경로가 존재하는가?Boolean탐색 문제 (Search)길이가 10 이하인 경로를 찾아라.List최적화 문제 (Optimization)가장 짧은 경로를 찾아라.List 옛날의 연구자들은 이러한 계산 문제들이 얼마나 어려운지를 알고 싶어 했다(물론 지금도 그러하다). 하지만, 앞서 얘기한 문제들은 입력과 출력이 모두 제각각이라서 이를 분석하는 게 어려웠다. 이때 나온 해결 방법이 모든 문제들을 대응되는 결정 문제로 치환하는 것이다. 예를 들면, 탐색 문제는 원래 "길이가 10 이하인 경로를 찾아라."는 문제이고 답은 실제 길이가 10 이하인 경로 List를 반환한다.. 2026. 11. 12. P와 NP 문제 P와 NP문제는 컴퓨터과학을 전공한 학생이라면 누구나 들어봤을 것이라 생각됩니다. 그만큼 유명하고, 계산 이론의 근간이 되는 내용이기 때문이죠. 실제로, P와 NP문제는 밀레니엄 7대 난제에 속하는 문제로 컴퓨터과학뿐만 아니라 수학자들까지도 관심이 큰 문제가 아닐까 싶습니다.P와 NP는 결국 복잡도(Complexity)이론에서 나온 용어인데, 이를 명확히 이해하기 위해서는 먼저 짚고 넘어가야 할 것이 있습니다. 바로 "빠르다"라는 것은 무엇가를 생각해봐야 합니다. 알고리즘이 1초만에 실행된다면 빠른걸까요? 1초면 빠르다고 생각할 수 있지만 만약 데이터 하나만을 처리하는데 1초가 걸렸다면? 또한, 데이터 백만개를 알고리즘 2초만에 실행했다면? 이는 앞서 말한 알고리즘보다 느린걸까요? 여기서 무언가 이상한 .. 2026. 11. 12. 이전 1 다음
