알고리즘/개념 (3) 썸네일형 리스트형 플로이드-와샬(Floyd-Warshall) 알고리즘 이해하기 최단경로를 탐색하는 플로이드-와샬(Floyd-Warshall) 알고리즘에 대해 알아보자.플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 거리를 찾는 동적 프로그래밍(Dynamic Programming) 알고리즘이다. (만약 최단거리의 경로를 구하고 싶다면 복원 로직의 추가가 필요하다.)1. 동작방식의 이해플로이드-와샬 알고리즘의 동작 방식은 아주 간단하다.모든 정점 쌍(i,j)에 대해, 중간 정점 k를 경유하는 경로가 기존 경로보다 짧은지 검사각 단계에서 k번째 정점을 거쳐가는 모든 경우를 고려즉 아래와 같은 세 노드가 있을 때, 기존에 주어진 i → j 의 길이와 노드 k가 중간에 추가된 i → k → j 를 비교하여 i → j 의 길이를 더 작은 값으로 갱신하는 것이다.점화식은 아래와 같.. 펜윅 트리(1차원 펜윅 트리, Fenwick Tree, Binary Indexed Tree) ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 위와 같은 1차원 배열이 있다. 해당 배열에서 ary[3]~ary[7] 구간합을 구하고자 한다. 가장 기본적인 코드는 아래와 같이 하나씩 모두 더하는 것이다. 해당 코드의 시간복잡도는 O(N) 이다.(연산의 수가 M일 경우 O(MN)) 펜윅트리를 사용하게 되면 이를 O(logN) 으로 감소시킬 수 있다. 그렇다면 펜윅트리가 무엇인지 알아보자. 1. 펜윅트리란 무엇인가? 펜윅트리는 Binary Indexed Tree, BIT 라고도 하며, 쉽게 말해 구간합을 빠르게 구하기 위한 자료구조이다. 2. 트리만들기(초기화) 입력받은 배열 ary[9] = {3, 5, 6, 2, 9, 10, 4, 7, 8} 를 이용해 펜윅트리를 만들어 보자. 펜윅트.. 2차원 펜윅트리 이해하기(2-dimentional Fenwick Tree) 펜윅트리는 비트연산을 통해 빠른 시간에 구간합을 구하는 배열 형태의 트리이다. 이 글에서는 2차원 펜윅트리만을 설명하고 있다. 1차원 펜윅트리에 대한 이해가 필요하면 블로그 내 펜윅트리 글(https://uldada.tistory.com/5)을 참고하자. 2차원 펜윅트리 우선 2차원 펜윅트리의 Update와 Sum 함수를 보자. 코드를 보면 x축(여기에선 열을 의미)으로 펜윅트리가 동작하며, 그 안에 while문을 통해 y축(행을 의미)으로 펜윅트리가 동작한다. 일단 update를 통해 초기화(입력받은 배열을 통해 펜윅트리 채워나가기)를 진행해 보자 초기화는 update 함수를 통해 진행된다.(1차원 펜윅트리와 동일한 방식) 입력받은 배열은 아래와 같다. 1 2 3 4 5 6 7 8 9 10 11 12 .. 이전 1 다음
