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를 통해 중복되..
https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 💡IDEA 조합의 개념을 알면 풀 수 있는 문제이다. nCr = n!/(n-r)!r! 으로 나타낼 수 있는데, 팩토리얼을 재귀로 구해도 되고, DP를 사용해도 될 것 같다. 아래 코드는 그냥 반복문으로 곱하면서 답을 구하는 풀이이다. n!/(n-r)! = n(n-1)(n-2)...(n-r+1) 임을 사용해서 먼저 구한 후, r!를 나누어준다. 📌CODE n, m = map(int, input().split()) ans = 1 for i in range(n, n-m, -1): ans *= i tmp = 1 for ..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 처음에는 replace를 사용하여 풀었지만 역시나 시간 초과가 발생했다. 스택을 사용해서 입력 문자를 하나씩 넣고, 스택에 쌓인 문자열 끝에 폭발 문자열이 있으면 그만큼 pop 해준다. 조인을 잘 활용해야 하고 스택에 아무것도 남아있지 않다면 "FRULA"를 출력한다. 📌CODE import sys input = sys.stdin.readline..
https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 💡IDEA DFS를 사용하는 문제이다. 행, 열, 파이프 방향 세 변수를 사용하여 DFS를 수행한다. 파이프 방향은 0이 가로, 1이 세로, 2가 대각선이다. 다음 파이프가 가로로 갈 수 있는 경우는 현재 파이프가 가로 혹은 대각선 인 경우이다. 가로로 가기 위해서는 다음 열 값이 범위 내에 있고, 빈 칸(0)이어야 한다. 다음 파이프가 세로로 갈 수 있는 경우는 현재 파..
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 현재 값의 2배, 또는 10배 후 더하기 1 한 값이 되므로, 현재 값보다 작아지는 경우가 없다. 즉, 방문을 확인할 배열이 굳이 필요 없다. BFS를 수행하며 A가 B가 될 때 수행할 동안 카운트해준 값을 반환한다. BFS를 수행했음에도 B가 되지 못했다면 -1을 반환한다. 📌CODE from collections import deque A, B = map(int, input().split()) def solve(n): q = deque() q.append((n, 1)) while..
