본문 바로가기

전체 글

 (82)
C++ 백준 11054 (가장 긴 바이토닉 부분수열) 백준 11054 (가장 긴 바이토닉 부분수열) https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net LIS를 이용하는 문제이다. 또한 LIS의 길이만 알면 된당. LIS의 길이에 대한 설명은 여기(링크)에 자세히 나와있으니 꼭 알고오자. LIS의 길이를 구하는 방법은 O(N^2)과 O(NlogN)로 구하는 두 가지의 방법이 있는데 본 글에서는 O(NlogN)방법을 이용한다. O(N^2)으로도 해봤는데 속도가 확실히 차이가 나는 것을 볼 수 있다. 밑에꺼가 O(N^2)이..
Socket Programming (소켓 프로그래밍) (1) API API란 시스템이 어플리케이션에 제공하는 인터페이스이다. API에는 여러 종류가 있는데 우리는 TCP/IP에서 쓰이는 다양한 API중 Sokcet에 대해 알아 볼 예정이다. TCP/IP에 쓰이는 API는 Socket말고도 TLK, XTI, Winsock, MacTCP등 여러 종류가 있다. Sokcet 소켓은 다섯개의 componet와 관련이 있다. 또한 아래의 함수들은 헤더파일과 헤더파일에 존재한다. 1. Protocol - 어떤 프토토콜을 사용할 건지 - socket()함수의 argument로 어떤 프로토콜을 사용할 건지 알려준다. 2. Source's address and port number - 보내는 곳의 주소와 포트넘버 - socket()함수는 socket descriptor(OS에서의 ..
CH3 : Transport Layer (5) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Congestion Control 이미 여러번 언급했지만 이번강의에서는 congestion control에 대해 자세히 알아본다. Congestion 라우터가 처리할 수 있는 용량보다 많은 packet이 들어오게 되면 congestion이 일어난다. congestion이 일어나면 크게 두가지 상황이 발생한다. 1. packet loss (라우터의 buffer가 overflow가 나서 패킷이 로스된다) 2. long delays (라우터의 queue가 매우 혼잡하여 처리과정이 느리다) 이러한 문제가 발생하지 않게 사전에 예방을 해야하는데 방법은 sendring rate를 ..
CH3 : Transport Layer (4) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Reliable Data Transfer - TCP는 SR ARQ방식과 비슷한 매커니즘을 사용한다. 그러나 SR처럼 WS를 정해놓지 않고 이 WS는 dynamic하게 변한다. 이때 이 WS는 flow control과 congestion control의 영향을 받는다. - cumulatvie ACK을 사용하고 다음에 받아야할 seq num을 보낸다 예를 들어 현재 seq num 1000번까지의 데이터를 받았다면 ack(1001)을 보낸다. - 재전송을 지원한다. timeout이 일어나면 재전송을 하는데 이때 이미 온 ACK에 대해서 똑같은 ACK이 3번오게되면 timeou..
CH3 : Transport Layer (3) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * 이전글에서는 UDP와 ARQ에 대해서 배웠다. 이번글에서는 TCP에 대해 자세하게 다룰 예정이다. TCP(Transmission Control Protocol) - 여러번 얘기했듯이 TCP는 연결지향형 프로토콜이다. 3-handshaking을 통해 상호간의 connection을 생성한 뒤 소통한다. - 1:1방식의 프로토콜이다. - full-duplex data 방식을 지원한다. full-duplex와 다른 개념에는 half-duplex, simplex가 있다. simplex : 단방향 통신, A는 B에게 또는 B는 A에게로만 통신할 수 있음 half-duplex : 양..
CH3 : Transport Layer (2) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Reliable data transfer 데이터전송을 reliable하게 하는 방식에는 두가지가 있다. 1. Forward Error Correction (FEC) - 반복되는 bit를 더해 리시버가 에러를 체크하게끔 한다. - 예를들어 센더는 1을 보낼때 111을 보내고, 2를 보낼때 222를 보낸다. 만약 111이 가는중에 에러가 발생하여 101이 도착했다면 리시버는 많이나왔던 1을 실제로 온 데이터로 받아들여 1이라고 인식한다. 2. Retransmission - 에러가 나면 재전송하는 기능이다. - ARQ(Automatic Reapeat Request)라고도 하며..
CH3 : Transport Layer (1) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * 저번 챕터2에서는 Application Layer에 대해 공부했었다. 이번 챕터부터는 그 하위레이어 Transport Layer에 대해서 공부하겠당 Transport Services 트랜스포트 레이어는 app간의 논리적인 소통을 담당한다. 이 레이어는 end system에서 작동한다. sender side : app의 메시지를 segment단위로 잘라 하위레이어인 network layer로 보낸다. receiver side : segment단위의 데이터를 message로 합쳐 상위레이어인 application layer로 보낸다. 나중에 다시 배우겠지만 네트워크 레이어는..
CH2 : Application Layer (6) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * Internet Video 최근 Netflix, YouTube등 비디오에 대한 수요가 높아지면서 이에 따른 네트워크상의 처리문제도 중요해졌다. 영상의 크기가 매우 클 경우에 하나의 서버에서는 다루기 힘들 수도 있다. 또한 각각의 유저가 가지고있는 네트워크상의 Capability가 다르기 때문에 이에 대한 처리도 고민해야한다. 때문에 distributed하고 application-level의 infrastructure가 생겨났다. Video Encoding 비디오 인코딩에는 두가지 방식이 있다. - CBR(Constant Bit Rate) : 인코딩의 rate가 고정되어있..

티스토리툴바