크루스칼 알고리즘 크루스칼 알고리즘은 최소 스패닝 트리를 구현하는 알고리즘 중 한 가지 방법이다. 크루스칼 알고리즘은 간선의 가중치를 확인해서 그리디하게 간선을 선택해서 최소 스패닝 트리를 구현한다. 간선의 가중치를 오름차순으로 정렬해 간선을 하나씩 추가하는 방법, 내림차순으로 정렬해 필요없는 간선을 하나씩 제거하는 방법도 있다. 그리디한 방법은 순간의 최적해를 찾을 수는 있지만, 크게 봤을 때 정해가 되는지는 증명이 필요하다. 크루스칼 알고리즘은 이미 저명한 학자들에 의해서 그 타당성을 인정 받았기 때문에 받아들이기만 하면 된다고 한다. 간선의 가중치를 오름차순으로 정렬해 필요한 간선을 하나씩 추가하는 방법은 다음과 같다. 간선의 가중치를 기준으로 정렬한다. (퀵정렬, 병합정렬 사용) 가중치가 낮은 간..
import sys n,k = map(int,sys.stdin.readline().split()) my_list = list(map(int,sys.stdin.readline().split())) pre_fix = [0 for _ in range(n+1)] for i in range(0,n) : pre_fix[i+1] = pre_fix[i] + my_list[i] answer = -9876543210 for i in range(n+1) : if i+k < n+1 : answer = max(answer, pre_fix[i+k] - pre_fix[i]) print(answer) 부족했던 부분 누적합을 구할 때, 앞에 여유 칸 없이 Prefix 배열을 만들었다. 이런 이유로 Prefix의 첫번째를 빼게 되면 항..
import sys n = int(sys.stdin.readline().rstrip()) my_list = list(map(int, sys.stdin.readline().split())) s = [0 for _ in range(n + 1)] for i in range(1, n + 1): s[i] = s[i - 1] + my_list[i - 1] answer = 0 for k in range(2, n): temp = (s[k] - s[1]) + (s[-2] - s[k - 1]) answer = max(answer, temp) for k in range(2, n): temp = (s[-2] - s[k]) + 2 * (s[k - 1] - s[0]) answer = max(answer, temp) for k i..
이번 포스팅에서는 중요한 자료구조인 큐와 덱에 대해 정리를 하려고 한다. 단, 이 게시글은 비전공자가 따로 공부하고 정리한 내용이기 때문에 틀린 내용이 있을 수 있다. 큐(Que)란? 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조를 가리킨다. 실생활에서 가장 보기 쉬운 형태의 자료구조이며, 간단한 예로는 줄 서는 것을 볼 수 있다. 지하철에서 먼저 줄을 서는 사람이 먼저 타는 것처럼 먼저 들어온 데이터가 먼저 나가는 형식의 자료구조로 보면 된다. 배열기반 큐 구현1( Two Pointer) 큐는 데이터의 가장 앞부분을 알려주는 First Index, 가장 뒷부분을 알려주는 Last Index가 있다. 이 두 Index의 이동을 이용해서 큐를 구현한다. 그렇다면 큐에서 각 쿼리가 발생했을 때, 이 Ind..
누적합(Prefix)는 언제쓰지? 누적합은 특정 수열이 주어지고, 그 수열에서 특정 구간의 값을 구하라는 쿼리가 반복적으로 들어올 때 주로 사용하게 되는 개념이다. 예를 들어 길이 n의 수열이 주어졌을 때, [0, n-1] 구간의 합이 얼마인지를 확인하라는 반복적인 쿼리가 들어올 수 있다. 이 때, [0, n-1] 구간의 합을 확인하는데 필요한 시간복잡도는 O(N)이다. 이런 쿼리가 한번만 들어오면 크게 문제는 없지만, 대부분 이런 경우는 쿼리가 반복적으로 들어온다. 이 경우, 최악의 경우 주어진 쿼리를 다 처리하는데 필요한 시간복잡도는 O(N^2)이 된다. 이 시간복잡도를 O(N)으로 처리하기 위해 필요한 개념이 누적합이다. 수열에 주어진 정보의 각각 구간의 누적합을 찾아내고, 그 값을 배열로 관리한다..