Dev_Diary

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 걸을 때는 가중치가 1, 순간이동 할 때는 가중치가 0인 트리 구조로 생각하고 다익스트라 알고리즘을 통해 풀면 쉽게 풀 수 있습니다. import heapq def solution(N, K): # 다익스트라 min_time = dijkstra(N, K) return min_time def dijkstra(start, end): # 최대시간 inf = float..

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 임의의 노드(A)에서 가장 멀리있는 노드(B)를 찾는다면 해당 노드(B)는 가장 멀리 떨어진 두 노드중 하나의 노드에 해당하게 됩니다. 그리고 해당 노드(B) 에서 가장 멀리 있는 노드를 찾는다면(C) B 노드와 C 노드는 가장 먼 두 점이 되므로 두 노드 사이의 거리를 출력해주면 됩니다. import heapq import sys def solution(V, data_list):..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 단순하게 모든 경우를 순회하게 되면 최악의 경우 N^2 의 시간 복잡도가 형성되어 큰 인풋에서는 시간초과가 생기게 됩니다. 따라서 순회를 최대한 줄이며 풀어야 하기 때문에 스택을 사용해 데이터 리스트 자체를 변경하며 풀었습니다. [ a, b, c ] 의 데이터가 주어졌을 때 경우의 수를 생각해보겠습니다. a>b, b>c 일 경우에는 a>c 이므로 리스트를 순회하지 않아도 됩니다. a>b, b= next_nu..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 3중 반복문을 기본으로 하는 풀이입니다. i 개의 데이터를 더하고 j 에서 시작하며 k 에서 끊어서 더하는 3중 반복문입니다. [a0, a1, ... , an] 의 전체 데이터를 두고 최소 코스트를 구한다고 가정하겠습니다. 처음으로 2 개의 데이터를 더하는 경우부터 시작해 n+1 개의 데이터를 더하는 경우까지 확장합니다. 처음 시작하는 데이터의 인덱스는 0부터 n+1-i 까지 입니다. 끊..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 절댓값을 비교해야 하기 때문에 최댓값 혹은 최솟값만을 찾을 수 있는 단일 힙으로는 구현이 힘들 것 같아 음수와 양수를 각각 담당하는 힙을 만들어 풀었습니다. import sys import heapq def solution(N, data_list): # 최대힙, 최소힙 max_heap = [] min_heap = [] # 음수는 최대힙에 넣고 양수는 최소힙에 넣음 for da..

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net heapq 가 최소힙이라는걸 감안하고 입출력시 -1 을 곱해주면 쉽게 풀 수 있습니다. import heapq import sys def solution(N, data_list): # 큐 hq = [] # 순차적으로 진행 for data in data_list: # 0 이면 if not data: # 큐가 비어있으면 if not hq: print(0) # 아니면 else: ..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합을 사용하되 수학적 방법을 조금 사용해야 하는 문제입니다. mod 계산, 나머지 계산은 선형성을 띄기때문에 여타 계산 전에 나머지를 구하고 계산을 해도 여전히 나머지는 동일합니다. 즉 미리 누적합에 대해 나머지를 구한 뒤 나머지를 기준으로 리스트를 만들고 나머지를 사용해 콤비네이션 연산을 진행했습니다. 처음에는 itertools 의 combin..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문자열의 길이가 길다보니 일반적으로 탐색하면 시간초과가 걸립니다. 입력된 문자가 폭발하는 문자열의 마지막 문자인지 파악하고 마지막 문자열이 폭발하는 문자열인지 판단했습니다. import sys def solution(str_data, target_str): # 스택 stack = [] # 스택에 한 글자씩 입력 for string in str_data: stack.append(str..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀적으로 접근하면 문제를 쉽게 풀 수 있습니다. def solution(N, data_list): # 카운트 global white global blue white = 0 blue = 0 # 재귀함수 호출 split_paper(data_list, [0, N], [0, N]) print(white) print(blue) # 구간을 쪼개는 함수 def split_paper..

https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 입력의 크기가 커서 100점 맞기가 어려운 문제였습니다. 단순히 순회하면 시간초과가 생기므로 누적합 리스트를 만들어 풀어야합니다. 문자별로 누적합 리스트를 만들어 풀었습니다. import sys from collections import defaultdict def solution(S, data_list): # 문자별 누적합 subsum = [[0..