Dev_Diary

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 워셜 알고리즘을 익히는 알고리즘 문제입니다. import sys def solution(n, data_list): # 최대 거리 inf = float('inf') # 거리 맵 구성, [i][j] 는 i 에서 j 로 가는 최단 거리 dist_map = [[inf for _ in range(n+1)] for __ in range(n+1)] # 데이터 거리 맵에 입력 for start, end..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 간선 중 음의 가중치를 지닌 간선이 있기 때문에 최단거리 알고리즘 중 벨만-포드 알고리즘을 사용해야 합니다. 벨만 포드 알고리즘은 모든 노드를 돌아다니며 이어진 간선을 최신화 해주는 알고리즘으로 조금 비효율적인 다익스트라로 보일 수 있지만 모든 노드를 돌아다니며 최적화해주는 특성 탓에 음의 간선이 포함되어 있어도 해를 찾을 수 있다는 장..

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..