나홀로 프로그래밍 공부하기

1. 최대 증가 부분 수열 실제로 출력하기 이전에 주어진 수열의 최대 증가 부분 수열(LIS)의 길이를 구하는 문제를 해결한 적이 있다. 그러나 단순히 길이만 알고 실제 LIS가 어떤 원소들로 구성되는지는 알 수가 없다. 예를 들어 S=[4, 7, 6, 9, 8, 10]의 LIS의 길이는 4라는 사실은 알 수 있지만, 실제 부분 수열을 알 수는 없었다. 그렇다면 S의 LIS인 [4, 6, 9, 10] 혹은 [4, 7, 9, 10]은 어떻게 알 수 있을까? (1) 문제 분석 및 설계 맨 처음 방법은 기존에 구현했던 lis() 함수가 LIS의 길이 대신 실제 LIS의 원소들을 담는 배열을 반환하도록 하는 것이다. 직관적이라는 장점이 있지만 모든 부분 문제마다 최적해를 저장해 메모리를 많이 차지하는 번거로운 ..

문제 출처 : algospot.com :: NUMB3RS algospot.com :: NUMB3RS 두니발 박사의 탈옥 문제 정보 문제 위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았 algospot.com 1. 완전 탐색에서 시작하기 (1) 알고리즘 설계 감옥이 있는 마을 p에서 시작해 마을 q까지 가는 길이가 d+1인 경로를 모두 생성한다. p에서 시작해 d번 인접한 마을로 옮기는 모든 경로를 생성하고, 이 중 q에서 끝나는 경로들이 출현할 확률을 계산하여 그 합을 반환한다. search(path) = path로 시작하는 모든 경로를 모두 만들고, 그 중 q에서 끝나는 것들의 출현 확률의 합을 반환 ..

문제 출처 : algospot.com :: POLY algospot.com :: POLY 폴리오미노 문제 정보 문제 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로 algospot.com 1. 완전 탐색에서 시작하기 먼저 세로 단조 폴리오미노에서 각 가로줄(행)에 포함된 정사각형들은 항상 일렬로 연속되어 있다. 따라서 각각의 가로줄마다 몇 개의 정사각형이 연속되어 있는지 결정하고 이를 좌-우로 적절하게 움직이면(세로 단조 폴리오미노의 조건을 만족하도록) 모든 폴리오미노를 만들 수 있다. 폴리오미노가 전체적으로 n개의 정사각형으로 이루어져 있다고 할 때 첫 번째 가로줄의 사각형을 1개부터..

문제 출처 : algospot.com :: ASYMTILING algospot.com :: ASYMTILING 비대칭 타일링 문제 정보 문제 그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 algospot.com 1. 문제 분석 모든 타일링 방법의 수는 8.11 단원에서 예제로 해결한 적이 있다. 대칭 타일링의 수를 쉽게 셀 수 있다면 모든 타일링 방법의 수에서 대칭 타일링의 수를 빼면 비대칭 타일링의 수를 구할 수 있다. 대칭 타일링의 수를 세는 첫 번째 단계는 n이 짝수인 경우와 홀수인 경우를 각각 나누는 것이다. n이 홀수인 경우 타일링 방법이 대칭이기 위해서는 항상 정가운..

문제 출처 : algospot.com :: SNAIL algospot.com :: SNAIL 달팽이 문제 정보 문제 깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 algospot.com 1. 비올 확률이 50%인 경우에 대해서 문제 분석 각 날마다 비가 오거나 오지 않거나 둘 중 하나이며, 가능한 m일 간 날씨의 조합은 모두 2^m가지 이다. 1일부터 m일까지 나타날 수 있는 모든 날씨 상황의 모든 조합의 수를 2^m으로 나누면 확률을 계산할 수 있다. 즉, 1일 부터 m일까지의 날씨 조합을 맑은 날은 1 비가 오면 2로 표현하여 대략 [1, 1, 1, 2, 2, ..., 1, 2] 같이..

1. 예제 : 타일링 방법의 수 세기 문제 출처 : algospot.com :: TILING2 algospot.com :: TILING2 타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있 algospot.com (1) 문제 분석 2*n 사각형을 채우는 모든 방법들은 맨 왼쪽 세로줄이 어떻게 채워져 있느냐로 나눌 수 있다. '한 개의 세로 타일에 의해 덮여 있는 방법'과 '두 개의 가로 타일에 의해 덮여 있는 방법'이 있다.. 이 때, 다음의 조건이 성립함을 알 수 있다. 1. 이 두 가지 분류는 타일링 하는 방법을 모두 포함한다. 2. 두 가지 분류에 모두 ..

문제 출처 : algospot.com :: QUANTIZE algospot.com :: QUANTIZE Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일 algospot.com 1. 문제 분석 (1) 기존의 재귀적인 해법을 찾을 수 있는가? 주어진 수열의 첫 번째 숫자를 어떤 숫자로 표현할지 결정하고, 나머지 수열에 대해 재귀 호출로 문제를 해결할 수 있을까? 이 문제에서는 양자화 표현으로 사용할 수 있는 숫자의 가짓수에 제한이 있기 때문에 지금까지 사용한 양자화 표현에 사용된 숫자를 무시할 수 없다. 이미 s가지의 숫자를 다 쓴 ..

문제 출처 : algospot.com :: PI algospot.com :: PI 원주율 외우기 문제 정보 문제 (주의: 이 문제는 TopCoder 의 번역 문제입니다.) 가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용 algospot.com 1. 문제 분석 입력의 크기가 최대 10,000인 것을 보면 완전 탐색으로 이 문제를 해결하기란 어려움 그러나 메모이제이션으로 이 문제를 해결할 수 있다. 주어진 수열을 쪼개는 모든 방법을 하나씩 만들어 보며 그중 난이도의 합이 가장 작은 조합을 찾는다. 재귀 함수는 한 번 불릴 때 마다 첫 조각의 길이를 하나하나 시도해보며 남은 수열을 마찬가지로 재귀 호출을 통해 분할한다. 첫 조각의 길이는 3,..