23.07.18

2023. 07. 18 화요일

 

- 벨만 포드 알고리즘이란? 조건, 구현? 음수 사이클, 판별법?

: 최단 간선을 구하는 알고리즘. 음수 간선이 포함되어 있어도 가능하다.

알고리즘은 노드의 수를 간선을 중심으로 이중 for문을 돌며, 출발 지점만 가중치를 0으로 두고 나머지는 INF으로 초기화, 이후 값이 INF라면 값을 더해도 오버플로우가 나므로 continue 하며 v번만큼 원래 있던 값과 현재 가중치+간선 값이 더 작은지 판별하고 작은 값으로 수정한다. (v만큼 반복하기에 visited 방문 배열이 필요 없다.)

 

단 음수 사이클이 있으면 정상 동작하지 않으며, 매번 모든 간선을 확인하기에 다익스트라에 비해 느리다. 즉, 노드의 개수 v만큼 반복한다.

 

음수 사이클이란 사이클에서 음수 값이 더 큰 경우로, 사이클을 돌았을 때 기존 값보다 값이 작아지는 사이클을 의미한다. 음수 사이클의 판별법은 v번이 아닌 v+1번을 돌려, 값이 변화가 있다면 음수 사이클이 존재하는 것으로 판별한다. (음수 간선 순환)

 

 

- 네트워크란, 프로토콜? 범위에 따른 네트워크 종류?

: Computer Network. 컴퓨터 간의 통신을 의미. 통신에는 파일 송수신, 웹 사이트, 이메일 열람 등 여러 종류가 있다. 컴퓨터의 통신에는 규칙이 존재하는데, 이를 프로토콜이라 한다.

 

LAN(Local Area Network) - 건물 등 특정 지역 범위 네트워크 (허브)

WAN(Wide Area Network) - ISP 등이 제공하는 광역 네트워크 (케이블)

WLAN(Wireless Local Area Network) - 무선 근거리 네트워크 (LAN의 종류)

 

 

- 프로토콜의 대표 모델과 설명? 왜 층으로 구분?

: ISO(국제 표준화 기구)에서 OSI 모델을 제정. 이를 OSI 7 layer이라 한다.

이는 실제로 쓰이는 것이 아니라, 네트워크에서 이런 프로토콜이 필요할 것이다라고 표준 기능들의 스펙을 정해놓은 것. 즉, 데이터 전송을 지원할 수 있는 추상 모델을 표준화.

 

7계층으로 이루어져 있으며, 최초 보내려는 데이터에 각 계층에서 담당하는 헤더를 차례차례 붙이고 7계층을 모두 통과하면 최종 데이터를 보낸다. 쌓으므로 네트워크 스택이라 부르며, 바로 다음 계층을 무시하고 건너뛸 순 없음. 정보를 보내는 애플리케이션에선 7층부터 진행되며, 받는 애플리케이션에선 1층부터 역순으로 진행된다.

 

계층이 나뉜 이유는 층별로 프로토콜을 수정할 수 있는데, 나뉘어 있지 않다면 전체적인 코드 수정이 필요하지만, 층별로 나누어 해당 계층에서만 교체하면 인접하는 다른 계층은 수정 없이 진행할 수 있다.