주제무 다시 봐도 핵심만 보이게끔!

무방향 그래프와 서로소 집합 서로소 집합의 필요성을 이해하기 위해서 아래 문제를 읽어보자. https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제를 읽어보면 진실을 알고 있는 사람이 포함된 파티와 포함되지 않은 파티로 나누고 싶을 것이다. 바이러스가 전염되는 것처럼 진실을 알고 있는 사람이 포함된 파티(그래프)는 모두 진실을 알게 된다. 하지만 단절된 그래프는 전염되지 않기도 하다. 위와 같은 상황에서 서로소 집합의 개념을 적용할 수 있다. 서로 다른 파티..

코테 연습 기타 첫 번째 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() def multiply(b): if b == 1: return A sub_result = multiply(b//2) % C result = sub_result ** 2 return result*A if b % 2 == 1 else result A, B, C = map(int, input().split()) print(multiply(B)..

코테 연습 BFS/DFS 첫 번째 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() sys.setrecursionlimit(2001) N, M = map(int, input().split()) relation = [[] for _ in range(N)] for _ in range(M): p_1, p_2 = map(int, input().split()) relation[p_1].append(p_2) relation[p_2].append(p_1) def ..

코테 연습 다이나믹 프로그래밍 첫 번째 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N, K = map(int, input().split()) items = sorted([list(map(int, input().split())) for _ in range(N)], revers..

코테 연습 다이나믹 프로그래밍 첫 번째 https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 왼쪽부터 차례대로 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 www.acmicpc.net import sys input = lambda: sys.stdin.readline().rstrip() N, K = map(int, input().split()) A = list(map(int, input().split())) dp = [False] * N dp[0] = True for idx in ra..