HTD

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net import sys input = sys.stdin.readline def getMinTimeToCatch(N, K): todo = [(N, 0)] isVisited = [False]*100001 isVisited[N] = True while todo: x, t = todo.pop(0) isVisited[x] = True if x == K: break if x-1..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net import sys sys.setrecursionlimit(500000) input = sys.stdin.readline def printPreorder(inorderStartIndex, inorderEndIndex, postorderStartIndex, postorderEndIndex): length = inorderEndIndex - inorderStartIndex if length == 0: return elif length..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys input = sys.stdin.readline def setUnattackableCountRecursively(index): if index == N-1: for i in range(N): if isAvailable[i][index] == 0: global unattackableCount unattackableCount += 1 else: for i in range(N): if isAvail..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net import sys input = sys.stdin.readline def getPriorty(c): if c >= 'A' and c priority: stack.append(c) else: # 우선순위가 더 높은 스택들을 모두 꺼냄 while stack and stack[-1] != '(' and getPriorty(stack[-1])

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 문제를 분석해보면, 전형적인 냅색 문제이다. 아래 사진을 보자. 각 열은, 해당 물건을 필수적으로 가져간다고 했을 때의 총 가치를 나타낸다. 점화식은 아래와 같다. DP[i][j] = DP[i][j-1] 또는 (현재 물건의 가치) + DP[0~i-1][j-(현재 물건의 무게)]의 최댓값 즉, dp[2][7]을 구할 때, 위의 사진과..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net import sys input = sys.stdin.readline def getMaxScore(stickers, n): for j in range(n): for i in range(2): if j == 0: continue elif j == 1: stickers[i][j] += stickers[(i+1) % 2][j-1] else: stickers[i][j] += max( sticke..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net import sys input = sys.stdin.readline INF = 1000000000 def bellmanFord(): global isAvailable for i in range(1, n+1): for j in range(1, n+1): for target, wasted in info[j]: if dp[target] > wasted + dp[j]: dp[target] =..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline def getRemainderRecursively(curB): if curB == 1: return a % c halfRemainder = getRemainderRecursively(curB//2) toReturn = halfRemainder*halfRemainder if curB % 2 != 0: toReturn *= a return toReturn % c if __name__ == '__ma..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net import sys input = sys.stdin.readline def setDistances(node): global distances for n, d in tree[node]: if distances[n] == -1: distances[n] = distances[node] + d setDistances(n) if __name__ == '__main__': V = int(in..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net import sys input = sys.stdin.readline def getParents(tree, N): parents = [-1 for _ in range(N+1)] todo = [1] while todo: cur = todo.pop(0) for node in tree[cur]: if parents[node] == -1: todo.append(node) parents[node] = cur return parents if __name__ == '__ma..