HTD

https://www.acmicpc.net/problem/13925 13925번: 수열과 쿼리 13 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 x y v: Ai = (Ai + v) % MOD를 수행한다. (x ≤ i ≤ y) 2 x y v: Ai = (Ai × v) % MOD를 수행한다. (x ≤ i ≤ y www.acmicpc.net 이 글은 Segment Tree의 Lazy Propagation을 알고 있다는 가정 하에 작성하였다. 자세한 사항은 아래 링크를 참고하자. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%8..

https://www.acmicpc.net/problem/2162 2162번: 선분 그룹 첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하 www.acmicpc.net import sys input = sys.stdin.readline def ccw(x1, y1, x2, y2, x3, y3): return (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) def is_two_lines_intersecting(line1, line2): x1, y1, x2, y2 = line1 x3, y3, x4, y4 = line2 m..

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net import sys input = sys.stdin.readline if __name__ == '__main__': T = int(input()) n = int(input()) A = list(map(int, input().split())) m = int(input()) B = list(map(int, input()...

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net import sys input = sys.stdin.readline def dfs(puttables, index, count): # Base case if index == len(puttables): global max_count max_count = max(max_count, count) return # Recursive case x, y = puttables[index] nx, ny = new_posi..

https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 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 keyword[i] != keyword[j] and j > 0: j = pi[j-1] if keyword[i]..

https://www.acmicpc.net/problem/9202 9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net import sys input = sys.stdin.readline dx = [-1, -1, -1, 0, 1, 1, 1, 0] dy = [-1, 0, 1, 1, 1, 0, -1, -1] POINTS = [0, 0, 0, 1, 1, 2, 3, 5, 11] LENGTH = 4 class Node: def __init__(self): self.children = {} self.is_e..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬에 단지 우선순위큐를 사용한 문제이다. 위상 정렬은 아래 글에 설명되어있다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-2623%EB%B2%88-%EC%9D%8C%EC%95%85%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%A8 [Python] 백준 2623번: 음악프로그램 https..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net import sys input = sys.stdin.readline def solution(): primes = get_prime_numbers() # Two pointers count = 0 primes_length = len(primes) start = 0 cur_sum = 0 for i in range(primes_length): # 현재 값을 추가 cur_sum += primes[i] # N 이하가 될 때까지 감소시킴 while cur_sum > N: cur_sum -= primes[start] start +..

https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net Segment Tree의 응용인 Lazy propagation의 응용 문제이다. Lazy propagation의 상세한 설명은 아래 링크에 담겨있다. https://rccode.tistory.com/entry/Python-%EB%B0%B1%EC%A4%80-10999%EB%B2%88-%EA%B5%AC%EA%B0%84-%ED%95%A9-%EA%B5%AC%ED%9..

https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net import sys input = sys.stdin.readline class Node(): def __init__(self, key): self.key = key self.children = {} class Trie: def __init__(self): self.head = Node(None) def insert(self, strings): current_node = self.he..