물체를 쪼개서 넣을 수 있는 배낭 문제의 경우 단위 무게당 이득이 가장 큰 것으로부터 택하여 집어넣으면 된다. 이 문제에 적용하기에 가장 좋은
알고리즘 설계 기법
은?
1) 분할 정복 방법
2) 욕심쟁이 방법
3) 동적 프로그래밍 방법
4) 분지 한계법
비결정론적(nondeterministic)
알고리즘의 성질에 속하는 것은?
1) 어떠한 문제이든 다항식 시간에 풀 수 있다.
2) 답을 반드시 구한다고 보장할 수 없다.
3) 해를 확률적으로 구하는 알고리즘이다.
4) 여러 가지 선택안 중 최적의 선택안을 스스로 택할 수 있는 능력이 있다.
NP 완전 문제
에 속하지 않는 것은?
1) 최단 경로 문제
2) 0/1 배낭 문제
3) CNF 만족성 문제
4) 해밀토니언 사이클 문제
“문제 B에 대한 알고리즘으로 문제 A를 풀 수 있을 때, 문제 A를 문제 B로
할 수 있다고 하며, 이러한
에 다항식 시간이 소요되면 다항식시간
이라 한다.” 밑줄 친 부분에 들어갈 적절한
용어
는?
1) 분할
2) 대체
3) 변환
4) 해석
어떤 NP-완전 문제 A를 문제 B로 다항식 시간 변환할 수 있다면 문제 B는 다음 중 어떠한
문제
인가? 단, 문제 B에 대한 비결정론적 다항식 시간 알고리즘은 구하지 못했다고 가정한다.
1) P-완전 문제
2) NP-완전 문제
3) NP-문제
4) NP-하드 문제
