https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 💡IDEA 수학과 분할 정복을 사용하는 문제이다. 피보나치 수열을 계산할 때 동적 계획법이나 변수 두개를 치환하면서 갱신하는 식으로 풀었었는데, 이 문제는 n이 너무 커서 감당할 수가 없다. 어떻게 풀어야할지 도무지 모르겠어서 https://www.acmicpc.net/blog/view/28 의 도움을 받았다. n이 굉장히 클 때 피보나치 수열을 계산하기 위해서는 행렬 제곱을 사용해야 한다. 아래 코드에서 matmul 함수는 행렬 곱셈 후 1000000007로 나누어주는 연..
https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 💡IDEA 다익스트라 또는 플로이드-워셜 알고리즘을 사용하는 문제이다. 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘(S.S.S.P - Single Source Shortest Path) 이라면, 플로이드-워셜 알고리즘은 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다. 플로이드-워셜 알고리즘은 다익스트라 알고리즘과는 다르게 음의 간선도 사용할 수 있다. 플로이..
https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net 💡IDEA 분할 정복과 수학을 사용하는 문제이다. 이 문제를 이해하려면, 일단 모듈로 곱셈 역원에 대해 알아야 한다. 학부 때의 기억을 되살리느라 힘들었다. 문제에서 자세히 설명해주고 있는 것 같지만, 문제만 봐서는 잘 이해가 되지 않을 것이다. 중요한 부분은 다음 내용이다. 어떤 분수가 기약분수로 나타냈을 때 a/b이면, 이 분수는 $a × b^{-1} (mod X)$ (X는 소수)으로 대신 계산하도록 한다. 여기서 $b^{-1}$은 b의 모듈러 ..
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 💡IDEA 벨만-포드 알고리즘을 사용하는 문제이다. 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘으로, 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다. 다익스트라 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 한 단계씩 최단 거리를 구한다. 가중치가 음수인 간선이 없다면 최적의 해를 찾을 수 있다. 우선순위 큐(he..
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 💡IDEA 다익스트라를 사용하는 문제이다. 1916번 최소비용 구하기 문제와 유사한 문제인데, 최소비용 뿐만 아니라 경로까지 구해야 한다. 백준에서는 시간초과 문제를 해결하기 위해 다익스트라 문제에서 대부분 heapq를 사용한다. edges 배열을 n+1이 아니라 m+1로 잘못 풀어서 3가지 다른 방법으로 풀었는데도 실패(IndexError)가 떴다. 결국 n+1로..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 💡IDEA 집합을 사용하는 문제이다. 진실을 아는 사람과 파티에 포함된 사람을 집합으로 만들어준다. 진실을 아는 사람이 포함된 파티에 있는 모든 사람을 진실을 아는 사람으로 취급해야한다. 즉, 교집합으로 찾으면서 진실을 아는 사람 집합을 업데이트 한다. 갱신한 진실을 아는 사람 집합과 파티에 있는 사람 집합을 다시 교집합 했을 때 겹치는 부분이 없다면 카운트 센다. 📌CODE import sys input ..
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 여러가지 조건들을 구현해야 하므로, 함수를 적절하게 사용하는 것이 좋을 것 같다. 내부 공기 / 외부 공기 체크 업데이트가 자주 이루어지므로, cheese 배열과 똑같은 air 배열을 만들어서 공기를 체크한다. 가장자리는 모두 0이라고 문제에서 주어졌으므로, (0,0) 좌표에서부터 BFS를 통해 모든 접한 곳의 외부 공기를 -1로 변경한다. 내부..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 1697번 숨바꼭질 문제와 유사한데, 수빈이가 동생을 찾는 가장 빠른 시간 뿐만 아니라, 가장 빠른 시간으로 찾는 방법의 개수도 구해야 한다. 조심해야 할 점은 방문 처리 부분이다. 예를 들어, 1에서 2로 변했다면 +1을 했을 수도 있고, *2를 했을수도 있어서 append 시에 방문 처리를 해주면 +1로 간 방법과 *..
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 💡IDEA 분할 정복을 사용하는 문제이다. 문제를 처음 보았을 때, 배열 안의 각 숫자를 제곱하면 되는 건 줄 알았지만 그게 아니라 행렬 자체를 제곱하는 문제였다. 선형대수학에서 행렬의 곱셈을 알아햐 하는데, 공식은 다음과 같다. A 행렬 × B 행렬 을 계산하기 위해서 A 행렬의 열과 B 행렬의 행의 각 수들을 곱해서 더한다. operator 라이브러리의 matmul 라는 행렬 곱셈 함수를 사용할 수 있겠지만..
https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 💡IDEA 백트래킹을 사용하는 문제이다. 백준에 N과 M 문제가 많은데, 12번 쯤 되면 순열을 조건별로 구할 수 있는 달인이 되었을 것이다. 15657. N과 M (8) 과 15663. N과 M (9) 두 문제를 적절하게 섞어서 풀 수 있는 문제다. 같은 수를 여러 번 골라도 되고, 비내림차순인 수열을 구한다. 같은 수 중복 허용이므로 반복문의 시작점은 idx 부터이고, tmp를 통해 중복되..
