기록공간

큐란? 큐(Queue)는 사전적인 정의로 '긴 열', '대기열'를 뜻한다. 길게 늘어져 있는 줄을 생각하면 편하다. 큐(Queue)는 일상생활에서도 자주 접하게 된다. 예를 들면 극장에서 표를 사려고 길게 늘어진 사람들의 줄, 또는 도로 위에서 신호를 기다리며 길게 늘어선 차들 등이 있다. 이러한 대기열에는 한 가지 중요한 특징을 가지고 있다. 그것은 바로 '선입선출(First-In First-Out : FIFO)'이다. 새치기라는 예외적인 상황을 제외하고 정상적인 경우라면 언제나 먼저 도착한 사람이 먼저 나가게된다. 자료구조에 사용되는 큐는 이러한 줄 서기의 특징을 그대로 가지고 있다. 큐는 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조이다. 먼저 저장된 데이터가 나중..

"오직 한 개의 클래스 인스턴스만을 갖도록 보장하고, 이에 대한 전역적인 접근점을 제공합니다." (GoF의 디자인 패턴 181p) 이번 장은 어떻게 하면 패턴을 안 쓸 수 있는지를 보여준다는 점에서 다른 장과는 정반대다. 싱글턴 패턴은 의도와는 달리 득보다는 실이 많다. GoF도 싱글턴 패턴을 남용하지 말라고 강조한다. 워낙 남용되는 패턴이다 보니 이 장에서는 싱글턴을 피할 방법을 주로 다루겠지만, 그래도 우선은 싱글턴 패턴에 대해서 살펴보자. 싱글턴 패턴 GoF의 디자인 패턴에서 발췌한 싱글턴 요약을 쉼표 기준으로 나눠 각각 살펴보자. 오직 한 개의 클래스 인스턴스만 갖도록 보장 인스턴스가 여러 개면 제대로 작동하지 않는 상황이 종종 있다. 외부 시스템과 상호작용하면서 전역 상태를 관리하는 클래스 같은..

이번 장에서는 UNIX 시스템의 프로세스 생성에 관해 논의한다. UNIX는 프로세스를 생성하기 위해서 fork()와 exec() 시스템 콜을 사용한다. wait()는 프로세스가 자신이 생성한 프로세스가 종료되기를 기다리기 원할 때 사용된다. 그러면 본격적으로 이 인터페이스에 대해 예제를 통해 더 자세하게 알아보자. fork() 시스템 콜 프로세스 생성에는 fork() 시스템 콜이 사용된다. 다음 코드는 fork()를 호출하는 코드(p1.c)이다. #include #include #include int main(int argc, char *argv[]) { printf("hello world (pid:%d)\n", (int) getpid()); int rc = fork(); if(rc < 0) // for..

그리디 알고리즘 문제이다. 끊어진 (적어도)N개의 기타줄을 사기위한 최소 비용을 구하기 위해서는 우선 브랜드 별로 오름차순으로 정렬하여 가장 싼 패키지 가격과 가장 싼 낱개 가격을 각각 구해준다. N이 6이상일 경우 패키지 가격으로 살 것인지 아니면 낱개 가격을 살것인지를 먼저 정해야 한다. 전자의 경우 N을 6과 나누어 나온 값 만큼 패키지 가격을 곱하여 최종 가격에 더해준다. 그리고 만약에 나머지 사야할 기타줄이 있는 경우, 그 갯수와 낱개의 곱이 패키지의 가격을 넘는다면 패키지 가격을 최종 가격에 더해주고 아닌경우 (낱개가격 * 사야할 기타줄 수)를 더해준다. 후자의 경우에는 그냥 (낱개가격 * 사야할 기타줄 수)를 더해주면 된다. 코드는 다음과 같다. #include #include using n..

추상화의 사전적인 정의 추상의 사전적인 정의는 이고 추상화는 이다. 즉, 어떤 사물이나 대상의 공통적인 특징을 뽑아내어 표현하는 작업이라는 뜻으로 풀어쓸 수 있겠다. 쉽게 말해 '일반화'를 시킨 다고 생각하면 편할 것이다. 추상화는 컴퓨터 과학에서 뺄 수 없는 개념이다. 도대체 왜 중요한 것일까? 컴퓨터 과학에서의 추상화 컴퓨터 과학에서 추상화는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다. 우리는 추상화를 통해서 컴퓨터, 자동차, 전자레인지, 프로그래밍 언어 등에서 복잡하고 어려운 세부사항들을 무시한 채 하나의 도구, 또는 장비로 파악하여 간단하게 사용할 수 있게된다. 예를들면, 우리는 자동차의 작동원리를 몰라도 운전을 할 수 있고, 컴퓨터의 작동원리를 몰..

그리디 알고리즘 문제이다. 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 예를 들어 A의 지원자가 B 지원자보다 서류 심사나 면접시험 중 하나라도 더 높다면 선발이 되고, 둘 다 낮다면 절대 선발되지 않는다. 알고리즘은 다음과 같다. 우선 서류 전형 순위를 오름차순으로 정렬한다. 정렬 후 가장 첫번째에 있는 사원은 조건에 무조건 만족하므로 선발한다. 선발된 사원의 면접 순위를 N에 기록하고 다른 지원자들의 면접 점수를 검사한다. 만약 지원자의 면접 순위가 N보다 작은 경우 조건에 만족하므로 선발하고 순위를 다시 N에 기록한다. 코드는 다음과 같다. #include #include using namespace std; struct ..

A가 B보다 작으므로 A를 앞에서 부터 한칸씩 옮기면서 B와 검사한다. 그리고 차이가 최소로 나는 값을 출력하면 된다. 앞이나 뒤에서 추가하는 작업을 할 필요는 없다. 왜냐하면 A에 앞이나 뒤로 B와 알맞은 값을 채워 넣는다고 가정하여, 추가한 위치의 알파벳은 항상 같기 때문이다. 코드는 다음과 같다. #include #include using namespace std; int main() { string A, B; cin >> A >> B; int min = 50; int diffSize = B.size() - A.size(); for (int i = 0; i

GPU에는 명령 대기열(Command queue)이 하나 있다. CPU는 그리기 명령들이 담긴 명령 목록(Command list)을 Direct3D API를 통해서 그 대기열에 제출한다. 여기서 중요한 점은, 일단의 명령들을 명령 대기열에 제출했다고 해도, 그 명령들을 GPU가 즉시 실행하는 것은 아니라는 점이다. 명령들은 GPU가 처리할 준비가 되어야 비로소 실행되기 시작한다. 즉, GPU가 이전에 제출된 명령들을 처리하느라 바쁘게 돌아가는 동안 명령들은 그냥 대기열에 남아 있다. 명령 대기열이 비면 GPU는 할 일이 없으므로 그냥 놀게 된다. 반대로, 대기열이 꽉 차면 GPU가 명령들을 처리해서 대기열에 자리가 생길 때까지 CPU가 놀게 된다. 상황 모두 바람직하지 않다.최적의 성능을 얻으려면 최대한..