기록공간

동작 원리 이번에는 응용 소프트웨어, 시스템 소프트웨어, 하드웨어를 아울러 컴퓨터가 켜지고, 프로그램이 실행되는 과정을 정리한다. 컴퓨터가 켜지는 과정 CPU는 컴퓨터에 전원이 들어오면 제일 먼저 메모리의 0번지 주소의 데이터를 읽는다. 메모리의 0번지에는 ROM(Read-Only Memory)이라는, 컴퓨터를 구동하기 위한 기본 정보가 담긴 메모리가 있다. ROM은 컴퓨터의 전원을 꺼도 메모리가 지워지지 않아, 컴퓨터가 켜지면 이 곳의 정보를 읽어올 수 있다. 따라서 전원이 켜지면 ROM에서 읽어 들인 내용을 바탕으로 하드웨어의 상태를 확인하는 POST(Power On Self Test)를 수행한다. 그리고 운영체제를 로드하기 위해 디스크의 첫번째 섹터인 마스터 부트 레코드(Master Boot Rec..

컴퓨터 하드웨어는 아주 단순한 저수준의 명령어만을 실행할 수 있다. 오로지 0과 1로 이루어진 저수준 명령어를 기계는 알아듣고 수행할 수 있다. 따라서 사용자들이 일반적으로 사용하는 복잡한 응용 프로그램(소프트웨어)은 사실 하드웨어에서 실행되기 위해 번역의 과정을 거친다. 높은 수준의 작업을 저수준의 명령어로 번역하는 여러 단계의 과정에는 시스템 소프트웨어가 필요하다. 이러한 소프트웨어들은 계층적으로 구성된다. 크게 하드웨어와 응용 소프트웨어로 구분할 수 있고 이 사이에는 여러 가지 시스템 소프트웨어가 존재한다. 1. 사용자가 컴퓨터를 켜서 사용하는 프로그램들 = 응용 소프트웨어 2. 응용 소프트웨어가 하드웨어에서 실행되도록 만드는 소프트웨어 = 시스템 소프트웨어 3. 실제 소프트웨어가 실행되는 곳 = ..

파일과 디렉터리 저장 장치의 가상화에 대한 두 가지 주요 개념이 개발되었다. 첫 번째는 파일이다. 파일은 단순히 일거나 쓸 수 있는 순차적인 바이트의 배열이다. 각 파일은 저수준의 이름을 갖고 있으며 보통은 숫자로 표현되지만 사용자는 그 이름에 대해서 알지 못한다. 이 저수준의 이름을 아이노드번호(inode number)라고 부른다. 앞으로 이 아이노드번호에 대해서 더 자세히 살펴볼 것이다. 대부분 시스템에서 운영체제는 파일의 구조를 모른다. (예를 들면 어떤 파일이 그림인지, 또는 C 코드인지) 파일 시스템의 역할은 그러한 데이터를 디스크에 안전히 저장하고, 데이터가 요청되면 처음 저장했던 데이터를 돌려주는 것이다. 하지만 이렇게 하는 것은 보기보다 쉽지 않다. 두 번째 개념은 디렉터리이다. 파일과 마..

이번 글에서는 Redundant Array of Inexpensive Disk 또는 RAID라고 더 잘 알려진 기술을 소개한다. 이 기술은 여러 개의 디스크를 조화롭게 사용하여 고속이면서 (디스크의 일부가 고장나더라도) 대용량의 신뢰할 수 있는 디스크 시스템을 가능케한다. RAID란? 외면적으로는 RAID는 하나의 디스크처럼 보인다. 읽거나 쓸 수 있는 블럭의 그룹으로 보인다. 안을 들여다보면 RAID는 여러 개의 디스크와 메모리, 시스템을 관리하기 위한 하나 또는 그 이상의 프로세서로 이루어진 복잡한 기계이다. RAID의 하드웨어는 컴퓨터 시스템과 매우 유사하며 디스크의 그룹을 관리하기 위한 전용 시스템이다. RAID는 단일 디스크에 비해 여러 장점들을 제공한다. 그 중 하나는 성능이다. 디스크 여러 ..

문제 N개의 배열 A에서 0 A[R], A[Q] + A[R] > A[P], A[R] + A[P] > A[Q]. 1을 출력하고 모든 경우에서 위 조건을 만족하지 않는다면 0을 출력하면 되는 문제이다. 해결 방법 우선 위와 같은 방법을 직접 적용하여, 모든 인덱스 경우에서 조건을 만족할때까지 찾는 방법이 있다. 예를 들면 (0, 1, 2), (1, 2, 3), ..., (0, 2, 3), ..., (N - 3, N - 2, N - 1) 모든 경우의 인덱스를 검사하며 위 조건을 만족하는 것을 찾으면 바로 1을 리턴하는 것이다. 하지만 이 방법은 삼중 반복문을 사용하므로 시간복잡도가 O(N^3)이다. 즉 최대 10만개의 배열 크기를 처리하기에는 매우 비효율적인 알고리즘이다. 우선 이것을 해결하기 위해서는 정수를..

문제 N개의 배열에 각 디스크의 반지름 크기 값이 들어 간다. 그리고 0 ~ N-1 까지의 인덱스 범위가 디스크의 위치가 된다. 디스크끼리 서로 교차하는 경우 그것을 한 쌍으로 본다. 이러한 쌍이 몇개 있는지 구하는 문제이다. 해결 방법 우선 처음으로 시도했던 방법은 각 디스크 별로 순회하며 다른 디스크끼리 서로 교차하는지 검사한 후, Heap에 집어넣어 중복값을 배제하고 Heap 크기만큼 출력하는 방법이다. 하지만 디스크를 검사할때마다 그 디스크를 제외한 모든 디스크를 검사하기 때문에(이중 반복문) O(N^2)의 시간 복잡도가 나왔다. 이 방법은 역시 효율성이 안좋기 때문에 통과할 수 없었다. 최소 O(NlogN)이하는 되어야 통과가 가능하다. 위 예제에 있는 디스크들의 모양을 다음과 같이 표식화 시켜..

구간 합(Prefix Sum)이란? 만약 N개의 정수형 배열이 있다고 가정했을 때, 부분 합은 0 ~ (N - 1)까지의 합을 의미하는 것이고, 구간 합은 a ~ b (0

문제 N개의 정수를 담은 컨테이너가 주어진다. 그리고 0 (2 + 2) / 2 => 2 일때 가장 작은 평균값이 나오기 때문에 답은 P = 1 이다. 해결 방법 단순하게 위의 방법을 코드로 구현하여 접근한다면, 효율성이 떨어지게 된다. 이때 시간 복잡도는 O(N^2)이 나온다. O(N)이 나와야 효율성에서 통과가 되기 때문에, 다른 방법을 생각해야 한다. 평균값의 원리를 잘 알고 있다면, 다른 방법을 사용해 볼 수 있다. 평균값은 항상 평균값을 계산할 숫자중에 가장 작은 값보다 크거나 같다. 예를들어 (1, 2, 3)이 있다면 (1 + 2 + 3) / 3 = 2로 가장 작은 값인 1보다 크다. 이 뜻은 최소 범위에서의 평균값을 알고 있다면, 그 이후 범위의 평균값은 구할 필요가 없다는 것이다. 예를들어 ..