자서전

3줄요약 dfs 백트래킹 문자열 서론 이 문제는 dfs + 백트래킹의 기본형 문제라고 볼 수 있다. 본론 우리가 이 문제를 풀 때 알아야 하는 것은 한 가지 뿐이다. dfs (응용) 어짜피 알파벳 대문자는 26개이기 때문에, dfs 완전탐색을 돌려도 되는 문제이다. (시간복잡도가 그렇게 크게 안 나온다.) 지금까지 어떤 알파벳을 체크했는지 알 수 있다면, 같은 문자가 두 개 나왔을 때 백트래킹을 할 수 있으므로, 그 방식으로 문제를 풀면 된다. #include #include using namespace std; #define MAXCHK (65 + 26 + 1) int Y, X; int graph[21][21]; bool check[MAXCHK]; // just for init int dfs(int x..

2623번: 음악프로그램 (acmicpc.net) 3줄요약 위상정렬 그래프 dfs (사이클 판정) 서론 이 문제는 위상정렬을 활용한 문제라고 볼 수 있다. 그냥 위상정렬이라고 갖다 박으면 안되고, 위상정렬이 어떨 때 성립하지 않는지 알아야 이 문제를 풀 수 있다. (그래도 골2는 좀...) 본론 우리가 이 문제를 풀 때 알아야 하는 점은 두 가지다. 위상정렬 위상정렬이 성립할 조건 ( 사이클이 존재하는 경우이다. 실제로 문제에서 사이클이 존재하면 성립하지 않는 것을 알 수 있다. 이제 끝났다. 우리는 위상정렬을 하기 전에 이 그래프에 사이클이 있는지만 체크해주면 된다. 하지만 N의 범위가 이 문제 처럼 10^5가 아니기 때문에, 보다 간단한 알고리즘을 응용할 수 있다. #include #include u..

1162번: 도로포장 (acmicpc.net) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 3줄요약 다익스트라 dp 혼종 서론 일반적인 최단거리를 구하는 문제가 아닌, 최단거리를 구하되, K (K