Hanbit the Developer

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N = S: minLength = min(minLength, end-start) curSum -= nums[start] start += 1 elif ..

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net import sys import itertools input = sys.stdin.readline def setValidSetCount(): global validSetCount leftSums = [] for i in range(N//2 + 1): for s in itertools.combinations(nums[:N//2], i): leftSums.app..

https://www.acmicpc.net/problem/1197 import sys input = sys.stdin.readline def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x, y = find(x), find(y) if x < y: parents[y] = x else: parents[x] = y def getMinSpanningTreeWeight(): minSpanningTreeWeight = 0 for a, b, c in vertices: if find(a) != find(b): union(a, b) minSpanningTreeWeight += c r..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys input = sys.stdin.readline INF = 100001 def floydWarshall(n): dp = [[INF*100]*(n+1) for _ in range(n+1)] # 초기화 for i in range(1, n+1): for j in range(1, n+1): if graph[i][j] != INF: dp[i][j] = graph[i][j] # 플로이드 ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net import sys input = sys.stdin.readline def getFarthestNodeAndPrefixWeight(start, n): todo = [(start, 0)] isVisited = [False]*(n+1) farthestNode = start maxWeight = 0 while todo: node, weight = todo.pop(0) isVisite..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys sys.setrecursionlimit(100000) input = sys.stdin.readline fibonacci = {0: 0, 1: 1, 2: 1} def getFibonacci(n): if not fibonacci.get(n): if n % 2 == 1: fibonacci[n] = (getFibonacci((n+1)//2)**2 + getFibonacci((n+1)//2-1)**2) % 1000000007 else: fibonacci[n] = ..

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])