# 문자열을 찾을때 사용하는 알고리즘이 여러가지 있는데, 대표적으로 KMP, 라빈카프, 보이어-무어, BruteForce, Trie등이 있다. 전체 문자열 길이를 N, 찾고자하는 패턴길이를 M이라 하면 BruteForce는 O(NM) / KMP는 O(N) + 전처리 / 보이어-무어는 O(N/M), 최악 O(N) / 라빈카프는 O(N)이다. # 이번에 소개할 자료구조는 Trie(트라이)라고 하는 자료구조인데, 우선 Trie라는 말은 retrieval(탐색)에서 따온 말이라고 한다. 트라이는 트리구조를 사용해서 문자열을 저장하는데, 시간복잡도가 가장 긴 문자열의 길이를 L이라 했을때 O(L)밖에 걸리지 않는다. # 우선 'fire', 'firefox', 'frodo', 'frost', 'fry'를 저장했을 ..
# 요즘 스터디에서 이분탐색을 주제로 한 문제들을 풀다 내가 풀이 하고 있는 방식이 '이분탐색'이 아니라는 것을 깨달았다. 아예 다른 것은 아니지만, 엄밀히 따지자면 '매개변수 탐색'이라는 분류가 따로 존재했다. # 이분탐색은 '정렬된 배열'에서 target의 존재여부와 존재한다면 위치를 알려주는 알고리즘이다. 우리가 찾는 target이 배열 안에 존재한다면, 그 위치를 알려준다는 것이다. # 하지만, 'target과 정확히 일치하는 값' 이 존재하지 않는다면?? -> 우리는 parametric search를 통해 최적화된 값을 찾을 수 있다. # Parametric Search는 최적화 문제를 결정 문제로 풀 수 있는 기술이다. '최적화 문제'니 '결정 문제'니 다 처음 들어보는 말이어서 어려울 수 있..
- 유클리드 호제법: 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 그냥 쉽게 말해 A = Bq + R이라는 식에서 A와 B의 최대공약수(GCD)는 B와 R의 GCD와 같다는 뜻이다. 이 알고리즘을 사용하면 빠르게 A와 B의 최대공약수를 구할 수 있다. - 증명은 다음 블로..
# 분할정복을 이용한 거듭제곱 - C**n연산은 x를 n번 곱하므로 O(N)이지만, 이 방법을 사용하면 O(logN)에 거듭제곱 값을 구할 수 있다. - 아래 코드에서 fpow함수가 그 방법이다. - n이 1이면 그냥 C의 1제곱이므로 return C를 해준다. - n이 2이상일 때, C의 n제곱은 다음과 같다. - n이 짝수이면 윗줄의 식을 만족하고, n이 홀수이면 아래줄의 식을 만족한다. 코드로 짜면 다음과 같다. 1. 재귀사용 def fpow(C, n): if n == 1: return C else: x = fpow(C, n//2) if n % 2 == 0: return x * x else: return x * x * C 2. 반복문 사용 - n & 1은 n이 짝수이면 0이므로 False이고, n이..
맨날 무엇이든지 대충대충 하는 습관이 들어서 그걸 고치기 위해 영어문서를 해석해보고 정리해본다. 문제풀이 할 때 가끔씩(?) 쓰는 collections 모듈이다. Source code는 https://github.com/python/cpython/blob/3.8/Lib/collections/__init__.py python/cpython The Python programming language. Contribute to python/cpython development by creating an account on GitHub. github.com 에서 확인할 수 있다. 여러 Object들이 존재하지만, 아직 사용해본 2개만 정리해보겠다. (나머지는 나중에 쓰는 날이 오면 그때 마다 정리하는 걸로..) *..
stack,queue,deque가 무엇인지 설명은 넘어가도록 하고 간단히 STL만 정리했다. queue는 stack과 비슷하고 q.top()대신 q.front()와 q.back()이 있다. queue의 멤버함수는 stack과 거의 같다. 스택 선언 stack s type 자료형을 저장하는 스택 생성 스택의 멤버함수 s.empty() 스택이 비어있으면 1 반환 아니면 0 반환 s.pop() 스택의 맨 위의 요소를 제거 s.push(x) 원소(x) 삽입 s.size() 스택의 전체 크기 반환(스택에 있는 원소 수) s.top() 스택의 맨 위에 있는 데이터 반환 deque는 vector와 비슷하고 데이터의 삽입과 삭제가 front와 back에서 가능하다. deque의 멤버함수는 vector와 거의 같다. d..
벡터 선언 vector v type 자료형을 저장하는 동적배열(벡터) 생성 vector v(n) 0으로 초기화된 n개의 원소를 가지는 벡터 생성 vector v1(n, m) m으로 초기화된 n개의 원소를 가지는 벡터 생성 vector v2(v1) v2는 v1 벡터를 복사해서 생성 vector v3(n, vector(m, 0)) n*m 크기의 2차원 벡터를 선언하고 0으로 초기화 vector v4 = vector(v1.begin()+2, v1.end()) v4는 v1의 2번째 원소부터 마지막 원소까지 복사하여 생성 벡터의 멤버함수 v.assign(n, x) n개의 원소값을 x로 할당 v.at(i), v[i] i번째 원소를 참조, at은 v[i]보다 느리지만 범위 점검함으로써 안전하다 v.front(), v..
STL(Standard Template Library) * 표준 C++ 라이브러리 * 구성요소 : Container, Iterator, Function Object, Algorithm 등 컨테이너 : 객체를 저장하는 객체, 자료구조 - 순차 컨테이너(sequence container) : array, vector, list, deque 등 * 자료를 입력한 순서대로 저장하기 때문에 저장, 검색 알고리즘에 불리 -> 많지 않은 양의 자료, 검색속도 중요하지 않은 경우 사용 - 연관 컨테이너(associative container) : set, multiset, map, multimap 등 * 이진탐색트리 기반 * 일정규칙에 따라 자료를 조직화하여 저장 * 자료를 정렬하여 저장하기 때문에 검색 유리 -> 많..
모르는 사이에 조금씩 조금씩..
