지나가던 컴공생

Snowflake 알고리즘은 분산 시스템에서 고유한 ID를 생성하기 위해 설계된 방법입니다. 이 알고리즘은 Twitter에서 개발되었으며, 여러 서버에서 동시에 ID를 생성할 때 발생할 수 있는 충돌을 방지하면서도 시간에 따라 정렬 가능한 ID를 생성합니다.Snowflake ID의 구조:Timestamp (41 bits): 밀리초 단위의 타임스탬프Datacenter ID (5 bits): 데이터 센터 식별자Worker ID (5 bits): 워커(서버) 식별자Sequence number (12 bits): 같은 밀리초 내에서 생성된 ID를 구분하기 위한 시퀀스 번호주요 특징:유일성: 분산 환경에서도 중복 없는 ID 생성정렬 가능: 시간 순서대로 정렬 가능높은 성능: 초당 수백만 개의 ID 생성 가능64비..

- https://school.programmers.co.kr/learn/courses/30/lessons/131532 - 레벨 : 4 더보기 distinct 유의,한 번 더 생각해볼 만한 문제 SELECT YEAR(a.sales_date) AS year, MONTH(a.sales_date) AS month, b.gender, COUNT(DISTINCT(a.user_id)) AS users FROM online_sale AS a INNER JOIN user_info AS b ON a.user_id = b.user_id WHERE b.gender IS NOT NULL GROUP BY year, month, gender ORDER BY 1, 2, 3 - https://school.programmers.co...

최소 공통 조상(Lowest Common Ancestor)는 트리(Tree) 구조에서 특정한 두 노드의 공통된 조상 중에서 가장 가까운 조상을 말한다. LCA 알고리즘은 트리에서 두 노드사이의 거리를 빠르게 구하는ㅇ 등의 다양한 계산에 활용될 수 있다는 특징이 있다. 여기서 다룰 알고리즘은 일종의 dynamic programming이며 최소 공통 조상을 빠르게 찾아내는 알고리즘이다. 노드를 거슬러 올라가 보면 15와 20의 LCA는 1이다. 이를 구하는 방법은 1. 모든 노드에 대한 깊이(depth)를 구한다. 2. 모든 노드에 대한 2^i번째 부모 노드를 구한다. 3. 최소 공통 조상을 찾을 두 노드를 설정한다. 4. 두 노드의 깊이(depth)가 동일하도록 거슬러 올라간다. 5. 최상단 노드부터 내려..

Rabin-Karp 알고리즘은 항상 빠르지는 않지만 일반적으로 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이라는 점에서 자주 사용된다. Ⅰ. 라빈카프 알고리즘은 해시(Hash) 기법을 사용하여 연산속도가 O(1) 이라는 장점이 있다. (시간복잡도는 O(n) cf) 해시는 긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법 ex) abaca의 해시 값 = 97 * 2^4 + 98 * 2^3 + 97 * 2^2 + 99 * 2^1 + 97 * 2^0 Ⅱ. 해시값이 중복되는 경우(==collision) 포인터를 이용해 연결자료 구조를 이용해 해결한다. Ⅲ. 해시값은 거의 일치하는 일이 없기 때문에 'parent string'과 'pattern string'의 해시값이 일치하는 경우에만 문자열을..

SSC(강한결합요소)는 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다는 특징이 있다. 즉 사이클이 발생할 경우 무조건 SCC에 속한다. 이는 Directed Graph에서만 의미가 있는데, Undirected Graph는 그래프 전체가 무조건 SCC이기 때문이다. SCC를 추출하는 알고리즘에는 코사라주 알고리즘과 타잔 알고리즘이 있는데 코사라주 알고리즘이 구현은 쉽지만 타잔 알고리즘이 더 적용하기 좋다는 점에서 타잔 알고리즘을 사용하여 구현 할 것이다. 1. dfs를 할 때, 처음 정점 x의 부모에게 고유한 번호인 id를 부여한다. 예를들어 d[x] = ++id; 로 작성하면 x의 부모인 d[x]에게 현재 id값에 1을 더한 번호를 부여하는 것이다. 즉 부모==id값이라고 생각하면 됨 2. 정점 ..

이분매칭(bipartite match)은 A집단이 B집단을 선택하는 방법에 대한 알고리즘이다. 사람의 집단을 A, 노트북의 집단을 B라고 할 때 이를 그래프로 나타내면 아래와 같다. 위와 같이 각 집단에 원하는 항목이 있을대 가장 효과적으로 매칭 시키는 알고리즘, 즉 최대 매칭(Max Matching)을 수행하는 알고리즘이다. 다시 말해서 모든 사람이 각각 노트 북을 선택하여 가장 많이 연결 되는 경우의 수를 찾는 것이다. 이는 용량(Capacity)가 1인 네트워크 플로우 문제로도 해석 할 수 있다, 다만 에드몬드 카프 알고리즘은 시간 복잡도가 O(V + E^2) 이기 때문에 이분매칭에 한해 더 빠르고 효율적인 DFS를 활용한 방법으로 구현 할 것이다. 1. 동빈은 A를 선택한다. 2. 태일은 A를 선..

위상정렬(Topolgy sort)는 순서가 정해져있는 작업을 차례로 수행 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘이다. 위상 정렬은 DAG(Directed Acyclic Graph == 사이클이 발생하지 않는 방향 그래프)에서만 사용가능하다. 여기서는 큐(Queue)를 이용하여 구현할 것이다. Ⅰ. 진입차수(화살표 받는 개수)가 0인 정점을 큐에 삽입한다. Ⅱ. 큐에서 원소를 꺼내 연결된 모든 간선을 제거. Ⅲ. 간선 제거 후 진입차수가 0이 된 정점을 큐에 삽입, 위 과정을 반복. -> 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이다 (위상정렬 불가능) 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다. #include #include #include #def..

Ⅰ. Floyd Warshall 알고리즘은 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘이다. Ⅱ. Dijkstra 알괴즘은 가장 적은 비용을 하나씩 선택했다면, Floyd Warshall 알고리즘은 '거쳐가는 정점' 을 기준으로 알 고리즘을 수행한다. 위 테이블은 '현재까지 계산된 최소 비용' 이다. 예를들어, 노드 1을 거쳐가는 경우 대각선과 1이 포함된( (1,n), (n,1) )을 제외한 부분을 갱신시키면 된다. 다시말해 x -> y 로 가는 최소비용과 X -> 1 -> Y로 가는 비용을 비교하여 더 작은 값으로 갱신시킨다. ex) D[2,3] vs D[2,1] + D[1,3] 위와 같은 방법으로 2를 거쳐가는 경우, 3을 거쳐가는 경우등을 계산하면 된다. n을 입력받아 n x..

- 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘이다. 흔히 GPS 소프트웨어에서 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. - 다익스르타 알고리즘이 다이나믹 프로그래밍 문제인 이유는 "최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다." 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 한다. Ⅰ. 출발 노드를 설정한다. Ⅱ. 출발 노드를 기준으로 각 노드의 최소비용을 저장한다. Ⅲ. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. Ⅳ. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신하고 이를 3, 4번을 반복한다. 위와 같은 그래프..

Ⅰ. 하나의 숫자가 소수인지 판별 bool isPrimeNumber(int x) { // 어떤 수 x의 "제곱근" 까지만 검사하는 것이 효과적임 int end = (int) sqrt(x); cout