본문 바로가기

분류 전체보기

 (49)
큰 수의 연산들 큰수의 연산 long long 범위를 넘어가는 수에 대해서 가끔 연산을 수행해야하는 경우가 있다. 이 경우 string을 통해 연산해야한다. 프로그래밍 대회나 문제풀이에서 가끔 보이니 익혀두는게 좋을 것 같아서 따로 정리해보려고 한다. 이 포스트에서는 반복적으로 수가 더해지거나 곱해져서 input이 커진 경우가 아닌 (이 경우는 다른 포스트에서 다룰 예정), 처음부터 long long 범위를 벗어나는 input에 대한 처리를 다룬다. 1. 덧셈 string addition (string a, string b) { string result; int flag_a = 0, flag_b = 0; if (a[0] == '-') flag_a = 1; if (b[0] == '-') flag_b = 1; if (fla..
Segment Tree Segment Tree 세그먼트 트리(Segment Tree)란 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하는 방법에 관한 것입니다. 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조입니다. Ex) 3번 인덱스에서 8번 인덱스까지의 합을 구하는 방법은? 설계 방법 1. 배열을 이용해 무식하게 구하기 단순히 선형적으로 구하는 방법을 생각해봅시다. 인덱스 3부터 8까지 데이터의 범위를 하나씩 다 더하는 방법. 이러한 방식을 고려했을 때 앞에서 하나씩 더해가므로 데이터의 개수가 N이면 시간 복잡도는 $ O(N) $이 나옵니다. 따라서 구간 합을 N번 구해야한다면 시간복잡도는 $ O(N^2) $ 가 걸리고 이는 매우 불편한 복잡도이기 때문에 더 좋은 알고리즘이 필요합니다...
Union-Find 알고리즘 Union Find 상호 배타적 집합, Disjoint-set. 여러 노드가 존재할 때 어떤 두 개의 노드를 같은 집합으로 묶어주고, 다시 어떤 두 노드가 같은 집합에 있는지 확인하는 알고리즘입니다. Find: 노드 x가 어느 집합에 포함되어 있는지 찾는 연산 Union: 노드 x가 포함된 집합과 노드 y가 포함된 집합을 합치는 연산 구현 초기화 // parent[i] : i 노드의 부모 노드, parent[i] = i 인 경우 i는 루트 노드 int parent[100]; for (int i = 0; i < 100; i++) parent[i] = i; find int find(int x){ if (x == parent[x]) return x; else return find[parent[x]]; } x ..
최단경로 문제 (2) - ASP (플로이드-와샬) 2. All Pairs Shortest Path 모든 정점에 대해 최단경로를 찾으려면 앞서 살펴본 다익스트라, 벨만포드 알고리즘을 정점의 갯수만큼 반복하면 될 것이다. 그렇다면 시간복잡도는 아래와 같다. Dijkstra: $ O (V \log V + E) \to O (V^2 \log V + VE) \because V \to V^2 \ on \ dense \ graph, \ O(V^3) \because E = V^2 $ Bellman-Ford: $ O (V*E) \to O (V^2 *E) \because V \to V^2 \ on \ dense \ graph, \ O(V^4) \because E = V^2 $ 너무 느린것 같다. 그래서 플로이드와 와샬이란 사람이 새로운 알고리즘을 제시했다. Floyd-Wa..
최단경로 문제 (1) - SSP (다익스트라, 벨만포드) Shortest Path 최단거리 문제 입력으로 그래프의 정보(간선과 정점의 갯수)와 각 간선의 가중치가 주어질 때, 출발점에서 도착점까지의 가는데 드는 최소비용을 구하는 문제 최단경로의 특성 i. Optimal Substructure를 가지고 있다. (Dynamic Programming) distance(n, m): n에서 m까지의 최단거리이라고 정의한다면 distance(1, 4) = distance(1, 2) + distance(2, 3) + distance(3, 4)로 정의할 수 있다. 증명 만약 각 구간 중 하나라도 구해진 최단경로보다 더 짧은 경로가 존재한다고 가정하자. 그러면 전체 최단경로는 더 짧아질 것이고, 기존에 구했던 최단경로는 더이상 최단경로가 아니게 된다. 이에 모순이 발생하므로 ..
String Matching (2) - KMP 알고리즘 KMP algorithm navie string matcher를 다시 생각해보면, 위의 사진 같이 앞에 5개의 문자는 일치하지만 마지막 6번째 문자가 달라서 같지 않다고 나오는 경우, 앞에 5개의 문자는 일치한다는 정보를 버리고 한칸을 shift하고 처음부터 다시 비교하게 된다. KMP알고리즘은 앞에 5개는 일치한다라는 정보를 저장하여 더욱 효율적으로 검색한다는 메인 아이디어로 시작한다. 설계 패턴 자체를 비교하여 필요한 정보를 미리 계산할 수 있습니다. 전체 문자열은 같지 않지만 부분문자열은 같은 경우, 얼마만큼 비교를 skip할 수 있을지 정보를 제공해주는 함수입니다. 위 예시의 경우 ababa까지 일치하였고 앞뒤로 ababa / ababa 3개의 문자가 일치하고 2개의 문자가 일치하지 않으므로 2칸..
String Matching (1) - Navie, Rabin-Karp 알고리즘 String Matching Notation & Terminology T [1 .. n]: n개의 문자의 텍스트 P [1 .. m]: m개의 문자의 패턴 1≤ j ≤m에 대해 T[s+j] = p[j]인 경우 T에서 시프트 s와 함께 P가 발생합니다. P가 T의 시프트 s와 함께 발생하면 s를 유효한 시프트라고 합니다. 그렇지 않으면 잘못된 시프트입니다. Navie algorithm 패턴을 한칸을 옮기며 텍스트가 끝날 때 까지 비교해 보는 방식 의사코드 Navie-String-Matching (T, P) n > P; int n = T.length(); int m = P.length(); for (int s = 0; s < n-m; s++) { int count = 0; for (int i = 0; i < ..
슬라이딩 윈도우 알고리즘 슬라이딩 윈도우 배열이나 리스트의 요소의 일정 범위의 값을 비교할때 사용하면 유용한 알고리즘이다. 예를들어 정수로 이루어진 배열 [4, 25, 64, 1, 23, 2, -10, 3, 2] 에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다. 설계 하나씩 다 더해보면 아래와 같다. 서브 배열 합계 체크 (브루트 포스) #include #include using namespace std; int main() { int n, k; cin >> n >> k; vector v; for (int i = 0; i > input; v.push_back(input); } int sum, max = -1; for (int i =..

티스토리툴바