알고리즘 (44) 썸네일형 리스트형 최단 경로 알고리즘 - 3. 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다. 핵심 아이디어 거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다. 구현 코드 void floyd_warshall() { // i 노드에서 j노드로 갈 때, k노드를 거쳐서 가는게 더 빠르다면 최단 거리 갱신 for (int k = 1; k b >> c; graph[a][b] = min(graph[a][b], c); } floyd_warshall(); for (int i = 1; i 최단 경로 알고리즘 - 2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 최단 경로(shotest path)를 찾는 알고리즘으로, 시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다. 특징 가중치가 음수 일 때도 사용이 가능 음수 사이클 감지 가능 시간 복잡도 : O(VE) 벨만포드 vs 다익스트라 다익스트라 그리디 방식 - 매번 방문하지 않은 노드 중, 최단 거리 노드 선택 음수 간선이 없다면 최적해를 찾을 수 있다. 벨만포드 매번 모든 간선을 확인 (따라서 모든 간선이 양수일 경우 다익스트라 알고리즘이 더 빠르다) 따라서 다익스트라 알고리즘의 최적해를 항상 포함 음수 간선이 포함된 경우 음수 사이클을 탐지할 수 있다. 핵심 아이디어 거쳐가는 노드를 기준으로 가능한 모든 노드 쌍의 최단 거리를 갱신해 나간다. 알고리즘 시작 노드 설정 최단 거리 테이블 초기화 다.. 최단 경로 알고리즘 - 1. 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘(Dijkstra Algorithm) 최단 경로(shotest path)를 찾는 알고리즘으로, 시작 노드에서 다른 노드들 사이의 최단 경로를 찾는 알고리즘이다. 단, 음의 간선을 포함하면 안된다. (음수 사이클이 발생할 수 있기 때문) 다익스트라 알고리즘은 매번 '가장 비용이 적은 노드'를 선택하여 임의의 과정을 거치기 때문에 기본적으로 그리디 알고리즘으로 분류된다. 핵심 아이디어 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택. 그 노드를 기준으로 최단 거리 테이블을 갱신 알고리즘 최단 거리 테이블 초기화 한다. (INF로 설정) 시작 노드 설정한다. (시작 노드 비용은 0) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐서 다른 노드.. 이분 탐색 이분 탐색/이진 탐색(Binary Search) 이분 탐색(Binary Search)이란, 정렬된 리스트에서 탐색 범위를 절반씩 줄여가며 값의 위치를 찾아내는 알고리즘이다. 필요 조건 내부 데이터가 정렬 되어 있어야 한다. Random Access가 가능해야 한다. (이분 탐색의 성능상 효율을 보기 위해 필요) 특징 한번 탐색할 때마다, 탐색 범위가 절반씩 줄어든다. 시간 복잡도가 O(logN) 으로 탐색 속도가 빠르다. 구현 방법 1. iteration version int binary_search(int A[], int L, int R, int T) { while (L A[M]) L = M + 1; else return M; } return -1; // unsuccessful } 특징 배열 인덱스 범.. 펜윅 트리(Fenwick Tree) Goal 펜윅 트리를 구현할 수 있다. 펜윅 트리(Fenwick Tree)란? 펜윅 트리는 구간합을 빠르게 구하기 위한 자료구조이다. (BIT, binary indexed tree 라고도 한다.) 기본 연산 sum(pos) : [0~pos] 부분합(prefix sum) [a, b]구간의 range sum은 sum(b) - sum(a - 1) 로 구한다. add(pos, diff) : 값 변경에 영향 받는 구간 갱신 두 연산 모두 O(logN)의 시간 복잡도를 갖는다. 공간 복잡도 : O(N) - (정확히 N + 1) 펜윅 트리 vs 세그먼트 트리 펜윅 트리 장점 코드 길이가 더 짧다. (구현이 간단) 메모리가 더 적게 든다. 세그먼트 트리 모든 구간에 대한 값을 가지고 있기 때문에 좀 더 일반적으로 사용.. 세그먼트 트리(Segment tree) Goal 세그먼트 트리를 구현할 수 있다. 세그먼트 트리(Segment tree)란? 각 노드가 구간을 표현하는 트리이다. (구간 트리 라고도 한다.) 세그 먼트 트리의 기본 구조 1. 루트가 표현하는 구간 크기가 2^n 형태인 경우 값의 개수가 2^n 꼴이 아닐 경우 남는 구간을 의미없는 기본 값으로 채워 포화 이진 트리 형태로 표현 2. 루트 구간이 표현하는 구간 크기가 2^n이 아닌 경우 Root Node : 전체 구간을 표현한다. Leaf Node : 크기가 1인 구간. 즉, 값 자체를 표현한다. Internal Node : [a, b] 구간 정보를 표현한다. 기본 연산 Query(from, to) : 구간 합과 같이 특정 구간에 대한 질의 처리 Update(index, data) : 값 변경에 .. Prefix sum GoalPrefix sum을 구현할 수 있다.Prefix Sum이란?시작 위치부터 현재 위치까지의 원소 합을 저장하는 배열이다.부분 합(partial sum) 또는 누적 합(cumulative sum)이라고도 한다. Prefix sum은 누적 합을 미리 구하는 전처리 과정을 통해 구간 합(range sum)을 빠르게 구할 때 사용된다. *prefix sum : 0~b까지의 누적합 (반드시 첫번 째 원소를 포함하는 구간)*range sum : a~b까지의 구간 합 예를 들어 누적 합을 저장한 배열을 pSum이라고 할 때,[a, b] 구간의 합을 구하기 위해서 pSum[b] - pSum[a - 1]와 같은 연산을 해주면 O(1) 시간에 구간 합(range sum)을 구할 수 있다.a가 0인 경우, pSum[.. 피보나치 수열 www.acmicpc.net/blog/view/28 이전 1 2 3 4 ··· 6 다음
