코팩

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 풀이 위상정렬문제인데 입력값이 이전의 문제와 다르게 들어온다. **중복된 간선이 들어올 수 있기 때문에 주의해야한다. : 집합으로 해결해주었습니다. 코드 # 2623번 음악프로그램 import sys from collections import deque n, m = map(int, sys.stdin.readline().split()) graph = [set() for _ in ..

https://www.acmicpc.net/status?group_id=13709 채점 현황 www.acmicpc.net 풀이 건물을 짓기 위해서는 선행으로 지어져야하는 건물이 존재한다. - 위상정렬 알고리즘을 적용해야함을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com 코드 # 1516번 게임개발 import sys from collections import deque n = int(sys.stdin.r..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다. (위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.) combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다. 이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다. 시간초과 문제로 인해 PyPy3로 제출해주었습니다. 코드(PyPy3..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 풀이 기존 bfs 알고리즘을 사용할 시에 시간초과가 일어난다. 주어지는 유저의 수가 n^6까지 주어지기 때문이다. 그래서 분리 집합 알고리즘을 이용해서 답을 구해주었습니다. bfs를 사용하게 되면 확인해야하는 친구 관계의 개수만큼 bfs가 돌아가기에 매우 비효율적입니다. 그러나 분리집합을 사용하게 되면 연결된 최상위 노드만이 저장된 리스트를 비교함으로 효율적으로 ..

https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 풀이 이분탐색 방법을 이용해서 풀어주어도 괜찮겠지만, 집합을 이용해서 문제를 풀어주었습니다. 코드 # 2776번 암기왕 t = int(input()) for _ in range(t): _ = int(input()) note_1 = set(input().split()) _ = int(input()) note_2 = input().split() for i in note_2: if i in note_1: p..

https://www.acmicpc.net/problem/1788 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 다이나믹 프로그래밍을 통해서 문제를 풀어주었습니다. 코드 # 1788번 피보나치 수의 확장 n = int(input()) dp = [0, 1, 1] for i in range(3, abs(n)+1): dp.append((dp[i-2] + dp[i-1])%1000000000) if n > 0: print(1, dp[-1], sep="\n") elif n < 0:..

https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 다이나믹 프로그래밍으로 피보나치 수를 구해주었습니다. 코드 # 10826번 피보나치 수 4 n = int(input()) dp = [0, 1] for i in range(2, n+1): dp.append(dp[i-2] + dp[i-1]) print(dp[n]) 출력결과