1. 문제 프로그래밍 언어 C 의 큰 문제점 중 하나는 언어 차원에서 문자열 변수형을 지원하지 않는다는 것입니다. C 에서는 문자 배열로 문자열을 표현하되 \0 (NULL) 로 문자열의 끝을 지정하는데, 이래서는 문자열의 길이를 쉽게 알 수 있는 방법이 없기 때문에 여러 가지 문제가 발생하게 됩니다. void strcat(char* dest, const char* src) { // dest 의 마지막 위치를 찾는다 while(*dest) ++dest; // src 를 한 글자씩 dest 에 옮겨 붙인다 while(*src) *(dest++) = *(src++); // 문자열의 끝을 알리는 \0 을 추가한다 *dest = 0; } 이런 문제 중 하나로 문자열을 조작하는 함수들의 동작 시간이 불필요하게 커진..

1. 문제 n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다. 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다. 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다. 게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합입니다. 현우와 서하는 점수가 더 낮은 쪽이 점수 높은 쪽에 한 점 차이마다 백 원씩 주기로 내기를 했습니다. 두 사람 모두 최선을 다할 때, 두 사람의 최종 점수 차이는 얼마일까요? 2. 풀이 /* ..

1. 문제 틱택토는 3x3 크기의 게임판에서 하는 3목 게임입니다. 두 명이 번갈아가며 o와 x를 게임판의 빈 칸에 쓰되, 먼저 같은 글자를 가로, 세로 혹은 대각선으로 3개 쓰이도록 하는 쪽이 이깁니다. 예를 들어, 다음 게임판은 x가 이긴 게임판입니다. xoo .x. ..x 게임은 항상 x부터 시작합니다. 틱택토 게임판의 현재 상태가 주어집니다. 두 사람 모두 최선을 다한다고 가정할 때, 어느쪽이 이길지 판단하는 프로그램을 작성하세요. 2. 풀이 /* - canWin(board) : 게임판이 현재 board일 때, 이번 차례인 사람이 이길 수 있다면 1, 비길 수 있다면 0, 질 수 밖에 없다면 -1을 반환한다. + board를 아홉 자리의 3진수로 본다. - 함수의 반환 값 중 -1이 있으므로, c..

1. 문제 계란 한 개에 _ _ _ _ _ _ _ _ _ _ _ _ _ 웨브바짐 달러! 계획 경제의 실패로 세계 최고의 인플레이션을 자랑하게 된 공산 국가 웨브바짐에서는 하루 중에도 물가가 계속 오르기 때문에 물건의 가격을 실시간으로 바꿔야 합니다. 웨브바짐에서 가장 큰 무가베 마트에서는 그래서 위와 같이 빈 칸만 쓰여 있는 광고판을 붙여놓고 계란 가격이 오름에 따라 (정확히는 웨브바짐 달러의 가치가 추락함에 따라) 실시간으로 숫자가 크게 적힌 플라스틱 판을 빈 칸에 갈아 끼웁니다. 예를 들어 계란 한 개에 35억 웨브바짐 달러라고 하면, 3이 쓰인 판 한 개, 5가 쓰인 판 한 개, 0이 쓰인 판 여덟 개를 빈칸에 순서대로 끼우는 것이죠. 무가베 마트에서 아르바이트를 하는 종욱이는 어느 날 곤란한 손님..

동적 계획법 중 메모이제이션을 적용하는 문제들이 참 많았는데, 무슨 소리인지 제대로 이해하지 못했다. 그래서 오늘 각잡고 조사해보았다. ^_^ 1. 동적 계획법이란? 동적 계획법 (dynamic programming): 처음 주어진 문제들을 분할하고, 이로부터 본 문제에 관한 답을 도출하는 접근 방법이다. 특히 부분 문제들의 수가 기하급수적으로 증가할 때 유용하다. 동적 계획법은 여러 문제 해결에 사용되는 부분 문제에 대한 결과를 여러번 계산하는 대신, 한 번만 계산하고 이를 재활용하여 속도를 향상시킨다는 점에서 분할 정복법과 차이가 있다. 이를 위하여 각 문제의 답을 메모리에 저장해야 하는데, 이미 계산된 값을 저장해두는 메모리의 장소를 캐시(cache)라고 하며, 두 번 이상 계산되는 부분 문제를 중..