본문 바로가기

분류 전체보기

 (87)
C++ 백준 1339 (단어 수학) 백준 1339 (단어 수학) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 설명 간단한 정렬로 풀 수 있는 문제였다. 각 자리수에 대해 가중치를 두고 그 가중치를 정렬한 뒤에 가중치가 높은 알파벳부터 9~1까지 차례대로 주면 된다. 예시를 살펴보자 ABB CAD 라는 두 수를 합친다고 가정해보자. 그러면 (100+10)*A + (10+1)*B + 100*C + D 가 될 것인데, 수가 가장 크려면 자신앞에 붙은 상수값이 가장 큰 알파벳에..
CH4 : Network Layer (2) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * IPv4 Addressing 각 인터넷 host들은 universally하게 uinque한 IP 주소를 가지고 있다. 라우터와 Layer1 (피지컬 레이어)사이에 있는 인터페이스를 NIC라고 한다. (Network Interface Card) IP는 이 인터페이스의 포트에 적용된다. 한 라우터에 여러개의 호스트가 접근해야 하기 때문에 Multi-homed라고 한다. 여러개의 IP가 접근해 오는 포트를 IP로 구분할 수 있다. IP주소는 계층적 구조를 가진다. network number + host number (총 32비트)로 이루어져 있는데, 같은 network에 존재..
CH4 : Network Layer (1) * 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. * 네트워크 레이어 목적지 IP를 base로 하여 host to host간의 패킷 전송을 담당한다. 네트워크 레이어에는 두가지 기능이 있다. 1. Data plane (데이터 전송 담당) - fowarding : 현재 라우터에서 적당한 라우터로 패킷을 어떻게 전송할 것인가? - Per-router fucntion : local의 하나의 라우터에서만 작동한다. 2. Control plane (전송 제어 담당) - routing : source로부터 destination까지 패킷의 route를 어떻게 결정할 것인가? - Network-wide function : Data pla..
Socket Programming (소켓 프로그래밍) (2) 지난 글에서는 server와 client의 연결, 그리고 메시지를 보내고 받는 함수들에 대해서 알아보았다. 본 글에서는 앞서 배운 과정과 함수들을 이용하여 직접 통신해보는 프로그램을 구현한다. 지난 글에서 알아본 과정은 다음과 같다. 만약 과정이 이해가 안된다면 이전글(링크)를 통해 이해하고 오자. TCP 다음 코드들은 메시지를 보내는 예시코드이다. TCP 서버코드 #define BUFSIZE 1024 void error_handling(char *message); int main(int argc, char **argv){ int serv_sock; int clnt_sock; char message[BUFSIZE]; int str_len; struct sockaddr_in serv_addr; struct..
C++ 백준 11066 (파일 합치기) 백준 11066 (파일 합치기) https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 전형적인 DP식 문제이다. 문제들을 풀면서 느낀 점인데 뭔가 문제를 보고 딱 떠오르는 알고리즘이 없으면 구현/DP인 것 같다. 설명 2차원 DP를 선언한다. dp[i][j]는 i부터 j파일까지 합쳤을 때 최소비용이다. 그렇게 되면 d[i][i] = 파일 i의 크기가 될 것이다. 아이디어는 다음과 같다. i~j까지의 파일을 합치는데 해당 파일들이 합쳐지기 전..
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를 ..

티스토리툴바