문제 이해 단계 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개다. 그렇다면 간선의 개수는 훨씬 더 많이 가능하다는 소리이다. 모든 정점을 일일이 하나씩 다 살펴보기에는 무리이다. 한 정점을 특정하여 찾는 방법밖에 없는 것 같다. 두 정점 사이의 길이가 가장 길어지려면? 트리에서 두 정점의 길이가 가장 길어지려면 어떻게 해야 할까? 당연히 한쪽 끝노드(리프 노드)에서 끝노드로 가는 것이 길이가 가장 길어질 것이다. 즉 우리가 우선적으로 찾아야 할 것은..

문제 이해 단계 https://www.acmicpc.net/problem/2638 NxM 크기의 맵에 1로 표기된 치즈가 있다. 치즈는 외부 공기와 두 번 이상 접촉하면 녹는다. 겉에서부터 치즈가 녹아내릴 때, 모든 치즈가 녹아내리는 데 걸리는 시간을 구하는 문제 문제 접근 단계 문제의 조건부터 살펴보자. 맵의 크기는 최대 100x100까지 가능하다. 맵의 크기는 그렇게 크지 않아서, 탐색을 하기에는 무리가 없을 것 같다. 문제의 유형 문제의 유형을 추측해 볼 때, 2차원 맵이 주어지고, 치즈가 없어지는 조건이 네 면 중 두 변이 접촉해야 하는 것이라고 했다. 이를 그림에서 살펴보면, 1이 없어지기 위해서는 겉에 있는 0과 2개 이상 인접해야 한다. 이를 쉽게 알아내기 위해서는 너비우선탐색(BFS)으로 ..

문제 이해 단계 https://www.acmicpc.net/problem/1043 사람 수 N과 파티의 수 M이 주어진다. 그다음줄에는 진실을 아는 사람의 번호가 주어지는데, 지민이는 모든 파티를 참석하면서 거짓말을 쳐야 한다. 하지만 진실을 아는 사람이 있는 파티에서는 무조건 진실을 말해야 한다. 진실을 들은 사람이 거짓말을 듣거나, 거짓말을 들은 사람이 진실을 들으면 이는 실패한 것이다. 해당 조건에서 지민이가 거짓말을 칠 수 있는 파티의 최대 수를 구하는 문제 문제 접근 단계 문제의 제한조건부터 살펴보자. 사람의 수 N과 파티의 수 M이 모두 50까지 가능하다. 상당히 작은 숫자라서, 완전 탐색이나 원하는 대로 풀이가 가능할 것 같다. 문제의 특징 이 문제의 특징적인 점은, 옳고 그름을 판단하기 위..