CS/Algorithm 이론
[Algorithm] 플로이드 와샬(Floyd Warshall)
플로이드 와샬 하나의 정점에서 다른 모든 정점으로 가는 최단 거리를 구하는 다익스트라와는 다르게 플로이드 와샬은 모든 정점에서 모든 정점으로 가는 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 또한 다이나믹 프로그램에 기반을 두고 있다. 알고리즘 핵심은 "X에서 Y로 가는 최소 비용 vs X에서 선택된 노드로 가는 비용 + 선택된 노드에서 Y로 가는 비용" 중 최소값을 선택하는 것이다. 즉, 점화식으로 나타내자면 distance[i, j] = min(distance[i, j], distance[i, n] + distance[n, j]) int INF = 1000000; int a[4][4] = { { 0, 5, INF, 8 }, { 7, 0, 9, INF }, { 2, INF, 0, 4 }, { INF..
[Algorithm] 다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘이란? 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있음 다만 이때 음의 간선을 포함할 수 없는데(비용이 음수일 수 없음!) 현실에선 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 적합하다고 할 수 있다. 다이나믹 프로그래밍인 이유는 '최단 거리는 여러 개의 최단 거리로 이루어져있기 때문'. 즉, 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 사용하게 된다. 알고리즘 출발 노드를 설정 출발 노드를 기준으로 각 노드까지 가는 비용을 최소 비용으로 저장하고 출발 노드를 방문한 노드로 체크 현재 방문한 노드들과 연결되어 있고 방문하지 않은 노드 중에서 가장..
[Algorithm] 최장 증가 수열 (LIS)
최장 증가 수열(LIS) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 푸는 방법 DP dp[x] : x번째 수를 마지막 원소로 가지는 list의 길이 라고 점화식을 두면 O(N^2)의 시간복잡도로 구현할 수 있음 하지만 N이 10만이 넘으면 이걸로 풀수 없음 -> 이분탐색으로 시간을 단축시키자 for (int k = 0; k < n; k++){ length[k] = 1; for (int i = 0; i < k; i++){ if(arr[i] < arr[k]){ length[k] = max(length[k], length[i] + 1); } } } 이분탐색 시간 복잡도: O(..
[Algorithm] 이분 탐색
정렬되어 있는 배열에서 데이터를 찾으려고 할 때 O(N)이 걸리는 순차탐색에서 시간을 줄여 O(logN)의 시간으로 값을 찾는 탐색 방법 특징 및 과정 이분 탐색을 하고자 하는 배열이 이미 정렬되어 있어야함 과정 left, right로 가운데롤 mid로 잡아줌 mid과 구하고자 하는 값을 비교 mid left = mid + 1 mid > 구하고자 하는 값 -> right = mid - 1 left > right이 될때까지 2-4번을 반복
[Algorithm] 비트마스킹
비트마스킹(BitMasking) 비트마스킹(BitMasking)이란 비트를 활용해 집합을 표현하는 기법이라고 볼 수 있다. 빠른 연산속도와 적은 메모리 사용량, 그리고 배열을 정수로 표현할 수 있다는 장점이 있다. 비트는 컴퓨터에서 사용되는 데이터의 최소단위인데 0과 1로 표현한다. 따라서 2진법이라고 생각하면 편하다. 비트마스킹은 이런 특징을 이용한다. 예를 들어 {1, 4, 3}이라는 집합이 있다고 해보자. 각 원소의 포함 여부를 이용해 부분집합을 표현하면 다음과 같다. {1, 4} => 110 {3} => 001 {1, 3} => 101 또한 이를 10진수로 표현할 수도 있다. {1, 4} => 110 => 6 {3} => 001 => 1 {1, 3} => 101 => 5 이러한 특징을 이용해 비트..
[Algorithm] 다이나믹 프로그래밍 Dynamic Programming
다이나믹 프로그래밍 (Dynamic Programming, DP)란? 다이나믹 프로그래밍 (이하 DP)란 여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘이다. 분할정복과 비슷하다고 생각할 수 있지만 분할정복은 작은 문제가 중복이 일어나지 않고, DP는 반복(작은 문제의 결과가 같다)된다. 그래서 DP에서는 작은 문제들이 반복되는 것을 이용해 문제를 풀어나간다. 포인트는 모든 작은 문제들은 중복을 제거하고 한번만 풀어야 한다는 점이다. 따라서 정답을 구한 작은 문제들을 어딘가에 메모(Memoization)해둔다. 다시 그보다 큰 문제를 풀 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 많이 언급하는 피보나치 수열 문제를 예시로 들어보자. ..
[Algorithm] 최소 신장 트리 Minimum Spanning Tree
Minimum Spanning Tree(MST) MST(Minimum Spanning Tree)에 대해 알아보기 전에 Spanning Tree가 무엇인지 부터 알아야 한다. Spanning Tree란 1. 그래프의 모든 정점을 포함 2. 간선의 수가 가장 적음(n-1개) 3. 사이클이 없음 인 트리의 특수한 형태이다. 위의 두 조건을 만족하는 경우는 여러가지 이므로 하나의 그래프에는 많은 신장 트리(spanning tree)가 존재할 수 있다. 이는 BFS, DFS를 이용하여 찾을 수 있다. 그렇다면 MST는 무엇일까 MST는 위에서 설명한 spanning tree 중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비..
[Algorithm] Hash table
Hash Table 이란? (key, value)로 데이터를 저장하는 자료구조로 빠르게 데이터를 검색할 수 있다는 장점이 있다. 해시 테이블이 빠른 검색 속도를 제공하는 것은 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 각각의 key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. Ex) (key, value) = ("John Smith", "521-1234")를 크기가 16인 해시 테이블에 저장하면, 먼저 index = hash_function("John Smith") % 16으로 index를 구해서 array[index] = "521-1234"로 저장한다. 평균 시간 ..