포도가게의 개발일지

동시성 프로그래밍이란 ? - 물리적으로는 하나의 일만 처리하지만 논리적으로 여러 일을 동시다발적으로 하는것 - 8장에서 나왔듯이 timer interrupt등 다양한 시그널들을 통하여 코어가 일을 나눠서 하게 된다. 동시성 프로그램을 만들기 위해 세 개의 기본 접근방법이 제공되며 프로세스 I/O 다중화 Thread 가 있다. 프로세스 - 8장에서 처럼 fork 등 chile process를 만들어 여러 프로세스를 만드는 기법 I/O 다중화 Thread - 하나의 프로세스 안에 여러 thread를 만들어 일을 논리적으로 동시에 처리한다. - 각 쓰레드는 고유의 정수 TID, 스택, 스택 포인터, 프로그램 카운터, 범용 레지스터, 조건 코드를 포함한 자신만의 context를 가진다. - 하나의 프로세스 안에..

클라이언트 - 서버 프로그래밍 모델 모든 네트워크 응용 프로그램은 클라이언트-서버 모델에 기초하고 있다.(한개의 서버 프로세스와 한개 이상의 client 프로세스로 구성) 클라이언트-서버 모델에서 근본적인 연산은 트랜잭션이다. 1. 클라이언트가 서버에게 요청을 보냄 2. 서버는 요청을 받고 해석 및 자신의 자원들을 적절한 방법으로 조작 3. 서버는 응답 Response를 클라이언트로 보내고 다음 요청을 기다림 4. 클라이언트는 받은 응답을 처리한다 예를들어 서버로부터 받은 page를 스크린에 디스플레이한다. 네트워크 호스트에게 네트워크는 단지 또 다른 I/O 디바이스이다. 네트워크에서 수신한 데이터는 I/O와 메모리 버스를 거쳐 어댑터->메모리로 DMA(direct memory access)로 전송된다...

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 ? 이친수를 만족하는 숫자의 개수를 찾아라 접근법 - 첫번째는 부분문자열로 일일이 다 검색을 해볼려했는데 자리수의 개수가 90인걸 보고 2**90을 볼수는 없으니 포기했다 ㅋㅋㅋ - 두번째로는 결국 종이에 써보다가 발견한 건데 신기하게도 피보나치수열을 만족한다는 것이였고 - 이 문제는 다이나믹 프로그래밍으로 연결된다 결구 f(n) = f(n-1) + f(n-2)로 문제를 풀 수 있..

ㅋㅋㅋㅋ 레드 블랙트리 항상 궁금했다 왜 알고리즘 주차 동안 트리 카테고리가 없는지 그리고 이번 주차에 깨달았다 트리중에 제일 복잡한 레드 블랙 트리를 할거니까 굳이 카테고리에 없었던 것 같다. 사실 바이너리 서치 자체가 트리 개념이고 탐색도 대부분 트리개념이긴 하지만 뭔가 트리에 대해서 좀 더 자세히 보게 된 시간이었고 depth를 어떻게 줄일까에 대한 대답으로 balanced개념이 나오고 결국 여러 밸런스트리 일종 중 제일 빡센 레드블랙 트리를 배움으로써 다른 트리 개념들을 역으로 좀 더 쉽게 만들어 버린것같다.. 근데 자꾸 레드벨벳 트리로 부르게되는데 면접에서도 레드벨벳트리로 부를까 걱정이다..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 ? 마지막 도시까지 도달했을때 최소 cost비용을 찾는 문제 접근법 - 2번째 도시로 이동할땐느 반드시 기름을 채우고 이동해야한다 - 그럼 얼마나 기름을 채우고 이동해야하나?가 문제였고 - 접근하게 일단 채우고 이동했는데 가격이 더 비싸면 첫번째에서 더 넣고 싸면 두번째에서 넣는 방식으로 접근함 import sys sys.stdin = open('inputs.text') n =..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 문제 : 가장 작은 카드 조합 만들기 접근법 - 가장 작게 만드는 문제 - 전체 카드에서 가장 작은 카드 2개를 뽑아서 더한값이 nC2 조합중 가장 작은 수의 합이다 - 그리디 알고리즘으로 접근 및 우선순위 큐를 이용하여 접근 import sys import heapq #sys.stdin = open("inputs.text") n,m = map(int,sys...

part1에서는 묵시적 가용 리스트(implicit list)에 대해 알아보았다. part2는 명시적 가용리스트에 대해 알아 보겠다. 명시적 가용 리스트(explicit list) 묵시적 가용리스트는 블록 할당 시간이 전체 힙 블록의 수에 비례하기 때문에 묵시적 가용리스트는 범용 할당기에 적합하지 않다. 더 좋은 방법은 가용 블록들을 명시적 자료구조로 구성하는 것이다. implicit list 대신 이중 연결 리스트를 사용하면 first fit 할당 시간을 전체 블록 수에 비례하는 것에서 -> 가용 블록의 수에 비례로 바꿀 수 있다. 첫번째 접근법으로는, 새롭게 반환(free)된 블록들을 리스트의 시작 부분에 삽입해서 LIFO순으로 유지하는 것이다. 두번째 접근법으로는, 리스트를 주소 순으로 관리하는것으..