본문 바로가기

Algorithms135

Trie 연습 #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include #include #define MAXSTR 100 #define CMD_INSERT 100 #define CMD_SEARCH 200 #define CMD_COUNT 300 #define CMD_DELETE 400 extern void init_trie(); extern void Tries_insert(char key[MAXSTR + 1]); extern bool Tries_search(char key[MAXSTR + 1]); extern int Tries_CountofkeysWithPrefix(char key[MAXSTR + 1]); extern void Trie.. 2021. 7. 13.
큰 수의 덧셈 #include int mstrcmp(const char* a, const char* b) { int i; for (i = 0; a[i] != 0; ++i) { if (a[i] != b[i]) return a[i] - b[i]; } return a[i] - b[i]; } void mstrcpy(const char* src, char* dst) { int c = 0; while (src[c]) { dst[c] = src[c]; c++; } dst[c] = 0; } #define MAX_LENGTH 10000 extern void init(int); extern void add(char[], char[], char[]); extern void sub(char[], char[], char[]); #define.. 2021. 7. 12.
알고리즘 문제 해결 전략 1 04부 유명한 알고리즘 새로운 알고리즘을 어떻게 고안할 것인가에 대해 공부했지마만, 새로운 알고리즘을 만드는 것이 프로그래밍 대회의 전부는 아님. 적절한 추상화와 모델링 과정을 거쳐 알고리즘을 적용하는 것, 정확한 코드를 작성하는 것 또한 대회에서 평가하는 중요한 역량임. 13장 수치해석 13.1 도입 직접 풀기 힘든 수학 문제르 근사적으로 푸는 알고리즘과 이들의 수치적 안정성, 오차의 범위 등을 연구하는 전산학의 한 분야. 13.2 이분법 이분법의 정의 주어진 범위내에서 어떤 함수의 값이 0이 되는 지점을 수치적으로 찾아내는 기법임. 꼭 단조 함수가 아니더라도 답이 여러 개 있는 함수라도 연속이기만 하다면 이분법을 사용해 근을 찾을 수 있음. 이분법은 매 반복마다 구간의 크기를 절반으로 줄여 나감. double f(doubl.. 2021. 7. 10.
알고리즘 문제 해결 전략 1 12장 최적화 문제 int n, k; int c[1000], r[1000]; bool decision(double average) { vector v; for (int i = 0; i = 0; } double optimize() { double lo = -1e-9, hi = 1; for (int iter = 0; iter < 100; iter++) { double mid = (lo + hi) / 2; if (decision(mid)) hi = mid; else lo =.. 2021. 7. 10.
알고리즘 문제 해결 전략 2 6장 트리 (9) 26.4 트라이를 이용한 다중 문자열 검색 트라이에 포함된 문자열들이 접두사를 공유할 경우, 이 접두사들은 같은 노드에 대응된다는 점을 이용해 탐색 공간을 줄이는 알고리즘을 설계할 수 있음. KMP 알고리즘은 전처리 과정에서 부분 매치 테이블을 계산하는데, 이것은 바늘 문자열의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 둔 것임. 대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다는 의미에서 이와 같은 정보를 실패함수라고도 부름. 아호 코라식 알고리즘은 문자열 검색 알고리즘이라고 부름. 아호-코라식 알고리즘은 긴 문서에서 많은 문자열을 동시에 찾아야 하는 검색 엔진 등에서 특히 유용하게 사용됨. 실패 함수의 계산 HARD 2021. 7. 8.
알고리즘 문제 해결 전략 2 6장 트리 (9) 26. 트라이 26.1 도입 문자열 특화 자료 구조의 대표적인 것임. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있음. 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리임. 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결됨. 트라이의 루트는 항상 길이 0인 문자열에 대응되며, 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1씩 늘어남. 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 이 노드가 종료 노드인지를 나타내는 불린 값 변수로 구성됨. 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 .. 2021. 7. 8.
알고리즘 문제 해결 전략 2 6장 트리 (9) 25 상호 배타적 집합 25.1 도입 상호 배타적 집합 이렇게 공통 원소가 없는, 다시 말해 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 자료 구조임. 배열로 상호 배타적 집합 표현하기 belognsTo[]. 찾기 연산이 O(1)이라는 점이 아주 좋음. 합치기 연산을 빠르게 하려면? 트리를 이용한 상호 배타적 집합의 표현 트리의 루트에 있는 원소를 각 집합의 대표. 모든 자식 노드가 부모에 대한 포인터를 가지고 있어야 함. struct NaiveDisjointSet { vector parent; NaiveDisjointSet(int n):parent(n) { for (int i = 0; i < n; i++) parent[i] = i; } in.. 2021. 7. 5.
알고리즘 문제 해결 전략 2 6장 트리 (8) 24.6 펜윈 트리: 빠르고 간단한 구간 합 구간 중 필요한 부분만 남긴 결과를 보여줌. 남은 구간은 수는 정확하게 n개임. 물론 n개의 수에 대한 부분 합을 n개의 숫자에 저장하는 것이니 놀랍지는 않지만, 구간 트리에 비하면 꽤 큰 절약임. 어떤 부분 합을 구한든 O(lgn)개의 구간 합만 있으면 된다는 사실. 각 구간에 대해 오른쪽 끝 원소의 인덱스와 이들의 이진수 표현을 보여줌. 다른 부분 합에 대해서 일일이 확인해 보면 오른쪽 끝 위치의 이진수 표현에서 마지막 비트를 지우면 다음 구간을 쉽게 찾을 수 있음. 펜윅 트리에서 배열의 값을 변경하는 것은 해당 위치의 값에 숫자를 더하고 빼는 것을 구현함. 맨 오른쪽에 있는 1인 비트를 스스로에게 더해 주는 연산을 반복하면 해당 위치를 포함하는 구간들을 .. 2021. 7. 5.
알고리즘 문제 해결 전략 2 6장 트리 (7) 24.2 문제: 등산로 등산로의 난이도는 등산로를 가다 만나는 표지판 중 최대 해발 고도와 최저 해발 고도의 차이임. 24.3 풀이: 등산로 최소치를 구하는 RMQ 클래스를 재활용함. 24.4문제: 족보 탐험 어떤 가문의 족보가 시조부터 시작해 쭉 주어질 때, 두 사람의 촌수를 계산하는 프로그램. 24.5 풀이: 족보 탐험 트리의 최소 공통 조상 찾기 트리를 일렬로 펴기 트리에는 항사 n-1개의 연결이 있으므로, 2n-2번 움직이게 됨. 처음에 루트에서 시작하는 것도 경로에 포함되므로, 전체 경로의 길이는 2n-1이 됨. - u를 포함하는 서브트리에서 v를 포함하는 서브트리로 넘어가려면 LCA(u,v)를 거치지 않으면 안됨. - LCAu,v)에서 그 부모 노드로 이 경로가 올라가려면 그 전에 LCA(u,.. 2021. 7. 5.