Koo's.Co

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 위상정렬을 이용한 기본 문제입니다. 1) 진입 차수를 저장할 리스트 2) graph의 형태를 저장할 리스트 진입차수 진입 차수는 간선의 화살표를 받는 개수를 의미합니다. (도착지가 되는 횟수) 1은 0 2는 1에서부터 오므로 1 3은 1에서부터 오므로 1 4는 2와 3으로부터 오므로 2 5는 2와 4로부터 오므로 2 구하고자 하는 진입차수는 [0, 1, 1, 2, 2] 가 됩니다. 1) queue를 생성하고 진입차..

2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 위상 정렬과 dp를 이용해 풀 수 있는 문제입니다. ACM Craft 문제와 거의 동일한 문제인 것 같습니다. 먼저 위상 정렬을 이용해 각 값들의 진입 차수를 구해준 후 bfs를 사용했습니다. 작업을 하기 위해서는 선행 작업들을 모두 수행해야 하기 때문에 dp리스트를 만들어 이전 작업들 중 가장 시간이 오래 걸린 값들만 저장해줍니다. -> max를 이용해 노드에 한 번 도착할 때마다 값을 갱신! 모든 작업이 완료된 시간을 구해야하기 때문에 max를..

1. 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 새로 오는 수는 그 전의 숫자들에 각각 1, 2, 3을 더해 만들 수 있다. 4의 경우 이전 3개의 숫자에 1, 2, 3을 더해 만들 수 있다. 그러므로 구하고자 하는 점화식은 위와 같다. import sys read = sys.stdin.readline dp = [0, 1, 2, 4] + [0] * 7 for i in range(4, 11): dp[i] = dp[i-1] + dp[i-2] + dp[i-3] for _ in range(int(read())): print(dp[int(read())]) 2. 1, 2, 3 더하기 2..

16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 bfs를 사용해서 푸는 문제입니다. 문제의 조건이 많은데 하나씩 살펴보며 풀어보겠습니다. 상하좌우 이동 가능 -> directions = [(-1, 0), (0, -1), (1, 0), (0, 1)] 상어와 물고기는 크기를 갖고 있음 처음 상어 크기 = 2 -> shark_size = 2 물고기의 크기 = 1 ~ 6 상어보다 "작은" 물고기만 먹을 수 있다 상어와 크기가 "같은" 물고기는 지나갈 수 있다 상어보다 크기가 "큰" 물고기는 지나갈 수 없다..

15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 이전에 있던 연산자 끼워넣기 문제와 동일하게 dfs를 사용한 문제입니다. 다른 점은 이전 문제들은 연산의 우선순위가 없고 앞에서부터 계산하는 문제였는데 이 문제는 곱셈과 나눗셈이 덧셈과 뺄셈보다 우선순위가 높다는 점입니다. 처음 문제를 풀었을 때는 이전 문제와 다르게 문자열 타입에 연산자를 합쳐서 마지막에 eval함수를 이용해 계산하는 방법을 사용했습니다. def dfs(idx, res, plus..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 풀이 각 도시들의 관계를 입력받고 이들 관계를 이용해 union-find 알고리즘을 사용하여 정답을 구할 수 있다. 인덱싱에 주의하고 union-find 알고리즘을 알고 있으면 금방 풀 수 있는 문제다. all 함수를 오랜만에 사용해봤는데 여러 상황에 쓸 수 있을 것 같다. 문제를 잘못 읽어서 M개만큼의 도시를 입력받는줄 알고 계속 IndexError에 시달렸다. 문제를 꼼꼼히 읽는 습관을 가지자.. import sys sys.setrecursionlimit(1..

1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 union-find 알고리즘을 이용하는 문제이다. find함수를 구현할 때 루트 노드를 갱신시키지 않으면 recursion을 반복할 때마다 처음부터 부모노드를 다시 찾아야 하기 때문에 꼭 루트 노드를 갱신시켜주는 기능을 생각해야 한다. recursion을 사용하기 때문에 sys.setrecursionlimit의 값도 바꿔주어야 한다. import sys sys.setrecursionlimit(10 ** 6) read..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 전에 풀었던 연구소 문제와 비슷하다 생각하여 백트래킹 방법을 먼저 생각해봤다. 연구소 문제는 주어지는 맵의 크기가 최대 8 x 8인 64였는데 이 문제는 최대 크기가 1,000 x 1,000으로 bfs를 사용해서 풀 경우 시간 복잡도가 O(NM^2)이 되는 절대 풀 수 없는 문제였다^^ import sys from collections import deque read = sys.stdin.readline direction = [(-..