기록공간

컴퓨터의 탐색은 레코드(Record)의 집합에서 특정한 레코드를 찾아내는 작업을 말한다. 레코드는 하나 이상의 필드(Field)로 구성된다. 예를 들어, 각 학생의 정보를 이진트리의 각 노드에 저장한다고 생각해 보자. 학생정보 구조체가 레코드에 해당하고, 구조체의 멤버 변수인 학번, 이름, 주소, 주민등록번호 등이 필드에 해당한다. 레코드를 서로 구별하려면 필드들 중에서 서로 중복되지 않는 고유한 값을 가지는 필드가 있어야 하는데, 이를 키(Key)라고 부른다. 학생 정보에서는 주민등록번호나 학번이 여기에 해당된다. 결국 탐색은 주어진 키를 가진 레코드를 찾는 작업이고, 레코드가 노드에 저장되는 이진탐색트리에서는 주어진 키를 가진 노드를 찾아야 한다. 이진탐색트리의 정의 이진탐색트리(BST, Binary..

고사양 컴퓨터에만 존재했던 멀티프로세서(Multiprocessor) 시스템은 일반적이 되었으며, 데스크톱 컴퓨터, 노트북, 심지어 모바일 장치에도 사용되고 있다. 여러 개의 CPU 코어가 하나의 칩에 내장된 멀티코어(Multicore) 프로세서가 대중화의 근본 원인이다. 싱글코어 CPU의 성능 개선이 한계에 봉착하면서 멀티코어 기술이 각광을 받게 되었다. 우리는 다수의 CPU를 사용할 수 있게 되었다. 이로 인해 운영체제가 새롭게 직면한 문제는 멀티프로세서 스케줄링이다. 지금까지 다뤘던 많은 원칙들은 단일 CPU를 전재로 하고 있었다. 그러면 여러 CPU에서 동작하도록 어떻게 확장할 수 있을까? 해결해야 하는 새로운 문제는 무엇이 있을까? 배경 : 멀티프로세서 구조 멀티프로세서 스케줄링에 대한 새로운 문..

동적계획법을 사용하는 문제이다. 아래 층에 있는 수를 선택 할때에는 대각선 왼쪽과 오른쪽 중 하나만 선택이 가능하다는 조건을 상기하며 살펴보도록 하자. 층마다 저장해야 할 정수 값들이 늘어난다. 그렇기 때문에 값을 저장할때나 DP테이블로 사용할때 2차원 배열이 필요하다. 맨 위에 값은 하나이기 때문에 DP테이블에 맨 윗층은 한개의 값이 저장된다. 그리고 2층은 값이두개가 되며 맨 위층의 값과 더하여 DP 테이블에 2개의 값이 저장된다. 여기서 특성을 알수 있는데 양 사이드에 있는 값들은 무조건 왼쪽 값은 그 위층의 맨 왼쪽값과만 더할 수 있고, 오른쪽 값은 그 위층의 맨 오른쪽 값과만 더할 수 있다. 그리고 3층은 값이 세개가 되며 양 사이드 2개의 값은 위와 같은 규칙으로 더해지고, 중간 값 하나는 2..

동적 계획법을 이용하는 문제였다. 규칙을 먼저 살펴 보도록 하겠다. 1자리 -> 1 => 1개 2자리 -> 10 => 1개 3자리 -> 100, 101 => 2개 4자리 -> 1000, 1001, 1010 => 3개 5자리 -> 10000, 10001, 10100, 10101, 10010 => 5개 .... 피보나치 수열과 같은 규칙을 보이고 있다. F[i] = F[i - 2] + F[i - 1] 하지만 90자리 까지 구한다는 점에 주의를 하자. 90자리까지 표현하려면 int 범위로는 부족하기 때문이다. 코드는 다음과 같다. #include using namespace std; int main() { unsigned long long dp[90 + 1]; int input; cin >> input; dp..

동적계획법을 사용하는 문제였다. 이번 문제는 다른 문제들과 다르게 DP 테이블을 2차원 배열로 만들어줘야 한다. 한 경우(집)에 3가지 값(RGB)을 DP 테이블에 기록해야 하기 때문이다. 예를들어 어떤 집 N을 R로 칠할경우, 전 집 N - 1은 R로 칠할 수 없으므로 G와 B로 칠하는 비용중 가장 작은 비용을 찾아 N의 R로 칠하는 비용을 더해 DP 테이블에 기록하면 된다. N에서 G와 B도 위와 같은 방법으로 해주면 된다. DP(N에서 R) = DP(N - 1에서 G나 B중 가장 작은 값) + H(N에서 R) DP(N에서 G) = DP(N - 1에서 R나 B중 가장 작은 값) + H(N에서 G) DP(N에서 B) = DP(N - 1에서 R나 G중 가장 작은 값) + H(N에서 B) (DP는 DP테이..

동적계획법을 사용하는 문제이다. 2x1 크기부터 타일을 채울 수 있는 방법의 수를 그려보면 다음과 같은 결과가 나온다. 2x1 => 1개 2x2 => 2개 2x3 => 3개 2x4 => 5개 ..... 규칙을 보면 피보나치와 같다. F[i] = F[i - 2] + F[i - 1] 하지만 2x1000까지 방법의 수는 int로 표현할 수 없으며 10007를 나눈 나머지를 출력하라고 하였기 때문에 방법의 수를 10007로 나눈 값을 dp 테이블에 기록하면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int dp[1000 + 1]; int input; cin >> input; dp[0] = 0; dp[1] = 1; dp[2] = 2; for (int ..

동적계획법을 사용하는 문제였다. 규칙 계단을 오른때는 1칸 또는 2칸 오를 수 있다. 연속된 3칸을 오를 수 없다. 마지막 계단은 무조건 밟아야한다. 위 3가지 규칙을 바탕으로 마지막 계단을 밟는 경우를 두가지로 분류 해볼 수 있다. 1. 마지막 계단을 밟고 그 전 계단을 밟는 경우 (하지만 위 규칙 2번으로 인해 무조건 전 계단을 밟은 이후 전전전 계단을 밟아야 한다.) 이 경우 점화식은 S[n] = S[n] + S[n - 1]이 된다. (위 규칙 2번으로 인해 DP[n - 3]도 더해줘야 한다.) (S는 계단의 값들을 보관하는 배열이고 DP는 계단까지의 최대값을 보관하는 DP테이블(배열)이다.) 2. 마지막 계단을 밟고 그 전전 계단을 밟는 경우 이 경우 점화식은 S[n] = S[n] + DP[n -..

트리란? 트리(Tree)는 계층 구조(Hierarchical Structure)로 자료를 저장하는 자료구조이다. 여기서 말하는 계층 구조란 트리를 구성하는 노드가 부모-자식(Parent-Child) 관계라는 의미이다. 즉 특정 부모 노드 하나에 여러 개의 자식 노드들이 연결되는 구조를 말한다. 이러한 구조로 노드들이 연결된 모습이 마치 마치 나무와 같아 트리라는 이름이 붙여졌다. 그래서 앞으로 살펴 볼 용어 중 나무의 부분에 대한 명칭을 가져온 것이 있다. 예를 들어, 컴퓨터의 폴더 구조나 가족의 가계도, 직장의 조직도 등과 같이 계층적인 관계를 가진 자료를 표현하고 싶은 경우 선형 자료구조만으로 충분하지 않다. 트리는 이러한 계층적인 자료를 표현하는데 이용되는 자료구조이다. 트리의 용어들 트리와 관련된..