낙서 코딩

개념

말 그대로 구간의 누적의 합을 구하는 알고리즘이다. 배열에 값을 저장하고 하나씩 더해가는 방식은 O(n^2)의 시간 복잡도를 갖는다. 하지만 누적합 알고리즘을 사용한다면 O(n)으로 시간복잡도를 줄일 수 있다. 보통 누적합은 부분 합을 구하기 위해서 사용하는데 만약 a부터 b까지의 합을 구한다고 하면 먼저 누적합을 만들고, b번째 요소에서 a-1번째 요소를 빼주면 구할 수 있다.

사용 하면 좋은 경우

1. 리스트에 일정 구간의 값의 합을 구할 때
2. 리스트에 일정 구간에 값을 넣어야 할 경우(시작과 끝 부분에 값 넣어놓고 누적합)

사용 방법

1. 구간의 합 구하기

import itertools

a = [3,2,1,6,8,4]
result = list(itertools.accumulate(a))

print(result)

🖨️ [3, 5, 6, 12, 20, 24]

1. 부분 합 구하기

import itertools

a = [3,2,1,6,8,4]
start = 3
end = 5
acc = list(itertools.accumulate(a))

result = acc[end] - acc[start-1]

🖨️ 18

누적합을 우선 구한 후 마지막 부분의 누적합 값에서 시작부분 전의 누적합을 빼서 부분 합을 구할 수 있다,

시간 복잡도

• O(N)

개념

그룹을 지을 때 사용할 수 있는 알고리즘이다. 처음에 자기 자신을 부모로 설정하고 조건에 따라 부모를 설정한다. Find는 자신의 최상위 부모를 찾는 역할을 한다. Union은 두 변수의 부모가 다르다면 하나의 최상위 부모를 다른 하나의 최상위 부모의 자식으로 만들어 두개의 그룹이 합쳐지는 기능을 수행한다.

• Union by Rank : 트리가 균형이 맞도록 한다. 각 집합에 대해 이 집합을 나타내는 트리의 높이를 rank 변수에 저장한다. 그리고 두 집합을 합칠 때 rank가 작은 집합을 rank가 큰 집합 아래에 붙힌다.
• Path Compression : 경로 압축(path compression)은 find 과정 가운데 경로 상의 모든 점들을 곧바로 루트 정점에 연결하는 방법이다. 이렇게 하면 위 그림과 같은 구조로 시간 복잡도가 훨씬 줄어들게 된다.

조건

• Cycle 구조가 생기면 안된다. 따라서 Union은 서로의 부모가 다를때만 해야한다.

사용하기 좋은 경우

1. 서로 중복되지 않는 부분 집합들로 나눌 때
2. 그룹의 수를 구할 때

구현 방법

1. Find

parent = [x for x in range(10)] # 자기 자신이 부모로 초기화

def find_parent(x, parent):
	if parent[x] == x: # x가 최상위 부모
			return x
	#x의 부모중 최상위 부모 찾기
	parent[x] = find_parent(parent[x], parent)
	return parent[x]

1. Union

def union_parent(a, b, parent):
	pa = find_parent(a)
	pb = find_parent(b)
	if pa == pb :
		pass
	elif pa < pb : # 더 큰애가 부모가 되게 설정
		parent[pa] = pb
	else:
		parent[pb] = pa

시간 복잡도

• O(M)+O(Mlog⋆N)+O(Nlog⋆N)=O((M+N)log⋆N)
• (M : find 연산 수, N : 트리가 바뀌는 횟수)