https://www.acmicpc.net/problem/14432 (머그컵 E번) 이 문제의 핵심은 문제 마지막문단에 있는 "(단, 임의의 마을 A에서 B까지 무조건 한 가지 경로가 존재한다.)" 이다. 다시말해 이 마을들간의 관계는 트리형태이고, 따라서 한점을잡아 root로 간주하여 DFS로 탐색하면서 값을 갱신해주면 정답을 도출해 낼 수 있다.

https://www.acmicpc.net/problem/14437 (머그컵 A번) DP로 접근하면 D[현재위치][남은횟수]를 가지고 풀이하면 O(N*S)에 풀 수 있을 것 처럼 보인다. 다른 방법으로는 중복조합과 포함배재의 원리를 이용해서 풀 수도 있다. 중복조합을 이용하면 속도도 빠를 뿐 아니라, combination 값을 구할 때 DP가 아닌 fermat little thm이용해서 풀면 배열을 잡을 필요가 없어진다. 즉 메모리에 구애받지 않는 풀이가 된다. 시간복잡도는 O(N+logP).

http://kks227.blog.me/220802519976 SCC구하는 알고리즘 중 Tarjan Algorithm에 대해 잘 정리해놓은 블로그 개인적으로 kosaraju Algorithm이 더 쉬운것같은데.. 이번에 문제풀다가 타잔알고리즘으로만 풀 수 있게 생긴문제가 나와서 공부하게됐다. 그 문제 : https://www.acmicpc.net/problem/13988

https://www.acmicpc.net/problem/7975 (AMPPZ 2012 B번) 어찌보면 흔한 BFS문제처럼 보일 수 있지만 "두 관광 명소 사이를 이동하는 와중에도 매력도가 100m마다 1씩 증가한다." 라는 조건때문에도착점이 동일하더라도 시작하는 위치에 따라 cost가 바뀐다는 점을 해결하는 것이 이문제의 키포인트로 보인다. 결국 이 문제는 변수가 아래 두가지인 셈이다.1. 현재위치와 다음위치 사이의 거리2. 다음위치의 매력도 이 문제를 해결하기위해 생각해 본 것이 한가지 변수를 고정시키면 어떻게 풀 수 있는가 였다.즉 2번 변수를 고정시켜 '만약 도시의 매력도가 모두 동일하다면 어떤점을 선택하는것이 유리할까' 라는 문제로 접근을 해보면, 간단하게도 현재위치에서 갈수있는 다음위치들중 가..

https://www.acmicpc.net/problem/9521 이 문제는 i에서 출발하여 f[i]로 향하는 간선을 직접 그려보면 몇가지 특징을 확인 할 수 있다. 1. 각 지점마다 하나의 간선을 출발시킨다는 점2. 상호간에 간선관계가 직/간접적으로 전혀 없는 덩어리?그래프?들로 이루어져 있다는 점3. 이 덩어리들안에는 무조건 단 하나의 루프가 있다는 점(자기자신으로 향하는 간선을 가진점도 루프로 간주) 결국 이 문제는 N개의 점이 몇개의 덩어리들로 나누어 져 있으며, 그 덩어리들은 각각 하나씩 루프를 가지고있다.루프에 포함되지 않는 점들은 K-1개의 경우를 가지게되고, 결국 루프를 구성하는 점들의 경우의 수를 구할 수 있어야 한다. 1번부터 M번까지, M개의 점으로 이루어진 루프가 있다면 1번 = K..

출처 : Google Codejam Qualification Round 2015 C. Dikstra (https://code.google.com/codejam/contest/dashboard?c=6224486#s=p2) ProblemThe Dutch computer scientist Edsger Dijkstra made many important contributions to the field, including the shortest path finding algorithm that bears his name. This problem is not about that algorithm. You were marked down one point on an algorithms exam for misspelli..

https://www.acmicpc.net/problem/1153 다양한 풀이방법이 있겠지만, Goldbach's Conjecture라 불리는 가설?을 이용하여 풀었다. 항상 소수관련문제는 정수론과 뗄레야 뗄 수 없는것 같기도하고.. Goldbach's Conjecture는 아직 증명이 되지않은 정수론 미해결문제중 하나로 "2보다 큰 모든 짝수는 두개의 소수의 합으로 나타낼 수 있다"는 가설이다. 물론 아직 반례를 찾지못해 미해결문제로 남아있다. 즉, 앵간히 큰 짝수(우리가 문제에서 접할 수 있는 수)까지는 다 성립한다는 뜻. #include int num[1000001] = { 0 };int N;void prime() { for (int i = 2; i*i

Maximum Sum Subarray라 불리는 문제에서 슬라이딩 윈도우기법으로 O(N)에 해결하는 알고리즘 Maximum Sum Subarray란 수열의 연속 부분합중 가장 큰 값을 찾는 문제 Kadane Algorithm을 간략히 설명하자면 1. 앞에서부터 수를 하나씩 더해가면서 sum이라는 변수에 매번 값을 저장한다. 2. 만약 sum이 음수가 되는 지점이 발생한다면, sum은 0으로 초기화한다. 3. 이 sum들을 매번 maximum값으로 갱신한다. 구간의 index가 필요하다면 sum을 갱신하는 부분에 추가하여 나타낼 수 있다. 위의 내용은 1-dim array에 관한 내용이고 이를 응용하면 2-dim array에서의 문제는 O(N^3)에 해결할 수 있다. (2차원 배열에서 최대 부분합) 참고영상..

https://www.acmicpc.net/problem/1750 naive하게 생각하면 포함-배제의 원리를 생각하기 쉬우나 조금 생각해보면 TLE가 떨어질거라는 확신이 드는 문제이다. DP를 이용해 N개의 원소중 1~i번째 숫자들을 후보로 하여 최대공약수가 j인 갯수를 d[i][j]라고 놓으면 생각보다 쉽게 점화식을 세울 수 있다. #include #define MAX 10000003#define LL long longint num[101];__inline int min(int a, int b) { return a > 1]; while ..

잘 정리된 블로그가 있어서 링크로 대체한다. 다익스트라 알고리즘(Dijkstra Algorithm) : 한점 - 다수의점 (음수가중치X)벨만-포드 알고리즘(Bellman-Ford Algorithm) 한점 - 다수의점 (음수사이클X)플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 모든점 - 모든점