HTD

https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Lazy Propagation을 통해, query, update 동작을 O(logN)으로 수행하여 이 문제를 해결한다. 이 글은 기본적인 Segment Tree를 알고 있다는 가정하에 설명한 것이다. 먼저, get_tree_length() 함수를 통해 적절한 길이를 얻고, 트리, lazy를 초기화 시킨다. 만약 N이 2의 제곱꼴이라..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include typedef struct Node { int val; struct Node *next; } Node; // Get minNode whose next node is min in linked list Node *getMinNode(Node *header, int length) { Node *cur = header; Node *minNode = cur; for (int i = ..

https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': N, M, K = map(int, input().split()) # Set counts counts = [[1]*(M+1) for _ in range(N+1)] for i in range(1, N+1): for j in range(1, M+1): counts[i][j] = counts[i-1][j] + counts[i][j-1] ..

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net import sys input = sys.stdin.readline MOD = 1000000000 MAX = (1

https://www.acmicpc.net/problem/7575 7575번: 바이러스 첫 번째 줄에는 감염된 프로그램의 개수 N 과 바이러스 코드 추정을 위한 최소 길이를 나타내는 정수 K 가 주어진다. 단, 2 ≤ N ≤ 100이고, 4 ≤ K ≤ 1,000이다. 두 번째 줄부터 각 프로그램에 대한 www.acmicpc.net import sys input = sys.stdin.readline def get_pi(keyword): keyword_length = len(keyword) pi = [0]*keyword_length j = 0 for i in range(1, keyword_length): while j > 0 and keyword[i] != keyword[j]: j = pi[j-1] if k..

https://www.acmicpc.net/problem/3356 3356번: 라디오 전송 첫째 줄에 S의 길이 L이 주어진다. 둘째 줄에는 길이가 L인 S가 주어진다. 메시지는 알파벳 소문자로만 이루어져 있다. (1 ≤ L ≤ 1,000,000) www.acmicpc.net import sys input = sys.stdin.readline def get_pi(string): string_length = len(string) pi = [0]*string_length j = 0 for i in range(1, string_length): while j > 0 and string[i] != string[j]: j = pi[j-1] if string[i] == string[j]: j += 1 pi[i] = ..

https://www.acmicpc.net/problem/2533 import sys sys.setrecursionlimit(300000) input = sys.stdin.readline TRUE, FALSE = 1, 0 INF = 1000001 def dfs(is_early_adapter, node, prev): # If dp already exists if dp[is_early_adapter][node] != INF: return adapter_count = is_early_adapter if is_early_adapter == TRUE: for n in graph[node]: if n == prev: continue dfs(TRUE, n, node) dfs(FALSE, n, node) adapter..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 먼저, 예시 입력 1의 전깃줄을 정렬하면 다음과 같다. 1 8 2 2 3 9 4 1 6 4 7 6 9 7 10 10 여기서 전깃줄이 안 꼬인다는 것은, 계속해서 값이 커져야만 한다. 즉, 가장 긴 증가하는 부분 수열을 구한다. O(NlogN)으로 가장 긴 증가하는 부분 수열을 구하는 것은 아래 링크에 설명되어있다. https://rccode.tistory.com/entry/14003 [Pyth..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': N = int(input()) costs = [0]*(N+1) for i in range(1, N+1): cur_input = list(map(int, input().split())) prev_max_time = 0 for j in range(2, 2 + cur_input[..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': n, m = map(int, input().split()) nums = [[0]*(m+1)] + [[0] + [int(c) for c in str(input().rstrip())] for _ in range(n)] dp = [[0]*(m+1) for _ in range(n+1)] max_length = 0 for i in range(1, n+1): fo..