문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이해 구간의 합을 구해야하는 문제이므로 누적 합 알고리즘을 활용한다. N의 범위가 100,000이므로 O(N)만큼 활용할 수 있고, 탐색을 통해 선택해야 하므로 이분 탐색이나 투포인터를 활용해야한다. 배열 값의 범위가 1,000,000,000이므로 이를 매번 다루면 연산 시간으로 인해 시간 초과가 염려되니, M으로 나눈 나머지 값을 가지고 활용..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이해 우선순위 큐를 이용하여 풀 수 있는 문제 파이썬 내장함수인 Heapq를 사용하면 간단하게 풀 수 있지만, 직접 구현해봄 구현 내장함수 사용 import heapq 를 사용하여 절댓값과 실값을 같이 저장하여 비교하여 사용 직접 구현 class를 통해 실 값을 저장하면 절댓값을 기준으로 비교하여 트리를 구성 코드 # 11286 절댓값 힙 import sys input = s..

https://www.acmicpc.net/problem/18111 이해 평탄화가 가능한 높이에 대해 모든 경우의 수를 비교해가며 풀어야하는 문제이다. 문제를 읽어보면 알 수 있 듯, 높이에 대한 인덱스가 중요하지 않아 2차원 배열이 아닌 1차원 배열로 입력을 받아도 되고, Dictionary 형태로 받아도 된다. 구현 N*M 행렬을 높이에 대한 Dictionary로 정의 collections 내부 defaultdict를 활용 높이에 대해 쌓을 블럭 수와 부술 블럭 수를 따로 저장하여 계산 식으로 풀이 만들 수 있는가? 👉 (부술 블럭 수) + (최초 인벤토리 블럭 수) >= (쌓는 블럭 수) 걸리는 시간 👉 (부술 블럭 수) + 2 * (쌓는 블럭 수) 걸리는 최소 시간 저장 및 최소 시간 중복 시 최..