one Book a Day

LRU cache O(1) 캐시는 불필요한 통신을 줄이고 기민한 UX를 제공 DB과부하를 막음.(query결과 저장) Proxy, CDN(유저와 가까운 CDN node) 메모이제이션 OrderedDict이용 from collections import OrderedDict MAX_SIZE = 2 cache = OrderedDict() def get_user(user_id): if user_id in cache: cache.move_to_end(user_id) return cache[user_id] if len(cache) == MAX_SIZE: cache.popitem(last=False) cache[user_id] = fetch_user(user_id) return cache[user_id] last=F..

인접 행렬 V^2개의 원소를 가진 2차원배열. 인접 리스트 V개의 연결리스트( 동적 배열 ) vector기반이라 느리다. 간선 번호 붙일 때 불편하다 ( 순회하기 힘들다. ) 간선 배열 #include #include using namespace std; typedef pair pint; #define x first #define y second const int maxv = 100000, maxe = 200000; pint edge[maxe]; // 배열의 각 주소는 (x, y) 튜플 페어를 가짐. int st[maxv]; // 간선을 정렬한 후, 각 점에서 시작하는 간선의 첫 인덱스 int v, e; int main() { // Input cin >> v >> e; for (int i=1; i> ed..

Hash 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것. 해시함수를 구현하여 데이터값을 해시값으로 매핑시킨다. 내부적으로 array를 사용해 데이터를 저장. 데이터 고유의 인덱스로 key의 고유 숫자 값이 저장됨. 특정 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터 사이에 끼어들어나 삭제시 다른 데이터로 채울 필요가 없음. 즉 추가적인 비용이 없도록 만들어진 구조. Hash Table 해시 테이블은 로 데이터를 저장하는 자료 구조 중 하나이다. Key값에 해시 함수를 적용해 index를 생성하고, index를 활용하여 값을 저장, 검색 할 수 있다. Key값을 해싱하여 검색, 저장하므로 평균 시간 복잡도는 O(1)이다. (항상 O(1)이 아닌 ..

0 - 1Knapsack Problem 쪼갤 수 없는 물건을 배낭에 담는문제로 DP로 풀어야하는 대표적인 문제 DP로 풀수 있는지 여부는 Principle of Optimality 성립 여부를 보면 된다. Principle of Optimality 어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다 즉 부분사례의 최적해가 현 사례의 최적해의 부품이 된다면 DP로 풀 수 있다. 물건을 취하지 않고 P[i-1][j]를 선택하느냐 취하고 P[i-1][j-wk] + v[i]를 하느냐. 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 13 13 2 0 0 0 0 8 8 13 13 3..

중복조합 서로다른 n개의 원소 중, 중복을 허락하여 r개를 뽑는 것. nHr = (n+r-1)C(r) 조합에서의 중복만 허용하므로 순서는 여전히 상관하지 않는다.(조합) dfs에서 i+1이 넘어가면 조합, i가 넘어가면 중복조합 def dfs(idx, depth): if depth == r: print(*comb) for i in range(idx,n): comb[depth] = arr[i] dfs(i, depth + 1) n-1개의 칸막이를 뽑아야하는 요소들 r개 사이에 배치하는 경우의 수. = n-1개의 막대기로 구분된 영역에 요소를 집어넣는 경의의 수. nHr = n-1+r C n-1 = n-1+r C r 다음에 예제 풀어 첨부할 것.

편집거리 알고리즘 두 문자열의 유사도를 판단하는 알고리즘 유사도란? 어떤 문자열을 삽입, 삭제, 변경을 몇 번 해서 동일하게 바꿀 수 있는지의 최솟값. LCS와 같이 2차원 배열을 통해 문자열을 하나씩 비교. 최초는 공집합과 비교해 문자열 길이만큼 1씩 카운트를 준다(공집합에서 그 문자열이 되려면 열마나 삽입되어야 하는가?) 두 문자를 비교해 추가, 삭제, 변경의 소요마다 1씩 카운트. A[i]==B[j]일 때 편집거리 D(i,j) = D(i-1,j-1) 같은 문자가 나왔을 때는 대각선 왼쪽 위의 값을 가져온다. A[i]!=B[j] 면 D(i,j) = min(D(i-1,j),D(i,j-1),D(i-1,j-1)) + 1 즉 수정, 삽입, 삭제를 한 편집거리중 최소값을 가져온다. def editDistanc..

Parametric Search 최적화 해법인 이분탐색을 결정문제로 바꾸어 푸는 기법. ex.) 고기를 200g잘라라 -> 고기가 200g보다 가벼운가? 무거운가? 의 결정문제로 바꿈.(예 아니오) 특정 값을 찾는게 아닌 오차 범위 내에서 가장 가까운 부등호 식으로 결과를 판별한다. 가능한 해의 영역이 연속적이어야 한다. (최솟값 결정문제 a가 만족한다면 a이상의 값은 모두 만족.) 예제 BOJ 1637 날카로운 눈 import sys input = sys.stdin.readline def get_sum(target): total = 0 for i in range(N): if target >= arr[i][0]: total += ((min(arr[i][1],target) - arr[i][0])//arr[..

Tree DP subtree에서 구한 해를 이용해 전체 트리의 해를 구하는 방식으로 진행이 됨. dp[i] = i를 루트로 하는 서브 트리의 ~같은 식으로 DP Table을 정의. dp는 보통 선형구조에서 이루어지지만 tree는 비선형 구조기 때문에 탐색 순서를 미리 정해주는게 일반적이다. / 그래프에서 우리가 dp를 사용하듯 트리도 dp를 사용하기 충분. 탐색 순서는 보통 dfs를 돌면서 나오는 트리인 dfs트리를 기준으로 한다. 트리 dp도 대부분 상태 dp가 들어간다. ex.) dp/[i]/[j] = i는 i를 루트로하는 subtree에서 i의 상태가 j일때. 보통 i번째 노드를 루트로 하는 서브트리에서 i번째 루트 노드를 포함했을 때와 포함 하지 않았을 떄 조건 중 최적값을 가져온다. 기본 구조 ..

라인스위핑 스위핑 알고리즘이란? 특정 선이나 공간을 한쪽에서부터 쓸어버리는 식의 알고리즘. 일정 좌표, 축기준 정렬 한 뒤 일정 시점의 좌우 가장 가까운 두 점사이의 거리보다 멀리떨어진 점은 조사하지 않는 방식. 가지치기를 하겠다는 이야기다.(O(NlogN)) 아래는 2261번 문제에 대한 분할정복 풀이. import sys input=sys.stdin.readline INF=sys.maxsize # 두 점 사이의 거리를 구하는 함수 def dist(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2 def divide(start,end): # 점 하나면 버림 if start==end: return INF # 점 두개면 거리구해서 리턴 elif end-start==1: retur..

Trie(트라이) = radix tree = prefix tree = digital search tree 탐색이라는 뜻의 retrieval에서 trie를 따온 것. 문자열 집합을 표현하는 트리 자료구조. 하나하나 비교가 아닌 key로 노드를 탐색. 원하는 원소를 찾는 작업을 O(M)에 해결 이진트리는 O(logN)*문자열의 길이 M => O(MlogN) 빠르지만 저장공간의 크기가 매우 크다.(자식들의 포인터를 모두 배열로 저장하고 있기때문.) 문자열 검색 문제에서 입력되는 문자열이 많을 경우 사용. 적용되는 기능. 검색엔진 사이트에서 제공하는 자동완성 및 검색어 추천기능에서 Trie 알고리즘 사용. 맞춤법 검사, IP라우팅 (라우터에서 packet을 포워딩해줄때 다음 라우터로 경로를 결정하기 위해 패킷의..