HTD

https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net import sys import math input = sys.stdin.readline def getTreeLength(): # 2의 제곱꼴인지 확인 if N & (N - 1) == 0: return 2*N - 1 else: return pow(2, math.ceil(math.log(N, 2)) + 1) - 1 def initializeSegmentT..

https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net import sys input = sys.stdin.readline def initializeSegmentTree(index, start, end): if start == end: tree[index] = (nums[start], nums[start]) return mid = (start + end)//2 initializeSegmentTree(index*2,..

https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import sys input = sys.stdin.readline DIV = 1000000007 def initializeSegmentTree(index, start, end): if start == end: tree[index] = nums[start] else: mid = (start + end)//2 tree[index] = i..

https://www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def solution(): ccw123 = ccw(x1, y1, x2, y2, x3, y3) ccw124 = ccw(x1, y1, x2, y2, x4, y4) ccw341 = ccw(x3, y3, x4, y4, x1, y1) ccw342 = ccw(x3, y3, x4, y4, x2, y2) # 평행 if ccw123*ccw124 == 0 and ccw341*ccw342 == 0: if mx1

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net import sys input = sys.stdin.readline def setDp(start): todo = [start] dp[start] = (0, 0) while todo: cur = todo.pop(0) if cur == 1: break if cur % 3 == 0 and dp[cur//3][0] > dp[cur][0] + 1: dp[cur//3] = (dp[cur][0] + 1, cur) todo.append(cur//3) if cur % 2 == 0 and dp[cur//2][0] > d..

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net import sys import bisect input = sys.stdin.readline sys.setrecursionlimit(1000000) if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) stack = [] stackLength = 0 # stack에서의 인덱..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net import sys import bisect input = sys.stdin.readline if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) stack = [] for n in nums: minBiggerIndex = bisect.bisect_left(stack, n) if minBiggerInde..

https://www.acmicpc.net/problem/11049 import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) nums = list(map(int, input().split())) for _ in range(N-1): _, c = map(int, input().split()) nums.append(c) # DP dp = [[0]*N for _ in range(N)] for d in range(N): for i in range(N - d): j = i + d if i == j: continue dp[i][j] = float('inf') for k in range(i, j): dp[i][j] = min(d..

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net import sys sys.setrecursionlimit(300000) input = sys.stdin.readline def search(node): stack.append(node) visitInfo[node] = curSearchStart next = nums[node] nextVisitInfo = visitInfo[next] # 이번 탐색 때 방문한 경우 if nextVisitInfo == c..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net import sys import copy input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def getCyclePositions(): airCleanerTopX = -1 airCleanerBottomX = -1 for i in range(R): if fineDusts[i][0] == -1: airCleanerTopX = i ai..