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..

Counter Clock Wise는 오른손 법칙을 이용해 주어진 세 점의 방향성을 알 수 있는 알고리즘입니다. 위와 같이 세 점이 주어질 때 이들 벡터와 CCW 알고리즘을 이용해 세 점의 방향을 구할 수 있습니다. A를 기준으로 B와 C에 대한 벡터들의 외적을 구합니다. 여기서는 외적의 결과가 음수기 때문에 오른손 법칙에 의해 세 점이 시계 방향을 갖는 것을 확인할 수 있습니다. 2차원에서의 외적은 z값을 0으로 놓고 계산하여 구할 수 있습니다. x1, y2, z3 = map(int, input().split()) x2, y2, z3 = map(int, input().split()) x3, y3, z3 = map(int, input().split()) u = (x2 - x1, y2 - y1, z2 - z..

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..