문제 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으로 나눈 나머지 값을 가지고 활용..

개념 특정 배열이 있을 때, 구간의 합을 말한다. 예를 들어, 다음과 같은 배열이 있을 때 3번째부터 5번째까지의 누적합은 12이다. 구현 일반적으로 누적합을 구함에 있어, i번째부터 j번째까지의 누적합을 구하라고 할 때마다 하나씩 더하면 i~j까지를 m개의 원소라고 하면 시간 복잡도가 m(j-i+1)의 제곱으로 늘어난다. 하지만 간단한 개념을 도입하면 시간복잡도를 O(2)까지 줄일 수 있다. 전체 누적합을 구한다. i번째부터 j번째까지 누적합을 구하려면 전체 누적합의 j번째 인덱스에서 i-1번째 인덱스를 빼면 된다. 응용 자료구조 응용 세그먼트 트리 2042 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N..

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/9935 이해 문자열을 완전 탐색을 통해 더했다가 뺐다가 할 수 있지만, 최대 길이가 1,000,000 이므로 뺄때, 붙일 때 길이만큼 탐색하고, 제거/더해줌 반복되므로 시간 초과가 날 수 있음 Stack 구조의 append/pop 연산을 통해 중복되는 반복을 제거하고, 최대 폭발 문자열의 길이만큼만 반복하게 하여 시간을 줄일 수 있음 구현 Stack으로 이용할 리스트 생성 Stack에 문자열 하나씩 저장하며, 길이가 폭발 문자열 길이 보다 길어졌을 때부터 폭발 문자열이 stack 내부에 있는지 확인 → 마지막 길이만큼만 확인하면 모두를 확인할 수 있음 만약 폭발 문자열이 있다면 pop 연산을 통해 제거 없다면 계속해서 append 연산을 통해 S..

https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 이해 문자열 탐색을 통한 완전탐색 구현 문제 해당 단어를 탐색하여 개수를 센 후, 이를 비교해도 시간이 충분하다.(O(1,000,000)) 구현 각 단어별 구성하고 있는 단어와 그 개수를 저장할 dictionary 생성(편의를 위한 defaultdict 사용) 단어별 구성 단어와 개수를 저장 단어별 구성 단어 개수에서 기준 단어 구성 단어의 개수를 빼서 개수를 재구성(아래와 같이 표현) 해당 단..

https://www.acmicpc.net/problem/15684 이해 사다리를 모두 놓아보면서 판별해야하는 문제 DFS 를 통해 완전 탐색을 하되, 중간 가지치기를 이용한 시간을 단축해야함 구현 사다리 타기를 통해 i → i 가 모두 가능한 지 체크 하는 함수 DFS를 통해 사다리를 놓는 경로를 모두 탐색해야하는 함수 사다리 조작에 있어 사다리를 추가할 때, 추가한 사다리가 3개가 초과되면 가지치기 만약 이전에 확인된 사다리의 조작한 사다리 수가 현재 돌고 있는 사다리의 조작한 사다리 수 보다 높은 경우 가지치기 사다리를 놓음에 있어 만약 2개 혹은 3개째 사다리를 놓을 때는 이전에 놓았던 사다리 위치보다 위에 놓을 필요가 없음 코드 # 15684 사다리 조작 import sys input = sys..