전체 글
허프만 코드는 그리디 알고리즘으로 해결할 수 있는 대표적인 문제이다. 오늘은 허프만 코드가 무엇인지, 그리고 어떻게 구현하는지에 대해 알아볼 것이다. 2023.06.08 - [Computer Science/Data structure & Algorithm] - [Algorithm] Greedy Algorithm (탐욕 알고리즘) [Algorithm] Greedy Algorithm (탐욕 알고리즘) Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 ..
Greedy Algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. (위키피디아) 탐욕법 : 단계마다 최적의 선택을 하여 문제 해결을 수행하는 경험론적 알고리즘. 그리디 알고리즘은 이름에서 유추할 수 있듯이 각 단계마다 당장 가장 '좋은' 방법을 선택한다. 문제를 전체적으로 고려해 가장 좋은 것을 찾는 DP나 이진탐색과는 차이가 있다. 기본 접근법 선택 절차 (selection procedure) 특정 후보 중에 하나를 선택해 해당 방식이 주어진 문제의 해인지 결정하는 절차이다. 이때 해는 현재의 상황에서 가장..
지난번에 가방 문제가 무엇인지 알아보고 0/1 knapsack problem을 DP 로 해결하는 방법을 알아보았다. 이번에는 그 글을 이어서 fractional knapsack problem에 대해 알아보겠다. 0/1 knapsack problem 과 다른 상황이니 주의하고 글을 읽기 바란다. 0-1 knapsack 은 greedy algorithm으로 풀 수 없다. 2023.06.07 - [Computer Science/Data structure & Algorithm] - [Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용 [Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용 Knapsack problem 어떤 물건들의 집합이 주어졌..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데,..
Knapsack problem 어떤 물건들의 집합이 주어졌을 때, 가방에 담을 수 있는 최대 가치의 물건들의 집합을 결정하는 문제 Knapsack problem은 크게 2가지 유형이 있다. 0/1 knapsack problem Fractional knapsack problem (a)가 문제상황이다. (b)와 달리 (c)는 물건을 쪼개서 (20/30) 가방에 넣었다. 이렇게 쪼갤 수 있는 경우를 Fractional problem, 그러지 못하는 상황을 0/1 knapsack problem이라고 한다. 오늘은 이 중 Dynamic programming으로 해결할 수 있는 0/1 knapsack problem에 대해 자세히 알아보겠다. 2023.06.08 - [Computer Science/Data struc..
쓰레드의 이론적 이해 쓰레드의 등장배경 프로세스의 생성에는 많은 리소스가 소모되고, context switching으로 성능이 저하된다. 그리고 프로세스간 메모리가 독립적으로 운영되어 데이터 공유가 어렵다. 그래서 프로세스보다 가볍고 경량화된 프로세스인 쓰레드가 탄생했다. 위의 사진처럼 쓰레드는 완전히 독립적인 실행 흐름을 가지고 있다. 하지만 쓰레드는 아래 사진처럼 프로세스 내에 형성된다. 그래서 context switching의 부담이 덜하며, 데이터 교환이 쉽다. 쓰레드의 생성 및 실행 쓰레드의 생성 #include int pthread_create( pthread_t *restrict thread, const pthread_attr_t *restrict attr, void*(*start_routi..
10장에서는 멀티 프로세스 기반의 스트림 분리에 대해 이야기를 한 적이 있다. 2023.05.28 - [Computer Science/Network Programming] - [Network] 10. 멀티 프로세스 기반의 서버 구현 [Network] 10. 멀티 프로세스 기반의 서버 구현 프로세스의 이해와 활용 다중 접속 서버의 구현 방법들 다중접속 서버 : 둘 이상의 클라이언트에게 동시 접속을 허용하여 동시에 둘 이상의 클라이언트에 서비스를 제공하는 서버를 의미한다. mobuk.tistory.com 15장에서는 FILE 구조체 포인터 기반의 분리에 대해 이야기를 나누었다. 2023.05.28 - [Computer Science/Network Programming] - [Network] 15. 소켓과 표..
표준 입출력 함수의 장점 표준 입출력 함수의 장점과 단점 1. 이식성이 좋다. 2. 버퍼링(버퍼에 저장했다가 한꺼번에 전송하는 것)을 통한 성능 향상에 도움이 된다. 표준 입출력 함수를 이용해 데이터를 전송할 경우 소켓의 버퍼 이외의 버퍼를 통해 버퍼링이 진행된다. 시스템 함수 ( read, write ) 는 버퍼링 없이 파일 복사를 진행하고 있기 때문에 상대적으로 표준 입출력 함수가 속도가 빠르다. (300MB 이상의 파일 복사를 테스트해보면 속도의 차이를 극명하게 느낄 수 있다.) 하지만, 표준 입출력 함수도 불편함이 있다. 1. 양방향 통신이 쉽지 않다. 2. 상황에 따라서 fflush 함수(출력 버퍼 비우는 기능)의 호출이 빈번하게 등장할 수도 있다. 3. 파일 디스크립터를 FILE 구조체 포인터..
멀티캐스트 (Multicast) 멀티캐스트 데이터 전송방식과 트래픽 이점 멀티캐스트 서버는 특정 멀티캐스트 그룹을 대상으로 데이터를 딱 한번 전송한다. 딱 한번 전송해도 그룹에 속하는 모든 클라이언트가 데이터를 받는다. 멀티캐스트 그룹의 수는 IP 주소 범위 내에서 얼마든지 추가가 가능하다. 특정 멀티캐스트 그룹으로 전송되는 데이터를 수신하려면 해당 그룹에 가입하면 된다. 연결의 개념보다는 그룹에 가입한다는 개념이기 때문에 TCP 보다 UDP 소켓 기반으로 구현해야한다. 라우팅과 TTL TTL : time to live 패킷을 얼마나 멀리 보낼 것인지 결정하는 요소이다. TTL은 정수로 표현되며, 라우터를 하나 거칠때마다 1씩 감소되고 0이 되면 소멸한다. int send_sock; int time_li..
우리는 이때까지 입출력을 할 때 read와 write를 사용했다. read와 write 는 기본 C언어에서 제공하는 함수이다. 이것 말고 sys/socket.h 에서 제공하는 send, recv 함수와 sys/uio.h에서 제공하는 readv, writev 함수에 대해 알아보자. send & recv 입출력 함수 send & recv 함수 - send #include ssize_t send(int sockfd, const void * buf, size_t nbytes, int flags); - recv #include ssize_t recv(int sockfd, void * buf size_t nbytes, int flags); send & recv 함수의 옵션과 그 의미 옵션 정보는 | 연산자로 둘 이..
