728x90 ALGORITHM/개념 정리15 [Algorithm] Pregix Sum (누적합, 구간합) 누적합, 구간합 배열의 일부 구간에 대한 합을 빠르게 구할 수 있음 N개의 원소의 합을 구하는 경우 완전 탐색으로 구하면 O(N) 구간합으로 구하면 O(1) 1차원 배열 sum이라는 리스트를 만들어서 sum[i]에 arr[0] ~ arr[i-1] 의 합을 저장 0 부터 i 까지의 합을 구하고 싶은 경우 : sum[i+1] i 부터 j 까지의 합을 구하고 싶은 경우 : sum[j+1] - sum[i] 2차원 배열 sum이라는 리스트를 만들어서 sum[i][j]에 arr[0][0] ~ arr[i-1][j-1] 의 합을 저장 (0, 0) 부터 (i, j) 까지의 합을 구하고 싶은 경우 : sum[i+1][j+1] sum 리스트를 만드는 방법? # arr는 n*n 배열 # 1. 행단위로 더하고 열단위로 더하기 .. 2022. 9. 19. [Algorithm] 다익스트라(dijkstra) 알고리즘 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지 최단 경로 다익스트라 알고리즘 : 음의 가중치 허용x 벨만-포드 알고리즘 : 음의 가중치 허용 모든 정점들에 대한 최단 경로 플로이드 워샬 알고리즘 다익스트라(dijkstra) 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해나가면서 최단 경로 구함 탐욕 기법 사용, MST의 프림 알고리즘과 유사 def dijkstra(start): distance[start] = 0 # 노드의 개수만큼 반복 for _ in range(N+1): min_idx = -1 min_value = float('inf') for i in range(N+1): if not visit.. 2021. 10. 21. [Algorithm] 최소 신장 트리 (MST) 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim Algorithm 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식 임의 정점 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중 최소 비용의 간선이 존재하는 정점 선택 모든 정점이 선택될 때 까지 반복 ''' 6 11 0 1 32 0 2 31 0 5 60 0 6 51 1 2 21 2 4 46 2 6 25 3 4 34 3 5 18 4 5 40 4 6 51 ''' def find_MST(s): key[s] = 0 # 정점.. 2021. 10. 21. [Algorithm] 서로소(상호배타) 집합 (Disjoint-sets) 서로소(상호배타) 집합 서로 중복 포함된 원소가 없는 집합 교집합이 없음 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분 → 대표자(representative) 상호배타 집합 표현 - 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 nodes = [1, 2, 3, 4, 5, 6] parents = [0] * (len(nodes) + 1) # 각 노드의 부모를 저장할 배열 Make-Set(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성 def make_set(x): parents[x] = x for node in nodes: make_set(node) Find-Set(x) : x를 포함하는 집합을 찾는 연산, 대표자를 반환.. 2021. 10. 20. 이전 1 2 3 4 다음 728x90
