다익스트라 최단 경로 알고리즘 (Dijkstra Algorithm)

다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 알고리즘은 음의 간선이 없을 때 정상적으로 동작하는데, 현실 세계의 길은 음의 간선으로 표현되지 않는다. 이 알고리즘은 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘이라고 할 수 있다. 알고리즘은 다음과 같이 동작한다.

Socket.IO 란?

Node.js 기반으로 브라우저와 서버 간의 실시간 양방향 이벤트 기반 통신을 가능하게 하는 라이브러리이다. WebSocket을 지원하지 않는 브라우저도 지원하며 멀티 디바이스(web, android, ios, windows)를 지원하는 특징이 있다. 즉, 브라우저가 WebSocket을 지원하면 일반 WebScoket 방식으로 동작하고 간단하게 사용할 수 있도록 도와주며, 지원하지 않는 브라우저면 HTTP 롱 폴링 방식으로 대체한다.

이진탐색(Binary Search)

• 배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있음
• 탐색 범위를 절반씩 좁혀가며 데이터를 탐색함
• 시작점, 끝점, 중간점을 이용해 찾으려는 데이터와 중간점 위치에 있는 데이터 비교 반복

순환 중복 검사 (CRC, Cyclic Redundancy Check)

데이터 전송할 때 데이터에 오류가 있는지 확인하기 위한 오류 검증 기법이다. 송신 측에선 CRC 값을 데이터에 붙인 코드 워드를 전송하고, 수신 측에선 수신된 코드워드에서 CRC 값을 이용해 에러를 발견한다. 수학적 연산 과정은 복잡하지만, CRC 패키지를 활용하면 간단한다.