Python

이 문제의 핵심은 최소힙을 사용하는 것이었다. 사실 처음엔 배열이나 스택을 활용하려고 했었는데 너무 모르겠어서 구글링 해보니 다들 최소힙으로 푸셨음..ㅎ즉 최소힙의 특성을 기반으로 상위 N개의 큰 숫자만 유지하는 방식을 구현해야 하는 문제였다. 최소힙의 개념부터 복습해보자면,최소 힙은 root node가 항상 가장 작은 값을 가지는 이진 트리이다.파이썬에는 이를 효율적으로 구현할 수 있는 자료구조로 heapq 라이브러리가 이미 존재하는데, 노드 삽입을 위한 heappush와 제거를 위한 heappop 메소드(가장 작은 값인 0번째 원소 제거)가 존재하고 각각 O(log k)의 시간 복잡도를 가진다.동작 방식은 힙에 새로운 숫자를 삽입할 때 내부적으로 힙 구조를 유지하도록 자동으로 정렬이 되는데, 가장 작..

(1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 인 이 범위가 포인트다. 예를 들어 1 1 1에서 시작하여 1씩 증가하다가 15 15 15가 되는 순간 E는 범위 끝에 도달했기 때문에 다음 회차는 1 16 16이 되어 버린다.마찬가지로 이 상태에서 1씩 계속 더 증가하다가 4 19 19 가 되면 이젠 M이 범위 끝에 도달하여 다음 회차는 5 20 1이 되어버리고, 이후 S도 13 28 9가 되면 범위 끝에 도달해서 14 1 10이 되는 구조인 것이다. 이렇게 세 변수가 각각 범위에 맞춰 1로 회귀하는 과정을 반복할 때, 우연히 딱 처음으로 각 범위로 나눈 나머지 값이 0이 되는 시점의 수를 출력하면 이것이 바로 구하고자 하는 년도가 될 것! # (1 ≤ E ≤ 15, 1 ≤ S ≤ 28..

2xn 크기 직사각형을 채우는 방법의 수를 구하는 문제이기 때문에 숫자가 매우 커지게 되므로 10007로 나눈 나머지를 출력해야 한다.피보나치 수열과 비슷한 구조로 해결할 수 있는데, 이 타일링 방법의 규칙을 분석해보면 다음과 같다.  f(n) = f(n-1) + f(n-2) f(n-1) : 2x1 크기의 타일을 세로로 하나 추가한 경우f(n-2) : 1x2 크기의 타일을 두 개 추가한 경우  최소가 n-2 이기 때문에 각각 f(1)과 f(2)의 초깃값을 부여해야 한다.2x1 직사각형을 채우는 방법은 1가지 이므로 f(1) = 1 , 2x2 직사각형을 채우는 방법은 2가지 이므로 f(2) = 2 이다. 따라서 최종적으로 결과는 f(n) % 10007 인 셈! ++ 여기서 굳이 다른 숫자도 아니고 1000..

import sys N, M = map(int, input().split())arr = list(map(int, sys.stdin.readline().split()))for _ in range(M): i, j = map(int, input().split()) print(sum(arr[i-1:j])) 처음에 작성했던 코드이다.예제로 테스트해본 결과 정답은 올바르게 나오지만, 아무래도 합계를 구하는 sum(arr[i - 1 : j]) 부분의 시간 복잡도가 매우 커지는 경우가 있게 되어 시간초과 오류로 틀렸음매번 구간 합을 계산하기 위해 sum(arr[i - 1 : j]) 을 호출하여 M 번의 구간 합을 계산해야 하기 대문이다. 이 문제를 해결하기 위해 찾아보니 구간 합 배열 (누적 합)을 구현, ..

다국어 문제이므로 이해를 위해 예시를 통해 짧게 설명을 해보자면 다음과 같다. N 으로 4가 주어지면 4명의 사람이 있는데, 이들이 각각 1 3 1 4 라는 의미는 각각 자신이 필요한 피자의 갯수이며 피자는 1번 사람부터 순서대로 1초마다 제공된다. 따라서 힌트에 나와있는 것처럼 피자를 받는 사람 번호를 일일이 기록해보면1 2 3 4 2 4 2 4 4 가 되고,여기서 각자 마지막으로 피자를 받은 순간이 피자 수령을 완료한 시점이기 때문에 결과는 1 7 3 9 가 되는 것이다!(각 숫자마자 제일 나중에 나온 인덱스+1 을 결과로 하여 출력하는 셈)  N = int(input())A = list(map(int, input().split())) # 1 3 1 4pizza = {i + 1 : A[i] for i..

스택을 활용하는 문제로, 첨부된 그림에 나타난 것처럼 정식 줄이 있고 그 옆에 임시 저장소 같은 골목길 이렇게 두 공간이 존재하는 상태이기 때문에 스택을 두 개 활용해주면 된다.  접근 방법: 큐와 스택을 활용- 줄 서있는 사람들을 기존의 arr 스택의 앞에서부터 차례대로 꺼내면서, 카운터에 바로 갈 수 없는 사람은 임시 스택 temp에 저장해두는 방식 - 현재 사람들이 가져야 할 번호표가 1번부터 시작해 순차적으로 카운터에 도달해야 한다.- 만약 arr 줄에서 나오는 번호와 번호표가 맞지 않으면 임시 스택 temp에 해당 사람을 보관했다가 나중에 꺼내기!- 이때 temp 스택에서 번호를 확인하는 조건은 맨 위의 번호가 현재 필요한 번호와 일치한다면, 해당 번호의 사람을 꺼내서 카운터로 전달하고 필요한 ..