공작소

문제 링크 : https://www.acmicpc.net/problem/2630풀이 과정분할 정복으로 풀이했다.합치는 과정에서, (1) 특정 색의 색종이가 4등분한 영역에서 각각 1개이고, (2) 다른 색의 색종이가 4등분한 영역에서 각각 0개라면, 특정 색의 색종이 1장으로만 해당 영역이 구성된 것으로 결과를 반환한다.전체 코드# 2630 : 색종이 만들기import sysinput = sys.stdin.readlinen = int(input().rstrip())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]def func(i, j, size): if size == 1: return [1, 0] if arr[i]..

문제 링크 : https://www.acmicpc.net/problem/1764풀이 과정먼저, 듣도 못한 사람의 명단을 Dictionary 에 저장한다.그 다음, 보도 못한 사람이 Dictionary 에 존재한다면 정답 배열에 넣는다.정답 배열 요소들을 사전순으로 출력한다.전체 코드# 1764 : 듣보잡import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())dic = {}for _ in range(n): string = input().rstrip() dic[string] = 1ans = []for _ in range(m): string = input().rstrip() if dic.get(string..

문제 링크 : https://www.acmicpc.net/problem/1697풀이 과정수빈이의 위치를 정점으로, 3개의 이동하는 방법을 간선으로 인식하여 너비 우선 탐색을 이용해 풀이했다. 전체 코드# 1697 : 숨바꼭질import sysfrom collections import dequeinput = sys.stdin.readlinen, k = map(int, input().rstrip().split())queue = deque()queue.append(n)visited = [False for _ in range(100001)]visited[n] = Truetime = 0done = Falsewhile queue: size = len(queue) for _ in range(size): ..

문제 링크 : https://www.acmicpc.net/problem/1620풀이 과정파이썬의 Dictionary 자료형을 사용해 풀이했다.전체 코드# 1620 : 나는야 포켓몬 마스터 이다솜import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())poke = {}for i in range(1, n+1): string = input().rstrip() poke[string] = str(i) poke[str(i)] = stringfor _ in range(m): string = input().rstrip() print(poke[string])

문제 링크 : https://www.acmicpc.net/problem/1389풀이 과정유저의 수 N 제한이 작고, 다른 모든 친구들과의 단계 합이 필요하므로 플로이드-워셜 알고리즘으로 풀이했다.케빈 베이컨의 수가 가장 작으며 그 중 번호가 가장 작은 사람을 출력한다.전체 코드# 1389 : 케빈 베이컨의 6단계 법칙import sysinput = sys.stdin.readlinen, m = map(int, input().rstrip().split())dp = [[float('inf') for _ in range(n)] for _ in range(n)]for i in range(n): dp[i][i] = 0for _ in range(m): a, b = map(int, input().rstrip()...

문제 링크 : https://www.acmicpc.net/problem/1463풀이 과정문제에서 나오는 연산 과정과, 연산을 하고난 뒤의 결과를 그래프로 인식하여 BFS로 풀이했다.탐색을 진행하는 도중 1이 나오면 바로 탐색을 종료하고 탐색 횟수를 출력한다.전체 코드# 1463 : 1로 만들기import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input().rstrip())visited = [False for _ in range(int(1e6)+1)]queue = deque()queue.append(n)visited[n] = Truetime = 0done = Falsewhile queue: size = len(queue)..