공작소

문제 링크 : https://www.acmicpc.net/problem/2263# 2263 : 트리의 순회import syssys.setrecursionlimit(int(1e5))input = sys.stdin.readlinen = int(input().rstrip())inorder = list(map(int, input().rstrip().split()))poorder = list(map(int, input().rstrip().split()))# 중위 순회가 주어지고# 후위 순회가 주어졌을 때# 전위 순회를 구해라.# 1. 요소를 하나씩 잡고, 그 요소가 다른 배열에 등장할 때까지를 구간으로 나누고,# [ 루트 ] - left - [ 루트 ] - left - [ 루트 ] 로 잡는다.# 2. 분할했..

문제 링크 : 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()...