프로그래밍 잡동사니

보호되어 있는 글입니다.

보호되어 있는 글입니다.

다항식 시간에 해결하지 못하는 문제가 근사해도 구하기 힘들다면 해 탐색 알고리즘을 사용한다 1. 백트래킹 기법 (Backtracking) 해를 찾는 도중에 막히면 (= 해가 아니면) 되돌아가서 다시 해를 찾는 기법으로, 최적화(optimization) 문제와 결정(decision) 문제를 해결할 수 있다 * 최적화 문제: 문제의 조건을 만족하는 해의 최대값 or 최솟값 등을 구하는 문제 * 결정 문제: 문제의 조건을 만족하는 해의 존재 여부를 답하는 문제 여행자 문제 (Traveling Salesman Problem, TSP) 백트래킹 알고리즘 최악의 경우 2^n개의 노드를 모두 탐색해야 하는 지수 시간이 걸리며, 이는 모든 경우를 다 검사하여 해를 찾는 완결 탐색 (Exhaustive Search)의 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

근사 알고리즘 (Approximation Algorithms) NP-완전 문제들은 활용성이 높지만 다항식 시간에 해결할 수 있는 알고리즘이 아직 발견되지 않았고, 존재하지 않을 것으로 추측된다. 일단 해결하기 위해 다음 3가지 중 1가지는 포기해야 한다 다항식 시간에 해를 찾는 것 모든 입력에 대해 해를 찾는 것 최적해를 찾는 것 NP-완전 문제를 해결하기 위해 3번째 요소(최적해)를 포기, 최적해에 아주 근사한 해를 찾아주는 것이 근사 알고리즘이다 최적해가 아닌 근사해를 찾는 대신 다항식 시간의 복잡도를 가진다 근사해가 얼마나 최적해에 근사한지 나타내는 근사 비율(Approximation Ratio)을 알고리즘과 함께 제시해야 한다 근사 비율이 1.0에 가까울수록 정확도가 높은 알고리즘이다 근사 비율을..

보호되어 있는 글입니다.

P(polynomial) 문제 집합은 다항식 시간 복잡도를 가진 알고리즘으로 해결되는 문제들을 의미하며, O(logn), O(n), O(nlogn), O(n^2), O(n^3) 등 점근적 표기법으로 O(n^k)에 포함되는 시간 복잡도 내에서 해결된다 다항식보다 큰 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합 들이 있는데, 이는 여러 가지 문제 집합으로 다시 분류되며, 이 중 지수 시간 시간복잡도를 가진 알고리즘으로 해결되는 문제들을 NP-완전 문제 집합이라고 한다 * 하나의 NP-완전 문제에 대해서 다항식 시간의 알고리즘을 찾아내면, 모든 다른 NP-완전 문제도 다항식 시간에 해를 구할 수 있다 NP 문제 집합은 이러한 P 문제 집합과 NP-완전 문제 집합을 포함하는 개념으로, 비결정적 다항식 시간..

보호되어 있는 글입니다.