기록공간

푸는 과정에서도 나와있듯 큐를 이용하는 문제였다. 종료과정은 모든 트럭이 다리를 건넜을 경우이다. 그리고 다리가 견딜 수 있는 무게는 정해져 있기 때문에 모든 트럭이 줄지어서 다리를 건널 수 없다. 트럭이 다리를 건널때 견디는 무게를 넘어가면 그 트럭은 다른 트럭이 건널때 까지 기다리고 건너야한다. 과정은 다음과 같다. 다리를 건너는 트럭 정보(트럭무게, 건너는 시간)를 담을 큐 컨테이너 q, 현재 다리에 가해지는 무게를 담을 정수형 변수 w, 다리를 건넌 트럭을 담을 벡터 컨테이너 v를 선언한다. w와 다리를 건널 트럭의 무게를 더했을때 다리가 견디는 무게보다 적다면 q에 트럭 정보를 담는다. 만약 더 무겁다면 다리가 견딜 수 없으므로 그 트럭은 대기해야 한다. 현재 진행된 시간과 q의 가장 앞에 있는..

주어진 조건으로 깊이 우선 탐색을 응용하는 문제였다. 여기서 공항권은 a에서 b로 가는 것으로 그래프의 간선이라고 생각하면 된다. 이 공항권은 모두 사용해야 한다. 즉 그래프에 존재하는 모든 간선들을 지나가야 한다는 뜻이다. (마치 한 붓 그리기와 같다) 다음은 예제 2를 그래프로 표현한 것이다. 항상 인천공항에서 출발한다는 사실을 유의하자. 또한 경로가 위 그림처럼 여러개인 경우가 있을 수 있다. ICN -> ATL -> SFO -> ATL -> ICN -> SFO ICN -> ATL -> ICN -> SFO -> ATL -> SFO ICN -> SFO -> ATL -> ICN -> ATL -> SFO 다음과 같이 경로가 여러 개인 경우 알파뱃 순서가 앞서는 경로가 먼저 나오도록 해야 한다. 모든 경로..

이 장에서는 하드 디스크 드라이브에 대해 더 자세하게 알아보고자 한다. 이런 드라이브들은 수 세기 동안 대부분 컴퓨터 시스템의 영구적이 데이터 저장소였으며 파일 시스템 기술은 거의 대부분 하드 디스크 드라이브의 동작에 기반을 두고 설계되었다. 그렇기 때문에 파일 시스템 SW를 구현하기 전에 디스크의 상세한 동작을 이해하는 것이 중요하다. 인터페이스 모든 현대 드라이브의 기본적인 인터페이스는 단순하다. 드라이브는 읽고 쓸 수 있는 많은 수의 섹터(512Byte 블럭)들로 이루어져 있다. 디스크 위의 n개의 섹터들은 0부터 n-1까지의 이름이 붙어 있다. 그렇기 때문에 디스크를 섹터들의 배열로 볼 수 있으며 0부터 n-1이 드라이브 주소 공간이 된다. 멀티 섹터 작업도 가능하다. 사실 많은 파일 시스템들이 ..

평균 시간이 가장 최소가 되기 위해서는 각 작업 소요시간 순으로 처리하면 된다. 여기에는 요청이 먼저 들어온 순서도 고려를 해줘야 한다. 여기서 가장 중요한 부분은 이것이다. 이것을 놓치면 계속해서 실패가 나올 것이다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 현재 작업 시간에 들어온 작업 요청이 없다면 먼저 요청이 들어오는 작업의 시간대로 점프해야 한다. 이 공백 부분을 놓치면 이 문제는 항상 다른 결과를 반환할 것이다. 알고리즘 풀이 과정은 다음과 같다. 요청 받은 작업들을 요청 시간을 기준으로 오름차순 정렬한다. 소요시간을 기준으로 하는 최소 힙을 만든다. 현재 작업 시간 0부터 시작한다. 작업 요청 시간이 현재 작업 시간 내에 있다면 그 작업을 최소 ..

공급 받는 횟수가 최소가 되는 방법은 수량이 많은 순으로 공급 받으면 된다. 공급 받을 날짜가 되면 그 날짜의 밀가루 수량을 힙에 추가한다. (여기서 힙은 최대힙) 그리고 밀가루가 다 떨어 졌을때 힙에서 최대 수량의 밀가루를 꺼내어 공급받은 후 그 횟수를 올려주면 된다. 이 과정을 0번째 날 부터 k-1번째 날까지 반복한다면 밀가루 수량을 k날까지 맞출 수 있게된다. C++에서는 힙의 원리가 적용된 'STL priority_queue'를 제공하므로 이것을 사용하면 간편하게 문제해결을 할 수 있다. 코드는 다음과 같다. #include #include using namespace std; int solution(int stock, vector dates, vector supplies, int k) { in..

먼저 입력/출력 장치의 개념을 소개하고 운영체제가 이 장치들과 상호 작용하는 방법을 알아보도록 하겠다. 당연한 얘기지만, I/O는 컴퓨터 시스템에서 상당히 중요한 부분이다. 컴퓨터 시스템을 유용하게 쓰려면 입력과 출력이 모두 필요할 것이기 때문이다. 그러면 운영체제에서는 I/O를 어떻게 시스템에 통합하는 것일까? 시스템 구조 위는 일반적인 시스템 구조를 그림으로 표현한 것이다. 이 그림에서는 CPU와 주 메모리가 메모리 버스로 연결되어 있다. 몇 가지 장치들이 범용 I/O 버스에 연결이 되어 있는데, 많은 현대의 시스템에서는 PCI(또는 많은 파생 버스들)를 사용하고 있다. 그래픽이나 다른 고성능 I/O 장치들이 여기에 연결될 수 있다. 마지막으로, 그 아래에는 SCSI나 SATA 또는 USB와 같은 주..

한 변의 길이를 알기 위해서는 우선 타일의 수가 어떻게 되는지 먼저 살펴봐야 한다. 1, 1, 2, 3, 5, 8, ... 규칙을 제대로 살펴보면 3번째 값부터 1번째 2번째 값을 합한 값이 나온다. 점화식으로 표현하면 다음과 같다. D[i] = D[i - 2] + D[i - 1] (i >= 3) 타일의 수는 이전 값을 기반으로 하여 구하기 때문에 동적 계획법을 사용하여야 한다. 이렇게 타일의 수들을 구했다면 타일 개수에 맞는 직사각형의 둘레를 구할 수 있게 된다. 어떻게 구하면 될까? 위 문제에서는 5개의 타일로 구성된 직사각형의 둘레를 구하는것을 그림으로 표현하였다. 그림을 살펴보면 5개의 타일들 중 가장 나중과 그 이전 타일만 안다면 직사각형 각 변의 길이를 구할 수 있게 된다. 모든 변의 길이를 ..

GUI 기반 프로그램이나 인터넷 서버에서는 다른 스타일의 병행 프로그래밍이 사용된다. 이런 스타일을 이벤트 기반의 병행성(event-based concurrency)이라 한다. node.js와 같은 서버 프레임워크에서 사용되지만, 시작점은 지금부터 다룰 C와 유닉스 시스템이다. 이벤트 기반의 병행성은 두 개의 문제를 갖고 있다. 먼저 멀티 쓰레드 프로그램에서 이벤트 기반 병행성을 올바르게 사용하는 것이 매우 어렵다. 락을 누락시키거나, 교착 상태 또는 다른 골치 아픈 문제들이 발생할 수 있기 때문이다. 또 다른 문제는 멀티 쓰레드 프로그램에서는 개발자가 쓰레드 스케줄링에 대한 제어권을 전혀 갖고 있지 않다는 것이다. 개발자는 운영체제가 생성된 쓰레드를 CPU들 간에 합리적으로 스케줄링하기만을 기대할 수밖..