-
[Algorithm] Dijkstra Algorithm
Dijkstra algorithm은 한 점 (vertex)에서 모든 점까지 최단거리를 구하는 알고리즘이다. 자료구조에서는 graph 이론을 배우면서 반드시 알아야 할 내용이다. 각 vertex까지 최단거리를 구하는 과정은 다음과 같다. 초기화: 아직 방문하지 않는 vertex에 대해서는 거리는 무한대,…
-
[Algorithm] Union-Find Algorithm
Union-Find 알고리즘은 그래프 알고리즘 중 하나로 “합집합 찾기”를 위해 사용되는 대표적인 알고리즘이다. 사용되는 연산 과정은 다음과 같다. Find: x가 어떤 집합에 속해있는지 찾는 연산 Union: x와 y가 속한 집합을 합치는 연산 Example Step…
-
[Algorithm] Kruskal’s Algorithm
Introduction (including Spanning Tree) Kruskal 알고리즘이란 최소한의 비용으로 다수의 노드를 연결을 greedy하게 할 때 사용하는 알고리즘이다. 이 알고리즘은 보통 Spanning Tree를 만들 때 사용되는데, Spanning Tree란 graph 구조에서 모든 vertex가 서로 연결이 되는데…
-
[Algorithm] Cyclic Redundancy Check (CRC)
Check Sum의 문제는 data의 합이 변하지 않으면, 중간에 data들이 변하여도 error를 찾을 수 없는 문제가 있다. 따라서 이런 문제를 해결할 수 있는 방식이 CRC다. 위 그림은 3-bit CRC의 예시로, 보내는 sender쪽에서 data를 특정…
-
[Algorithm] Check Sum
Data를 전송 할 때 data의 무결성을 검증하기 위해 사용하는 기법이다. Parity bit은 단순히 1의 개수가 홀수인지, 짝수인지를 확인하는데 이 때 data가 짝수개가 변경되면 parity bit을 통해서 무결성을 검증하기 어렵다. Check Sum은 Sender 쪽에서…
-
[Algorithm] Parity Bit
데이터의 무결성을 확인하기 위한 방법 중 하나로 보내는 data의 1의 개수가 홀수인지 짝수인지 확인하여 받는 쪽에서도 동일한지 확인하는 방법이다. 예를 들면 ‘a’ ASCII data를 보낸다고 했을 때 0110_0001 (97)의 data가 전송 될 것이다.…
-
[Algorithm] Hamming Weight (Bit Count)
Data에서 1의 개수를 세는 알고리즘을 Hamming Weight라고 부른다. 여기엔 다양한 알고리즘이 존재한다. 1. Simple 위 방식의 시간복잡도는 O(n)을 가진다. 2. Hamming Weight: Level 1 위 코드는 wikipedia에 나와있는 코드를 32-bit에 맞춰서 변경해봤다. 만약…
-
[Algorithm] Find First Set (FFS) Bit
FFS는 데이터 중에 특정 bit가 1로 설정됐는지 찾는 알고리즘이다. 위 코드는 하위 비트부터 순차적으로 for loop을 돌면서 무식하게 찾는 방법이다. 만약 찾고자 하는 bit가 상위에 있다면 시간이 오래 걸릴 것이다. (시간 복잡도는 O(n))좀…
-
[Algorithm] Generic Swap and Sort
Generic Swap Swap 함수는 어디서든 많이 쓰는 함수 중 하나다. 그런데 type에 무관한 swap 함수가 필요할 수 있기 때문에 타입에 무관함 swap 함수를 소개한다.(C++에선 함수 overloading이 가능해서 동일한 함수 이름이여도 타입이 다르면 다르게…
-
[Algorithm] Knuth-Morris-Pratt (KMP) 알고리즘
효과적인 설명을 위해 notation은 다음과 같다.x: 찾고자 하는 문자열m: x의 길이y: 본문의 문자열n: y의 길이 Morris-Pratt 알고리즘은 패턴 매칭을 하는데 유용한 알고리즘 중 하나다. Shift OR 함수처럼 매칭 시작전에 lookup table을 만드는 작업이…
