왕도를 찾아서

다익스트라 알고리즘(Dijstkra Algorithm)이란, 그래프가 주어졌을 때 특정 노드 두 개 사이의 최단 거리를 찾을 수 있는 알고리즘이다. 1부: 다익스트라 알고리즘을 이용해 최단 경로 복원하기간단히 구현해보자면 다음과 같다:코드 A#include #include #include #include #define NMAX 1500using namespace std;typedef pair pii;int main(){ int v,e; cin>>v>>e; int k; cin>>k; vector rd[NMAX]; // road for(int i=0;i>u>>v>>w; rd[u].push_back(pii(v,w)); } int dis[NMAX];..

미국 NSA가 주도한 올림픽 게임 작전은, 이란의 핵무기 시설을 파괴하기 위해 내부에 '스턱스넷'이라는 바이러스를 심은 작전이다. 이 카드뉴스는 군복무 중 보안 창작물 경연대회에 제출했지만 대대 내 예선에서 탈락한 작품.

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다.전 글에서 소개한 플로이드 워셜 알고리즘의 구현을 그대로 가져오겠다. for(int x=0;x 이는 노드 a와 b를 잇는 최단 거리를 d[a][b]에 저장하는 알고리즘이다. 근데 경로 그 자체는 구할 수 없다. d[a][b]=min(d[a][b],d[a][x]+d[x][b]);이 부분을 보자.d[a][b]보다 d[a][x]+d[x][b]가 작다면 d[a][b]를 그 값으로 업데이트하는 부분이다. 무슨 뜻이냐면 기존에 a에서 b로 가는 경로보다 a에서 x를 갔다가, x에서 b로 가는 경로의 길이가 더 짧으면 그 길을 택한다는 뜻이다. 최종적으로 그 길을 택했다면 a에서 b로 가는..

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 노드들 간 최단 경로를 찾는 알고리즘이다. 일단적으로 노드 N개와 두 노드를 잇는 간선 K개가 주어지고, 특정 두 노드를 잇는 최단 거리를 찾아야 하는 상황이 주어진다.이럴 때는 다익스트라 알고리즘을 쓰면 된다. 다익스트라(데이크스트라) 알고리즘(Dijkstra Algorithm)은 두 노드 간 최단 경로를 찾는 알고리즘이다. 플로이드 워셜 알고리즘은 언제 쓰느냐?가능한 모든 두 노드들 사이 최단 거리를 구할 때 쓴다. 그러니까 하나만 구하면 될 때는 다익스트라, 모두 구해야 할 때는 플로이드 워셜을 쓴다. 다익스트라 알고리즘의 시간 복잡도는 O(KlogK)이고 플로이드 워셜의 시간복잡도는 O(N^3)이다.https://www...

드디어 마지막 계층인 응용 계층에 도달했다!  요청과 응답사용자가 URL을 입력하는 행위를 요청이라고 하고, 서버는 사용자의 요청에 응답을 한다. HTTP  프로토콜 HyperText Transfer Protocol요청과 응답을 위한 프로토콜이다. 클라이언트와 서버가 어떻게 데이터를 교환할지 정해놓은 규칙으로, 80번 포트를 사용한다. 문자 형태로 데이터가 전송된다. 그 데이터의 구조는 다음과 같다.시작 라인헤더공백(1줄)바디 body 시작 라인요청/응답이 어떤 메시지인지를 알려준다. 요청 메세지의 경우 HTTP 메서드, 경로, HTTP 버전으로 이루어져 있다. GET /index.html HTTP/1.1 HTTP 메서드데이터를 수신하는 서버에서 어떤 작업을 해야 하는지를 알려주는 용도이다. GET, P..

나는 현재 고려대학교에서 수학과를 이중전공중이다. (현재 군휴학 중) 수학과 홈페이지를 둘려보던 도중 새로운 것을 발견했다. 바로 마이크로디그리 Microdegree 제도이다.https://www.youtube.com/watch?v=jL1FJf8LHTc 2023년에 생겼다는데, 나는 오늘 처음 알았다. 수학과를 이중전공으로 택한 것은 순전히 내가 수학을 좋아하기 때문이었지만 깊이 공부하다보면 힘들다. 마이크로디그리 제도는 이중전공까지는 아니고 한 15학점 정도만 선별된 전공과목을 들으면 micro한 degree를 주는 제도이다. (크게 쓸모가 있을지는 잘 모르겠다.) https://math.korea.ac.kr/%ec%9d%b8%ea%b3%b5%ec%a7%80%eb%8a%a5%ec%9d%98%ec%88%..

휴가 나갔다 와서 오랜만에 네트워크 공부 시작. 전송 계층오류 점검 기능과 컴퓨터가 데이터를 받을 경우 어떤 애플리케이션으로 전달해야 하는지를 식별하는 기능을 한다. 오류 점검 방법에는 3가지가 있다. 1. 혼잡 제어네트워크로 들어가는 정보량을 조절해 네트워크가 혼잡해지지 않게 하는 방법이다. 수신자로부터 정상적인 ACK를 받으면 데이터 전송량을 점점 늘려가다가 타임아웃이 발생하면 데이터를 줄여서 발송한다. 2. 흐름 제어3일차의 회선 제어랑 동일한 방식이다. ACK 메세지를 받은 후에야 다음 데이터를 보내는 식이다. 3. 오류 제어- 확인 응답: ACK를 받지 못하면 오류로 판정한다.- 시간 초과: 특정 시간 내 ACK가 없으면 오류가 있다고 판단한다. (ACK가 너무 늦게 올 때)연결형 통신데이터를 ..

오랜만에 책을 폈다. 왜 바빴나 생각해보면...? 글쎄. 아무튼 오랜만에 폈다. 네트워크 계층 공부 시작. 많이 공부한 것 같은데 아직 3계층이다. 나는 일하면서 IP주소 관리 업무를 담당하고 있는데, 그 덕분에 확실히 이해가 잘 된다.IP 주소 인터넷상의 컴퓨터의 고유한 주소다. 인터넷 서비스 제공자(ISP)인 SKT, KT, LG U+ 등에게 인터넷 설치를 신청하면 공인 IP를 부여받는다. 32비트(4바이트)로 이루어져있다. 1바이트(8비트)씩 나누어 마침표로 구분해 10진수로 표기를 한다. 예시: 192.168.2.124 따라서 각 바이트는 0~255까지 값만 가질 수 있다. 다만 0과 255는 용도가 정해져있기 때문에 IP 주소로 사용하지 않는다. 이를 테면 마지막 바이트가 0인 주소는 네트워크 ..

사지방에 들어와 30분간 핸드폰을 한다. 드디어 사지방 로그인을 한다. 그리고 1시간 10분동안 핸드폰을 한다. 이렇게는 안되겠다 싶어서 드디어 책을 펼친다. 오늘은 3일차로, OSI 7계층 중 2계층인 데이터 링크 계층을 공부하겠다. 오늘부터는 임시저장 하는 습관을 들인다. 오늘도 어김없이 검색하다가 사이트를 클릭했는데 (첨보는 블로그 비슷한 사이트) 유해사이트라고 차단되어 다 날라갈 뻔 했다. 다행히 이번엔 임시저장을 해 파일을 날리지 않았다.데이터 링크 계층데이터를 관리하고 전달하는 계층이다. 여러 데이터를 동시에 전송하면 서로 충돌해 제대로 전달이 되지 않는데, 이 오류를 탐지하고 수정하는 역할을 한다. 오류를 감지하고 수정하는 데는 3가지 방식이 있다. 1. 회선 제어 통신의 시작에 ENQ(en..

오늘도 네트워크를 공부한다. OSI 7계층 중 가장 아래 계층인 물리 계층을 공부한다. 사지방에서 글쓰다가 인터넷 검색 하다가 fmkorea 사이트에 들어갔는데 유해사이트로 차단되어서 크롬창이 완전이 꺼져버렸다. 자동저장도 안 되어서 쓰던 글 전부 날아가서 화난다. 30분 동안 쓴 글 날아가버렸다. 사지방의 유해사이트 차단기능은 정말 잘못 설계되었다. 인터넷 하다가 실수로 트위터를 들어가도 크롬창이 다 강제종료된다. 트위터도 유해사이트기 때문이다. 공들여 쓴 글 처음부터 다시 쓰겠다.물리 계층 물리 계층은 컴퓨터들을 물리적으로 연결하고, 데이터를 전기 신호로 변환 및 제어한다. 데이터를 0과 1의 비트로 변환하고, 비트를 전기 신호로 변환하고, 전기 신호를 전송하고, 전기 신호를 다시 비트로, 비트를 다..