전체 글51 파라메트릭 서치 파라메트릭 서치(parametric search) 파라메트릭 서치란 최적화 문제를 결정 문제로 바꿔 이분 탐색을 이용해 해결하는 방법이다. 여기서 결정 문제란 예 혹은 아니오 형태의 답이 나오는 문제를 말한다. 예를 들어 외판원 문제를 최적화 문제와 결정 문제로 표현하면 아래와 같다. optimize(G) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 최단 경로의 길이를 반환한다. decision(G, \(x\)) = 그래프 G의 모든 정점을 한 번씩 방문하고 시작점으로 돌아오는 길이가 \(x\)이상인 경로가 있는 있는가? 최적화 문제의 답은 보통 실수, 정수이므로 답의 경우의 수가 무한개이지만, 결정 문제의 답은 예 혹은 아니오 이므로 답의 경우의 수가 2개이다. 왜 결정문제로 바꿔.. 2022. 6. 8. 배낭 문제 배낭 문제(Knapsack Problem)는 유명한 동적 계획법 문제 중 하나이다. 배낭 문제가 어떻게 응용되는지 정리해보자. 배낭 문제란? 일정한 가치와 무게를 가진 짐을 담을 수 있는 최대 무게가 정해진 배낭에 담을 때, 가치의 합이 최대가 되도록 배낭에 짐을 넣는 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다. 완전 탐색 짐의 개수가 \(N\)개 일 때 가능한 부분집합의 개수는 \(2^N\) 개이다. 따라서 시간 복잡도는 \(O(2^N)\)이다. → 너무 느리다. 동적 계획법 $$ D[i, w] = \text{배낭의 무게 한도가 }w \te.. 2022. 6. 6. 그래프에서 사이클 찾기 사이클(Cycle) 이란 그래프에서 사이클은 한 정점에서 시작하여 어떤 경로를 지나 다시 그 정점으로 돌아오는 경로를 말한다. 유향, 무향 그래프에서 사이클을 찾는 방법을 알아보자. 유향 그래프에서 사이클 찾기 유향 그래프에서 사이클은 DFS를 사용해 찾을 수 있다. DFS 수행 중 역행 간선이 있다면 그래프 내 사이클이 있다고 판별할 수 있다. #include using namespace std; int visited[10]; vector adj[10]; bool dfs(int here) { visited[here] = 1; for(int& there : adj[here]) { if(visited[there]) return true; if(dfs(there)) return true; } return f.. 2022. 6. 6. 이전 1 ··· 4 5 6 7 다음