기록공간

재귀 또는 순환이란 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 재귀는 많은 문제들을 해결하는데 독특한 개념적인 해결책을 제공한다. 재귀를 이용하여 만든 재귀 함수는 어떻게 문제를 풀어가는지에 대해 직관적으로 알 수 있도록 해주어 가독성을 높인다는 장점이 있다. 하지만 단점도 존재한다. 함수를 호출하면 그 함수가 끝날때 어디로 복귀해야 한다는 복귀주소를 스택에 쌓게 되는데, 재귀함수는 재귀하는 횟수가 많아 질수록 이 쌓이는 복귀주소가 기하급수적으로 늘어나게 된다. 이로인해 스택 오버플로우가 발생하면 프로그램이 뻗는 현상이 나타난다. (이를 해결하기 위해 동적 계획법(Dynamic Programming)이라는 알고리즘을 사용한다) 재귀는 트리 구조에서 정말 많이 사용..

컴퓨터의 탐색은 레코드(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 -..