studlog

그래프에서 최단거리는 경우에 따라 BFS, 다익스트라, 벨만 포드, 플로이드 와샬을 사용하여 구할 수 있다. 그렇다면 최장거리는 어떻게 구할 수 있을까?사이클이 없는 무향 그래프(트리)에서 최장거리트리에서는 어떤 두 노드를 선택해도 둘 사이의 경로가 항상 하나만 존재한다. 따라서 BFS을 이용하여 구할 수 있다.사이클이 없는 유향 그래프에서 최장거리일반적인 그래프에서 최장거리를 구하는 방법은 NP-Hard로 알려져 있다. 하지만 DAG(Directed Acyclic Graph)에서는 구할 수 있다. DAG에서 최장거리를 구할 수 있는 2가지 방법을 정리해보자.동적 계획법정점 $u$ → $v$의 최장거리를 구하는 점화식을 아래와 같이 세워보자.$$ D[i] = \text{정점 } i \text{ 에서} v..

입력의 범위가 터무니 없이 크다면입력으로 범위가 [0, 1000000000]인 값이 1,000개 들어올 때 입력 값을 인덱스로 하는 배열이 필요하다면 아래와 같은 방법을 사용할 수 있을까? 아니다, 배열의 메모리만 해도 4 * 10억 byte = 4GB로 메모리가 부족하다.int index[1000000000];int main(){ for(int i = 0; i > var; index[var] = 1; }}좌표 압축 알고리즘입력 값의 범위가 10억이지만, 입력의 개수는 1,000개 이므로 배열에 쓸모없는 공간이 너무 많다. 예를 들어 공차가 100인 값이 1,000개 들어온다고 해도 각 입력 값 사이의 빈 공간이 99개나 있는 격이다. 배열 사이의 빈 공간을 줄여서 값들에 새로운 ..

오일러 투어 테크닉(euler tour technique)오일러 투어 테크닉이란 DFS로 트리를 탐색하면서 임의 정점 \(v\)의 진입 시점과 탈출 시점을 기록하여 트리의 서브 트리를 일차원 배열로 관리하는 테크닉이다.과정1. 루트부터 DFS를 시작해 각 정점의 진입 순서를 left 배열에 기록하자. (0-base, 1-base 상관없다.)2. 탈출 순서를 right 배열에 기록하자3. 트리와 left, right 배열을 한 번에 보면, 정점 v를 루트로 하는 서브 트리에 속한 정점들의 방문, 탈출 순서가 모두 루트 정점에 진입, 탈출 순서 사이에 있다. 즉, 각 정점을 루트로 하는 서브 트리가 하나의 구간으로 나타난다.구현 방법진입 순서와 탈출 순서를 어떻게 관리할까? 전역 변수를 이용하여 관리할 수 ..

배낭 문제(Knapsack Problem)는 유명한 동적 계획법 문제 중 하나이다. 배낭 문제가 어떻게 응용되는지 정리해보자.배낭 문제란?일정한 가치와 무게를 가진 짐을 담을 수 있는 최대 무게가 정해진 배낭에 담을 때, 가치의 합이 최대가 되도록 배낭에 짐을 넣는 문제이다.배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는 경우로 나눌 수 있는데 짐을 쪼갤 수 있는 경우 그리디 알고리즘으로 해결 가능하며, 짐을 쪼갤 수 없는 경우 동적계획법으로 해결 가능하다.완전 탐색짐의 개수가 \(N\)개 일 때 가능한 부분집합의 개수는 \(2^N\) 개이다. 따라서 시간 복잡도는 \(O(2^N)\)이다. → 너무 느리다.동적 계획법$$ D[i, w] = \text{배낭의 무게 한도가 }w \text{이고 }..

사이클(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..