여행자의 책

배열의 부분합을 구할 떄 사용하는 자료구조 일반적인 for으로 구현하면 N이 리스트의 길이일떄 O(N)의 시간복잡도로 계산 가능하지만 세그먼트 트리를 사용하면 O(logN)으로 가능하다. 초기화 과정 O(logN) 출력 O(logN). 세그먼트 트리는 크게 두가지 함수가 존재한다. 하나는 주어진 정수 리스트를 바탕으로 세그먼트 트리를 만드는 init함수와 만든 세그먼트 트리를 이용해 특정 구간합을 반환하는 query함수이다. 구체적인 구현은 아래와 같다. 세그먼트 트리는 이진 트리로 루트, 왼쪽자식, 오른쪽 자식으로 구성되어있다. 한편 세그먼트 트리를 구성하는 leaf 노드를 제외한 모든 정점의 값은 해당 정점을 중심으로 왼쪽 자식과 오른쪽 자식으로 합이고 리프노드의 자리에는 주어진 정수 리스트의 값이 ..

나이브한 방식의 최소 공통 조상 찾기 def solution(N, tree, v1, v2): level = [0 for i in range(N+1)] parent = [0 for i in range(N+1)] visited = [0 for i in range(N+1)] def dfs(here, depth): visited[here] = True level[here] = depth for there in tree[here]: if not visited[there]: parent[there] = here dfs(there, depth+1) root = 1 #root 1로 가정 dfs(root, 1) def LCA(v1, v2): """ v1, v2의 공통조상을 찾아주는 알고리즘 """ #같은 레벨로 만들어 ..

1. 버블 알고리즘 def buble_sort(arr): N = len(arr) for i in range(N): for j in range(i+1, N): if arr[i] > arr[j]: arr[i], arr[j] = arr[j], arr[i] return arr 2. 병합 정렬 알고리즘 def merge_sort(arr): N = len(arr) if N < 2: return arr mid = N // 2 left, right = arr[:mid], arr[:mid] left_arr = merge_sort[:mid] right_arr = merger_sort[mid:] result = [] l = r = 0 while l < len(left_arr) and h < len(right_arr): if..

1. 상호 배타적 집합과 유니온 파인드 상호 배타적 집합이란 서로간의 교집합이 없는 부분집합을 의미한다. 이를 표현하기 위해 유니온 파인드(Union Find) 라는 자료구조를 사용한다. 상호 배타적 자료구조를 표현하기 위해선 크게 3가지 연산이 필요하다. 1. 초기화(Initialization) : n개의 원소를 n개의 집합에 포함되어 있도록 초기화 2. 합치기(Union) : 두 원소에 대해 이 두 원소가 주어질 때 이들이 속한 두 집합을 하나로 합친다. 3. 찾기(Find) : 임의의 원소가 어떤 집합에 속해 있는지 반환 => 이러한 연산을 클래스로 구현해주면 된다. 2. 구현 다음은 파이썬으로 구현한 Navie한 Union 파인드이다. class NaiveDisjointSet(): parent =..