www.acmicpc.net/problem/1602 1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 멍멍이가 괴롭힐 수 있는 시간이 작은 순으로 정렬하고 그 순서로 플로이드 알고리즘을 이용해 문제를 해결했다. 코드 #include #include #include #include #include #include #include #include #include using namespace std; int n, m, q; vector dog2; vector dog1..

www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아 www.acmicpc.net 그래프를 만들고 벨만 포드 알고리즘을 이용해 문제를 해결했다. 벨만 포드 알고리즘에서 here이 묘비인 경우와, here로 아직 오는 방법이 없을 때를 고려한다. 코드 #include #include #include #include using namespace std; int w, h; int g; int e; vector adj[30][30]; //걸리는 시간과 위치 int dxdy[4][2] = { {0,-1},..

www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 두 노드가 같은 높이일 때까지 올리고, 같은 높이일 때 같은 노드라면 그것이 공통조상이고, 다른 노드라면 두 노드를 모두 위로 올려 다시 같은 노드인지 확인하는 것을 반복한다. 코드 #include #include #include using namespace std; int n; int m; vector adj[50001]; vector height(50001, 0); vector parent(50001,..

www.acmicpc.net/problem/12849 12849번: 본대 산책 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다. www.acmicpc.net 그래프를 만들고, 현재 위치와 지난 시간을 고려하여 long long cache[8][100001]를 사용해 중복계산을 하지 않는다. 코드 #include #include #include using namespace std; int d; vector adj[8]; //정보과학관, 전산관, 신양관, 진리관, 학생회관, 형남공학관, 한경직기념관, 미래관 순서(0~7) long long cache[8][100001]; //그래프를 만들고 cache를 초기화한다 void Pre() { for (int i = 0; i < 8; i++)..

www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 O(n log n) 알고리즘 사용하여 문제를 해결했다. 코드 #include #include #include #include #include #include #include #include #include using namespace std; int n; vector input_data; vector here_finish_long(1000000); //..

www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 유니온 파인드를 이용하여 문제를 해결했다. 코드 #include #include #include using namespace std; int g, p; vector parent(100001); void Pre() { for (int i = 0; i < 100001; i++) { parent[i] = i; } } //유니온 파인드의 파인드 int Find(int u) { if (..