자서전

3줄 요약: DP 난 도대체 왜 팰린드롬을 분할하는 것인지 모르겠다. 어느 문제에서는 유사회문인지를 출력하라 하지 않나, 어느 문제에서는 공장을 개설하지 않나... 팰린드롬은 내가 제일 싫어하는 문제 중 하나이다. 이 문제를 풀 때는 DP를 두 번 사용하여 풀 수 있다. dp[i][j] = i번째 문자부터 j번째 문자까지 회문인지 체크하는 dp dp2[i] = i번째 인덱스에서 분할 개수의 최솟값 dp[i][j]가 약간 이해가 안 갈 수 있는데, 예를 들어보자. 문자열 'BOTTOM' 에서 제일 앞의 인덱스를 1이라고 할 때, dp[1][6]은 false이고, dp[2][5]는 true, dp[3][4]도 true... 이렇게 볼 수 있다. 이를 어떻게 구현할까? dp[i][j] 가 true이고, str..

1949번: 우수 마을 (acmicpc.net) 3줄요약 트리 DP 문제풀이 우리는 문제에서 주어진 3가지 조건들을 만족해나가면서 풀어야 한다. 여기서 우리가 주목해야 할 점은 3번 조건이다. 우리는 약간 생각해보면 3번 조건이 1, 2번 조건에 통합된다는 것을 알 수 있다. 애초에 인접한 마을이 모두 우수 마을이 아니면, 2번 조건이 성립하지 않으므로 그냥 그 마을을 우수 마을로 선정하는 것이 더 이득일 수 있다. 즉, 3번 조건을 만족하지 않는 해가 있다면 그것은 최적의 해가 아니라는 소리다. 이제 진짜 문제풀이로 가보도록 하자. dp[node][a] 를 정의한다. (a = 이 마을을 우수 마을로 설정할 것이면 1, 아니면 0) Top-Down 방식(dfs)로 해결한다: 만약 a가 1이라면, dp[n..

3줄요약 그리디 정렬 구현 서론 하고 싶은 얘기는 없다. 본론 이 문제는 그리디로 풀 수 있다. 사람의 수도 아닌, A 혹은 B에서 떨어진 거리에 대하여 정렬하지 않고, A와 B의 거리의 차가 큰 순서대로 정렬한다. 그리고 정렬한 배열의 i = 0~N-1 에 대해 다음의 4가지 경우를 생각한다. 만약 a가 더 크다면, 그리고 지금 있는 풍선 수로 i번째 인덱스의 팀의 사람들을 충당할 수 있을 때의 경우 a가 더 크지만 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우 b가 더 크고, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 있을 때의 경우 b가 더 크지만, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우 이 경우들에 대해 각각 알맞은 처리를 하면 된다. 코드는 밑에 있다...

3줄요약 그리디 서론 이 문제는 여러모로 함정이 많은 문제이다. 대표적으로, 입력 데이터가 오름차순이더라도 문제에서 따로 명시된 정보가 없으면 정렬해야 한다는 것이다. 아이디어가 굉장히 빨리 떠올랐기 때문에, 10분만에 풀 수 있었다. 본론 우선 먼저 나는 냅색 문제로 접근을 시도했다. 하지만 N

3줄요약 아이디어 최소 스패닝 트리 정렬 서론 이 문제는 최소 스패닝 트리에 아이디어를 결합한 문제이다. 골드 1치고는 매우 어렵다고 생각한다. 본론 N

3줄요약 백트래킹 빡구현 서론 이 문제를 보고 처음에 난감했었다. 이 문제가 어떻게 골드 4인지 모를 만큼 감이 안 잡혔다. 이 문제를 브루트포스로 풀면 최대 O(9^81) 의 시간복잡도가 나오기 때문에, 이 문제는 브루트 포스로 풀 수 없다. 하지만, 백트래킹을 잘 하면 1억번의 연산 밑으로 해결할 수 있다는 생각이 들어 실행에 옮겼다. 본론 이 문제는 사전순으로 앞서는 것을 출력해야 하기 때문에, 체크를 다음의 순서로 해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ... 다음의 순서대로 진행하되, 그 자리에 숫자를 넣었을 때 안되는 경우를 미리 체크해 주면서 백트래킹을 실행하면, 문제가 풀린다. 코드는 밑에 있다. #..

3줄요약 다익스트라 (Similar to KCM Travel, but has lil different) dfs인줄 알았는데 또익스트라 서론 다익스트라 문제이다. 이 문제는 영양가가 넘쳤다. KOI 2016 고등부 2번문제이기도 하고, (나는 중학생이지만) 다익스트라와 기본적인 사고방식을 성장시키기 좋은 문제였다. 본론 기본적인 다익스트라 문제와는 다르게, 이 문제는 다익스트라를 2번 실행해야 한다. 첫 번째로 모든 정점에서부터 j번째 정점으로 가는 최단거리를 구하는 다익스트라, ( 시간복잡도: O(V * E * log(V) ) 두 번째로 첫 번째에서 구한 dist[i][j] 배열을 토대로 1번 정점에서 V번 정점으로 가는 최단거리를 구하는 다익스트라이다. ( 시간복잡도: O (V^2 * log(V) ) ..

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