티스토리

Bloofer Blog
검색하기

블로그 홈

Bloofer Blog

bloofer.tistory.com/m

Bloofer 님의 블로그입니다.

구독자
0
방명록 방문하기

주요 글 목록

  • NP 문제에 대한 쉬운 설명 P 문제 Polynominal complexity의 알고리즘을 가지고 있는 쉬운 문제. 즉, 다항 시간내에 풀리는 문제. NP 클래스 Non-deterministic Polynominal complexity를 가지는 문제들. 운에 기대면 현실적인 비용으로 해결할 수 있는 문제들. 예를 들자면 주어진 지도 위의 도시(그래프)를 한 번씩만 방문하는 경로 찾기 문제인 해밀턴 경로(Hamilton path) 문제가 대표적이다. 이를 다항시간 내에 푸는 알고리즘은 아직 없다. 건너풀기(Problem Reduction) 문제 A를 푼 알고리즘으로 동일하게 B 문제를 해결할 수 있다면, 그 문제는 간접적으로 풀 수 있는 것이다. 단, A 문제로 푼 답을 B 문제의 답으로 옮기는 건 다항 시간내에 되야한다. NP 완전.. 공감수 0 댓글수 0 2019. 7. 22.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.