도비의 기술부채 인력소

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net [문제] [코드] from collections import deque n , k = map(int, input().split()) visited = [0] * 100001 def bfs(): q = deque() q.append(n) while q: now = q.popleft() if now == k: return visited[now] for next_to in [now*2, now-1, now+1]: if 0

1806번: 부분합 첫째 줄에 N (10 ≤ N = s: result = min(result, end-start) total -= number[start..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net [문제] [코드] import sys input = sys.stdin.readline N = int(input()) solution = sorted(list(map(int, input().split()))) ##투포인터 start = 0 end = N-1 target = abs(solution[0] + solution[-1])#절대값 -> 0까지 거리 result = [solution[0], solution[-1]] #초기값 설..

1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net [문제] [코드] import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) tree = [[] for _ in range(n+1)] #indexing을 위해서 +1사이즈로 구성 #두노드 사이 거리를 구하는 bfs def bfs(a, b): q = deque() q.append((a, 0)) visited = [False] * (n+1) visited[a] = True while q: s..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net [문제] [코드] #중위 순회 문제 #순서가 주어지고 트리를 유추하는 문제 import sys input = sys.stdin.readline k = int(input()) squence = list(map(int, input().split())) trees = [[] for _ in range(k)] #완전 이진 트리이니까 각 층의 노드는 중간의 값 def binary_tree(array, depth): mid_index = len(a..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net [문제] [코드] import sys input = sys.stdin.readline N = int(input().strip()) #Dic 활용 해서 노드 구성 Tree = {} for i in range(N): node, left, right = input().strip().split() Tree[node] = [left, right] #input값 출력 print(Tree) ##전위 중위 후위 함수로 구현 def preorder(node): #전위..

1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net [문제] [코드] import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline n, m = map(int, input().split()) parent = [i for i in range(n + 1)] def find_parent(x): if parent[x] != x: parent[x] = find_parent(parent[x]) return parent[x]..

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net [문제] [코드] import sys input = sys.stdin.readline reference = {} N = int(input()) words = [] for _ in range(N): word = input().rstrip() words.append(word) for j in range(len(word)): if word[j] in reference: reference[word[j]] += 10 **(len(word)-j-1) else: ref..

1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net [문제] [코드] from itertools import combinations N = int(input()) result = [] for i in range(1, 11): for temp in combinations(range(0, 10), i): temp = list(temp) temp.sort(reverse=True) result.append(int("".join(map(str, temp)))) result.sort() try: print(r..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제] [코드] N = int(input()) dp = [[0]*10 for _ in range(N+1)] for i in range(1, 10): dp[1][i] = 1 for i in range(2, N+1): for j in range(10): if j ==0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] print(sum(dp[N]) % 1000000000) [해설] 다이나믹 프로그래밍 문제이다 문제의 핵심 간단하다 아래의 그림을 참..