전체 글 (82) 썸네일형 리스트형 C++ 백준 2503 (숫자 야구) 백준 2503 (숫자 야구) https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 간단하게 브루트포스로 해결가능한 문제였다. 처음에 문제를 보고 각 스트라이크와 볼에 대해 경우의 수를 빠르게 줄여볼 방법을 생각했지만 string의 길이가 3이고 전체 수가 1000도 안된다는 점을 보고 그냥 브루트포스로 접근했다. (그래도 0ms가 나오더라..) 설명 설명이라고도 하기 쪼끔 민망하지만 설명해보자면 다음과 같다. 인풋이 세자리 string과 스트라이크,.. C++ 백준 2533 (사회망 서비스 SNS) 백준 2533 (사회망 서비스 SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 친구들간의 관계를 그래프로 표현해서 풀 수 있는 문제였다. 또한 중복되는 연산을 막기위해 DP를 사용하는데 설명에서 언급하겠다. 설명 문제 조건을 보면 얼리어답터가 아닌 사람들의 친구들은 무조건 얼리어답터여야 한다. 또한 얼리어답터가 아닌 사람들의 친구들은 얼리어답터이거나 아니어도 된다. 언뜻보면 이분그래프를 생각할 수 있지.. C++ 백준 1202 (보석 도둑) 백준 1202 (보석 도둑) https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 정렬과 우선순위큐를 이용해 풀 수 있는 문제였다. 설명 우선 가방의 크기를 오름차순으로 정렬한다. => 담긴 vector를 bag이라고 하겠다. 또한 보석의 pair를 무게에 대한 오름차순으로 우선순위 큐에 저장한다. => 해당 큐를 jew라고 하겠다. 준비를 마친 후 과정은 다음과 같다. 정렬된 가방의 크기.. 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까지의 파일을 합치는데 해당 파일들이 합쳐지기 전.. 이전 1 2 3 4 5 6 7 8 ··· 11 다음
