문제 이해 단계 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 첫 번째 줄에 문장이 주어지고, 두 번째 줄에 폭발 문자열이라는 특정 키워드가 주어진다. 문장에서 폭발 키워드가 있으면 그 부분을 지운다. 그리고 문장을 이어 붙인다. 문장을 이어 붙였을 때, 또 키워드가 완성된다면 그 부분을 지운다. 이런 식으로 모든 폭발키워드를 지운 후, 남은 문장을 출력한다. 문제 접근 단계 제한사항부터 보자. 문장의 길이는 최대 1,000,0..

문제 이해 단계 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 입력으로 정점의 개수 N과 간선의 개수 E가 주어진다. 여기서 간선은 양방향 그래프이다. 정점 1에서 정점 N까지 최단경로로 움직여야 하는데, 무조건 타깃으로 설정한 정점 A와 정점 B를 방문해야 한다. 여기서는 한번 이동했던 간선도 다시 이동하는 것을 허락한다. 이러한 조건일 때 두 정점을 반드시 거치면서 최단 경로로 이동할 때의 값을..

문제 이해 단계 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수열이 존재한다. n이 입력으로 들어올 때, n번째 수열의 값을 구하는 것이 문제. 문제 접근 단계 이 문제가 골드 2인 데는 제한사항 때문이다. 입력으로 들어올 수 있는 n이 10^18까지 가능하다. 엄청나게 크다. int 자료형으로는 절대 받을 수 없고 가장 큰 자료형인 long long int를 써야지만 받을 수 있다. 기존에 풀던 DP방식으로 문제를 풀면 시간 복잡도가 O(n)이 나온다. 이는 결국 1초가 넘어 시간초과가 나오기 때문에 다른 ..

문제 이해 단계 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 입력으로 A, B, C가 들어온다. 자연수 A를 B번 곱하고, C로 나눈 나머지를 출력해라. 문제 접근 단계 상당히 간단한 문제로 보인다. 하지만 그렇지 않다. 여기에는 2가지의 문제점이 존재한다. 첫 번째는, 수의 범위이다. 제한사항을 보면 입력이 2,147,483,647까지다. 입력부터 20억이 넘어가기 때문에 20억^20억 long long int 자료형을 아득히 넘어간다. 그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다. 자료형을 넘..

문제 이해 단계 https://www.acmicpc.net/problem/2263 이진트리의 정점이 1~n까지의 번호가 중복 없이 매겨져 있다. 이진트리의 중위 순회와 후위 순회가 입력으로 주어질 때, 전위 순회를 출력하는 문제 문제 접근 단계 전위, 중위, 후위 순회의 개념과 특성을 미리 알고 있어야 한다. 전위 순회 : 루트 → 왼쪽 → 오른쪽 중위 순회 : 왼쪽 → 루트 → 오른쪽 후위 순회 : 왼쪽 → 오른쪽 → 루트 그림을 보면서 하는 것이 가장 빠르다. 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이 된다. 우리는 이 2가지 정보를 가지고 전위 순회를 구해야 한다. 일단 후위 순회는 루트 노드가 마지막에 오기 때문에,..

문제 이해 단계 https://www.acmicpc.net/problem/22861 main 폴더 안에 있는 폴더의 총 개수 N과 파일의 총 개수 M이 주어진다. 그리고 폴더를 옮기는 횟수 K가 주어진다. 폴더를 옮긴다는 것은 폴더 A에 있던 하위 폴더와 파일들을 모두 폴더 B로 옮긴다는 것 그리고 마지막에 쿼리 Q가 주어지고, 그 쿼리에 맞는 파일의 종류가 몇 개인지, 그리고 파일의 수가 몇 개인지 출력하는 문제 사실문제가 상당히 길기 때문에, 링크를 타고 들어가서 문제를 읽고 오는 편이 낫다. 문제 접근 단계 입력으로 들어오는 것이 많다. 그렇기 때문에 더더욱 제한사항부터 살펴봐야 한다. 폴더(N)와 파일(M)의 개수는 최대 1,000개까지 가능하다. 파일을 옮기는 횟수(K)도 최대 1,000회까지 ..

문제 이해 단계 https://www.acmicpc.net/problem/9663 NxN짜리 체스판에 N개의 퀸을 서로 공격하지 못하게 둔다. N이 주어졌을 때 이 경우의 수를 구하는 문제 문제 접근 단계 퀸이 움직일 수 있는 경로는 위와 같다. 퀸을 정가운데 놨을 때, 노란색 영역에는 퀸을 두면 안 된다 제한사항부터 알아보면, N은 최대 14까지 가능하다.이 말은 맵은 14x14까지, 체스 말은 14개까지 가능하다는 것이다. N이 상당히 작기 때문에 완전탐색이 가능할 것 같다. N개의 퀸을 체스판에 두는 모든 경우의 수를 구해야 하기 때문에, 퀸을 모든 곳에 둬서 판단하는 방법밖에 없다. 그런데 일반적인 백트래킹으로 이를 확인하기에는, 최대 14^14로 대략 100억이 넘어간다.(시간 초과) 그래서 2..

문제 이해 단계 https://www.acmicpc.net/problem/1167 입력으로 트리의 정점 개수 V와 간선의 정보가 주어진다. 트리의 간선에는 가중치가 존재한다. 임의의 두 정점 사이의 거리 중, 가장 긴 것의 길이를 출력하는 문제 문제 접근 단계 문제 조건부터 살펴보면, 정점의 개수가 최대 100,000개다. 그렇다면 간선의 개수는 훨씬 더 많이 가능하다는 소리이다. 모든 정점을 일일이 하나씩 다 살펴보기에는 무리이다. 한 정점을 특정하여 찾는 방법밖에 없는 것 같다. 두 정점 사이의 길이가 가장 길어지려면? 트리에서 두 정점의 길이가 가장 길어지려면 어떻게 해야 할까? 당연히 한쪽 끝노드(리프 노드)에서 끝노드로 가는 것이 길이가 가장 길어질 것이다. 즉 우리가 우선적으로 찾아야 할 것은..