실시간 협업 툴을 만들때 사용하는 기술로 CRDT와 OT가 대표적이다. OT(Operational Transformation)은 유저들의 모든 변경사항을 기록하고, 서버에 전송해 순차적으로 적용해 결과를 만드는 방식이다. 구글 독스 등에서 사용하는 기술이나, 사용자가 몰리면 과부하 걸릴 수 있다. 반면 CRDT(Conflict-Free-Replicated Data Types)는 모든 개체(char 등) 유니크한 값으로 저장하기에 변경 사항을 합칠 때 충돌이 발생하지 않는다. 매번 서버의 응답을 기다릴 필요 없는 방식이다. refs CRDT vs OT A Gentle …

Read More

유향 그래프의 정점을 탐색 가능한 순서로 정렬하는 알고리즘이다. 유입 간선이 없는 정점들을 찾아 정렬된 리스트에 추가한다. 유입 간선이 없으므로 바로 탐색해도 무방한 정점들이다. 해당 정점들의 유출 간선들을 제거한다. 앞선 정점들을 방문한 상황에서는, 해당 간선들이 그 다음 탐색에 영향주지 않는다. 모든 정점을 정렬할 때 까지 1과 2를 반복한다. 불가하다면 그래프에 사이클이 존재하는 것이다. [구현 예시] from collections import defaultdict, deque indegree = defaultdict(int) for v, neighbors …

Read More

content 연산을 수행하는 비용(시간, 공간)의 상한을 대략적으로 표기하는 방법 비용이 어떤 비율로 증가하는지(상수, 선형, 로그, 지수 등)에만 관심있어서 지배적이지 않은 항은 무시한다 O(2N) == O(N) O(log_2(N)) == O(log_10(N)) refs links

Read More

알고리즘을 수행 과정 별로 분할하여 비용(시간 복잡도)을 구하는 분석 방법. 일련의 연산들을 구분하여 평균적인 비용을 낸다는 측면에서 worst-case approach 보다 현실적일 수 있다. refs 분할상환분석 - 위키백과, 우리 모두의 백과사전 links Big-O

Read More