알고리즘(アルゴリズム）/알고리즘 이모저모(アルゴリズムの緒論)
Decision Problem
JIN_YOUNG _KIM
2023. 3. 9. 11:06
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
위 문제에서 처음으로 결정 문제(Decision Problem)에 대해 접하게 되었다.
결정 문제의 정의는 다음과 같다.
계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다.
예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다.
답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다.
일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합(무한히 존재하는 해에 대해서는 결정 문제로 환원시킬 수 가
없다)의 유한한 부분집합이기 때문에,
대부분의 문제는 결정 문제로 환원될 수 있다.
최적화 문제의 구현이 어렵거나 해법이 떠오르지 않을 때는, Decision Problem으로 환원해서 생각을 해 보자!!
(시간 복잡도도 O(logN)으로 매우 빠르다)