늘 겸손하게

목차 문제명 문제풀이 코드 친구비 문제 유형 : 그래프 이론, 그래프 탐색, 분리 집합 난이도 : 골드 4 https://www.acmicpc.net/problem/16562 문제 풀이 '친구의 친구는 친구' 이기 때문에 분리 집합으로 친구끼리 같은 집합으로 묶은 뒤, 각 집합에서 최소 Ai만 뽑아내어 합했을때 값이 K 이하면 출력, K 초과면 "Oh no"를 출력하면 된다. 구현 시 주의사항은, union 메소드로 요소가 다수인 집합과 요소가 다수인 집합을 묶었을때 집합의 모든 root값을 업데이트 해주어야 한다. 예로, root[1] = 1 root[2] = 2 root[3] = 2 root[4] = 2 root[5] = 1 이고 union 함수가 def union(a, b): a = find_roo..

목차 문제명 문제풀이 코드 선수과목 (Prerequisite) 문제 유형 : DP, 위상정렬 난이도 : 골드 5 https://www.acmicpc.net/problem/14567 문제 풀이 위상정렬 알고리즘을 조금 응용한다. 큐 내부에 요소 하나를 빼내어 탐색하고 다음 탐색할 요소들을 큐에 다시 넣는 방법 대신, 큐에 존재하는 요소를 전부 빼내어 탐색하는 것을 하나의 loop으로 보고 모든 요소를 탐색할때까지 반복한다. 코드 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) graph = [[] for _ in range(N + 1)] degree = [0] * (N + 1..

목차 문제명 문제풀이 코드 연산자 끼워넣기 (3) 문제 유형 : DFS, 백트래킹 난이도 : 골드 4 https://www.acmicpc.net/problem/15659 문제 풀이 백트래킹 문제이므로 기저조건으로 N - 1개의 연산자를 모두 썼을때 식을 계산하여 최대, 최소 값을 구한다. 함수를 재귀적으로 호출하는 조건은, 사용가능한 연산자가 남아있을 경우이다. 코드 N = int(input()) A = list(map(int, input().split())) plus, minus, multi, div = map(int, input().split()) max_ans = int(-1e11) min_ans = int(1e11) def rec(string, p, m1, m2, d, cnt): if cnt ==..

목차 문제명 문제풀이 코드 백준 - 16929번 : Two Dots 문제 유형 : DFS, 그래프 탐색 난이도 : 골드 4 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 문제 풀이 모든 정점에 대하여 1. 주어지는 게임판과 동일한 넓이, 높이의 배열을 선언하고 2. dfs로 그래프를 탐색하면서 시작점에서 몇번째로 탐색한 정점인지를 기록합니다. 3. 탐색이 끝나면 시작점 주위에 값이 4 이상인 값이 있다면 싸이클이 있는것이므로 "Yes..