왕도를 찾아서

다익스트라 알고리즘(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..

https://www.acmicpc.net/problem/33489  xA_i 를 x와 y에 대해 표현하면... 직접 써보자. A_0 = xA_1 = yA_2 = x - yA_3 = -x + 2yA_4 = 2x - 3yA_5 = -3x + 5yA_6 = 5x - 8y..... 규칙이 보이는지? x와 y의 계수는 피보나치 수열의 숫자들이다.x/y=R이라고 두자.그럼 A_i>0일때마다 1점을 얻으니,0점: x>0 (당연한 소리)1점: y>0 (당연한 소리) x와 y 값에 상관없이 1점은 기본으로 받을 수 있다. 계속해보겠다. 2점: R>1/13점: R4점: R>3/25점: R6점: R>8/57점: R8점: R>21/13.....역시나 규칙이 보인다.R값은 홀수번째 연속된 두 피보나치 수의 비율보다 작아야 하..

나는 현재 고려대학교에서 수학과를 이중전공중이다. (현재 군휴학 중) 수학과 홈페이지를 둘려보던 도중 새로운 것을 발견했다. 바로 마이크로디그리 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인 주소는 네트워크 ..