CS (27) 썸네일형 리스트형 [Lecture] Socket programming Socket programming? * socket programming reference : TCP/IP 소켓 프로그래밍 - C버전, Michael J.Donahoo, 박준철 번역 os에서 제공하는 서비스를 이용하기 위해 인터페이스를 사용해야한다. 다른 컴퓨터의 두 process사이의 소통을 위해선 socket이라는 api가 필요하다. 응용 프로그램과 네트워크 간의 인터페이스 응용 프로그램이 소켓을 만든다 소켓 유형은 통신 스타일을 지시한다 reliable vs. best effort connection-oriented vs. connectionless Two essential types of sockets 소켓의 통신 유형에 따라 두가지로 나뉜다. (TCP, UDP) SOCK_STREAM TCP so.. [Lecture] 애플리케이션 계층 지난시간 핵심 : packet 한묶음으로 같이 다닌다. 많은 사용자가 라우터에게 packet을 주면 queue에 쌓이고(delay) 넘치면 drop돼서 데이터가 유실된다 (인터넷 손실의 90% 차지) 차량 1대가 1bit이다 packet (10bit) 한묶음으로 데이터가 간다. packet앞쪽이 router에 먼저 도착했다고 해도, 뒤가 도달하지 못하면 기다린다. (다 도착하면 이동한다) 이게 packeting switching이다. network 계층 = network 기능이 있는 process 각 계층 안 다양한 프로토콜 존재 (대표적인 예만 작성) Application Layer HTTP Transport Layer TCP/UDP Network Layer IP Data Link Layer WIFI/.. [Algorithm] brute force, 시간복잡도 문제풀이 고려사항 1. 제한된 메모리와 시간 2. 알고리즘 시간복잡도 문제에서 제시된 입력의 크기와 프로그램의 수행시간과의 관계를 나타내는 함수 Big-O(빅-오) : 상한 점근 (가장 느리게 실행될 때)을 이용해서 시간복잡도 표현 간단하게 생각하면 최고차항의 차수 또는 지수의 밑이 중요하다 1초 = 10^9 Bruteforcing 모든 경우의 수를 확인해보는 방법 빠른 입출력 - main 아래에 구문 적기 cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); - 이 경우 scanf, printf 혼용 X cin, cout만 사용하기 - endl(버퍼를 비운다)대신 개행문자 '\n' 사용하기 1) 블랙잭 BOJ 2798 주어진 배열에서 M을.. [Lecture] SCC SCC : Strongly Connected Component Connecte Component는 undirected graph에서 존재한다 SCC는 directed graph에서 임의의 두 정점에 대해 양방향으로 가는 경로가 모두 있을 때, 존재한다 즉, 모든 노드가 양방향으로 reachable한 노드의 최대한 키운(Maximal Subset) 집합이다 //SCC는 사이클이 한 개 이상 겹쳐진 형태를 띤다. 하나의 정점도 SCC가 될 수 있다 [참고] Directed graph : 문제를 해결한 알고리즘이 나왔을 때, 같은 방향으로 undirected graph에도 적용시켜 해결할 수 있다 Undirected graph : undirected graph에서 해결한다고 해서 directed graph가 .. [Lecture] BCC Biconnected Component (maximal set) Biconnected Graph : 임의의 한 노드를 제거해도 나머지 모든 노드들이 연결되어 있는 그래프이다. 따라서 biconnected graph에는 cv가 존재하지 않는다 (무방향 그래프에서 정의되는 개념이다) Biconnected Component : cv에 의해 끊어진 그래프들의 각 부분을 의미한다 BCC 내의 임의의 두 노드는 완전히 다른 (edge와 node가 겹치지 않는다) 2개 이상의 경로가 존재한다 cv가 있으면, 그래프 전체가 BCC가 아니다(정의와 모순됨) 기본적으로 cycle을 BCC라고 한다 cv가 있었는데, 사라지면 연결이 끊기는 것이므로 BCC상태가 아니다 * cv는 여러 BCC에 걸쳐있다 * cv가 아닌 노드는.. [Lecture] Cut Vertex Cut Vertex 전제 : 전체가 연결된 graph가 있다고 했을 때 (일부분을 봐도 되지만, 여기선 그냥 전체를 전제로 한다) Cut vertex를 버리면, graph가 disconnected graph가 된다 x와 y가 존재한다고 하자 x에서 y로 가는 모든 path가 s(Cut vertex)를 통해서 간다 그래프에서 Cut Vertex를 어떻게 찾을 수 있을까? - 노드를 하나씩 빼보면서 disconnected graph가 되는지 확인한다 각 노드(N)에 대해 DFS를 한다(M+N) = O(N(M+N)) = O(MN) Cut Vertex => cv로 대체한다 Idea1 child가 하나일 땐, parent는 cv가 아니다 왜냐하면, 하나의 노드가 사라진다고 해도, connected graph를 유.. [Lecture] Graph Traversal 특정 노드(x) 하나가 없어지면, 그래프가 끊어질 때, 특정 노드(x)를 구하는 방법은 무엇일까? 방향이 없으면 힘들어진다 다익스트라는 소스에서 가까운 것부터 방향을 만들어가면서 해결한다 보통 방향을 정한 다음에 늘려가면서 구한다 local과 global 정보가 섞여 들어오면서 문제를 풀게된다 다익스트라에선 빨간색이 최종답이었다 위 그림에서 30 입장으로 인접한 노드들을 바라봤을 때, 35,38,40이라는 정보를(local)알 수 있다 global 정보는 파란 것 중에서 가장 작은 것을 뽑는 것이다 global정보가 간단할수록 쉽게 풀린다 다익스트라는 traversal로 볼 수 있다 Traversal어떤 순서에 따라 그래프의 노드를 방문한다 일반적으로, 해당 노드에서 연산을 하면 방문했다고 표현하고, 지.. [Lecture] 컴퓨터 네트워크 기초 ARPAnet (알파넷) - 미국 국방부에서 관련 기간의 정보 공유를 위해 개발한 컴퓨터의 연동망 - 최초로 컴퓨터간의 네트워크 통신이 연결돼 Packet 교환을 성공한 기술 - 4개의 호스트 컴퓨터를 연결하는 네트워크로 구축 현재의(개념적인) 인터넷 모습 - 노드 개수를 셀 수 없다 - 계속 팽창하고 있다 인터넷 상에서 우리의 위치는? 가장자리 (Internet edge) // 사용자는 노트북을 열고 닫으며 인터넷 접속을 기호에 따라 할 수 있다. Web Server도 가장자리에 포함된다. // 일반적으로 사용자와 서비스 사이에서 데이터 교환 및 처리가 가장 활발히 일어나는 지점으로 생각한다. 인터넷 상에서 가운데(Internet core)는? Router * 메세지를 전달받아 목적지까지 옮기는 기능 .. 이전 1 2 3 4 다음
