크루스칼 알고리즘 크루스칼 알고리즘은 최소 스패닝 트리를 구현하는 알고리즘 중 한 가지 방법이다. 크루스칼 알고리즘은 간선의 가중치를 확인해서 그리디하게 간선을 선택해서 최소 스패닝 트리를 구현한다. 간선의 가중치를 오름차순으로 정렬해 간선을 하나씩 추가하는 방법, 내림차순으로 정렬해 필요없는 간선을 하나씩 제거하는 방법도 있다. 그리디한 방법은 순간의 최적해를 찾을 수는 있지만, 크게 봤을 때 정해가 되는지는 증명이 필요하다. 크루스칼 알고리즘은 이미 저명한 학자들에 의해서 그 타당성을 인정 받았기 때문에 받아들이기만 하면 된다고 한다. 간선의 가중치를 오름차순으로 정렬해 필요한 간선을 하나씩 추가하는 방법은 다음과 같다. 간선의 가중치를 기준으로 정렬한다. (퀵정렬, 병합정렬 사용) 가중치가 낮은 간..
누적합(Prefix)는 언제쓰지? 누적합은 특정 수열이 주어지고, 그 수열에서 특정 구간의 값을 구하라는 쿼리가 반복적으로 들어올 때 주로 사용하게 되는 개념이다. 예를 들어 길이 n의 수열이 주어졌을 때, [0, n-1] 구간의 합이 얼마인지를 확인하라는 반복적인 쿼리가 들어올 수 있다. 이 때, [0, n-1] 구간의 합을 확인하는데 필요한 시간복잡도는 O(N)이다. 이런 쿼리가 한번만 들어오면 크게 문제는 없지만, 대부분 이런 경우는 쿼리가 반복적으로 들어온다. 이 경우, 최악의 경우 주어진 쿼리를 다 처리하는데 필요한 시간복잡도는 O(N^2)이 된다. 이 시간복잡도를 O(N)으로 처리하기 위해 필요한 개념이 누적합이다. 수열에 주어진 정보의 각각 구간의 누적합을 찾아내고, 그 값을 배열로 관리한다..
1. 스케쥴링 - 가장 먼저 있는 것을 처리하는 경우 - 뒤에 있는 것부터 처리하는 경우 - 스케쥴이 짧은 것을 먼저 처리하는 경우 - 스케쥴이 짧고 빠르게 오는 것을 먼저 처리하는 경우.
Colletions의 Defaultdict 라이브러리 Collection에는 Defaultdict 라이브러리가 있다. Defaultdict 라이브러리는 딕셔너리를 선언했을 때, 기본적으로 가지게 될 값을 지정해주는 라이브러리다. 예를 들어, 아래의 값은 무조건 에러가 발생한다. 이유는 A[char]에 대한 초기값이 설정이 되지 않았기 때문이다. A = {] for char in 'abcdefghijklmnopqrstuvwxyz' : A[char] +=1 위의 경우를 최소화 해주기 위해 Defaultdict 라이브러리가 존재한다. 아래의 예시는 a라는 딕셔너리에 기본 자료형이 int인 값을 넣어준다. from collections import defaultdict a = defaultdict(int) fo..
구현 전, 알아두어야 할 것 Lower Bound 및 Upper Bound는 모두 경계값을 찾는 함수다. 이 함수는 반드시 정렬이 된 값들에서만 사용할 수 있다. Lower Bound 파이썬 코드 구현 : O(logn) Lower Bound는 찾고자 하는 값이 가장 처음으로 나오는 위치를 찾는 함수다. 예를 들어, 4를 찾는다면 4가 가장 처음으로 나오는 위치를 찾는 함수다. 아래 표를 예시로 들 경우, Index는 6이 정답이 된다. Index 0 1 2 3 4 5 6 7 8 Value 1 1 1 2 2 3 4 4 4 Lower Bound 함수를 구현할 때, 나는 다음과 같이 구현했다. 1. 이진 검색을 기준으로 값을 찾는다. (logn의 시간복잡도 구현) 2. 이진 검색 시, 다음과 같은 로직으로 접..