다익스트라 알고리즘은 그리디 알고리즘이며, 그리디 알고리즘이 최적해를 보장하는 몇 안되는 경우 중 하나이다. 다익스트라 알고리즘은 그래프와 시작 버텍스를 인풋으로 받아 시작 버텍스로부터 이를 제외한 모든 버텍스들로 가는 최단 경로로 구성된 spanning tree를 구성한다. 이 과정에서 시작 버텍스를 subgraph로 두고 이 subgraph를 점점 확장시킨다. 다익스트라 알고리즘은 또한 모든 노드에 대해 시작 노드로부터의 거리, 즉 distance를 저장한 테이블이 필요하다. subgraph를 확장시킬 때마다 그 인접한 노드의 distance를 줄일 수 있는지 확인하고 줄인다. 이를 relaxation이라 한다. 의사코드 def djikstra_algorithm(G, s): S = {s} # dist..
Prim algorithm 의사코드 def prim_algorithm(v): mark v as visited and include it in the m.s.t while there are unvisited verticies: find a least-cost edge(x, u) from a visited vertex x to unvisited vertex u mark u as visited add the vertex u and the edge (x, u) to the m.s.t # if needed, relax u 프림 알고리즘은 weighted graph에서 minimum spanning tree (weight 합이 가장 작은 spanning tree)를 찾기 위한 알고리즘으로, 그리디 알고리즘이 최적인..
DFS def DFS(v): mark v as visited # by array or something for unvisited_vertex in unvisted_vertices_adjacent_to_v: DFS(v) 위 재귀 구조는 함수 호출 스택을 쌓게 된다. 따라서 이 코드를 그대로 스택으로 구현할 수도 있다. 2021/03/13 추가) 코딩테스트 문제 풀 때는 실질적으로 이런 구조로 짜는게 편하다 def DFS(level, node, record): # 1. record record
graph: G = (V, E) 정점(vertex, node) - 어떤 대상물이나 개념 간선(edge) - 관계 subgraph adjacent path cycle simple path: 노드가 중복되지 않는 path simple cycle: 시작점이자 끝점인 노드 외에 어떤 노드도 중복되지 않는 cycle(다른 중복되는 노드가 있다면 그 노드가 subcycle의 시작점이자 끝점이 됨. 즉 simple cycle은 subcycle이 없음) connected cycle: 어떤 두 노드를 잡아도 그 사이에 path가 있는 그래프 complete cycle: 모든 노드 사이에 간선이 있는 그래프 directed graph(digraph) undicrected graph adjacency multigraph: ..
이 게시글은 kadamon.tistory.com/22 velog.io/@hygoogi/%EA%B8%B0%EC%88%A0-%EB%A9%B4%EC%A0%91-%EC%A7%88%EB%AC%B8-%EB%AA%A8%EC%9D%8C ko.myservername.com/top-60-networking-interview-questions github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Network 여기서 대답할 수 있을 것 같은 질문들에 대답을 써볼 것이다. 부족한 부분은 하이라이트 표시를 해놓을 것이다. 21/03/08 OSI 7계층에 대해서 설명해주세요. osi 7계층은 ISO 에서 지정한 네트워크 모델로, 위에서부터 차례대로 응용 계층, 표현..
0. ARP(address resolution protocol) 모든 호스트(IP가 부과된 노드)는 자신 내트워크 내의 호스트들에 대해 로 구성된 매핑, 즉 ARP표를 캐시에 가진다. 이 테이블을 ARP를 통해 학습한다. IP주소와 mac주소의 대응은 계속 바뀔 수 있기 때문에, 15분에 한번씩 이 표가 갱신되어야 한다. 즉 ARP는 최소한 15분에 한번은 동작한다. ARP는 다음과 같이 동작한다. 15분이 지났거나 캐시의 매핑에 없는 IP에 요청을 보낼 때 ARP 쿼리를 브로드캐스팅한다. (ARP 쿼리의 구성은 생략) 이에 모든 네트워크 내 호스트가 쿼리를 받고 해당 IP가 자기껀지 확인한다. 이들 중 자기 IP가 맞는 호스트가 자신의 mac주소를 응답해준다. 1. datagram forwarding ..
네트워크는 여러가지 요소들에 의해 만들어진다. 와이파이, TCP, HTTP, 케이블, 이러저런것들... 이들을 5개의 계층으로 나누어 설명하는 것이 TCP/IP 5계층 모델이다. 1. physical layer 말 그대로 컴퓨터와 컴퓨터를 연결하는 물리적 장치이다. 물리적인 연결, 전기 신호 변환/제어(전기회로에서 배우는 것들..)에 해당한다. 2. data link layer (여기서부터는 프로토콜이다.) 물리적인 신호를 해석하고, 물리 주소를 부여한다. 노드와 노드 사이의 통신을 담당한다. 예시로 와이파이와 이더넷이 있다. 와이파이와 이더넷은 물리적인 신호가 아니라 그것을 해석하는 프로토콜을 의미한다! 3. network layer (internet layer) 라우터를 통해 서로 다른 네트워크끼리 ..
