1. 문제 설명 (1) 위험한 살인마 두니발 박사가 감옥에서 탈출했다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 쉽사리 잡히지 않았다. (2) d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수를 찾았고, 그는 감옥에 남겨둔 노트를 분석하여 아래와 같은 가설을 세웠다. 1 두니발 박사는 검문을 피해 산길로만 이동한다. 2 두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다. 3 두니발 박사는 수색을 피하기 위해 매일 인접한 마을로 움직여 은신한다. (3) 이 3개의 가설을 검증하기 위해 교도소로부터 산길로 연결된 N개 마을들의 지도를 아래의 그림과 같이 구했다. * ex) 지도의 3번에 교도소가 있다고 가정하면, 두니발 박사는 0번, 1번, 2번, 4번, ..

1. 문제 설명 (1) 정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부른다. (2) N개의 정사각형으로 구성된 폴리오미노들을 만들려고 하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶다. * 세로로 단조라는 뜻은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 것이다. (3) 예를 들어, 아래의 그림 (a)는 정상적인 세로 단조 폴리오미노이지만, (b)는 파란색 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아니다. * (c)는 맨 오른쪽 아래 사각형이 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아니다. (4) N개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작..

( 아래의 사이트에 나오는 알고리즘을 먼저 보는 것을 추천합니다. ) 타일링 방법의 수 세기 (난이도: 하) (tistory.com) 타일링 방법의 수 세기 (난이도: 하) 1. 문제 설명 (1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자. (2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다. (3) 예를 들어, N=5라고 kind-coding.tistory.com 1. 문제 설명 (1) 아래의 그림과 같이 2xN 크기의 직사각형을 2x1 크기의 타일로 채우려고 한다. (2) 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있다. * 단 이 타일링 방법은 좌우 대칭이어서는 안 된다. (3) 위의 그림은 2x5 크기의 직사각형을..

( 이 알고리즘은 아래 링크에 이어서 진행됩니다. ) 우물을 기어오르는 달팽이 (난이도: 하) (tistory.com) 우물을 기어오르는 달팽이 (난이도: 하) 1. 문제 설명 (1) 깊이가 N미터인 우물의 맨 밑바닥에 달팽이가 있다. (2) 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우된다. (3) 날이 맑으면 하루 kind-coding.tistory.com 1. 문제 설명 (1) 앞의 문제에서는 날이 맑거나 비가 올 확률은 동일하게 50%의 확률을 가졌다. (2) 그러나 여기서는 비가 올 확률을 50%에서 75%로 올라갔다고 가정한다. (3) 그렇다면 달팽이가 앞으로 M일 안에 우물 끝까지 올라갈 확률을 찾는 프로그램을 작성하시오. 2. 입출력 조건 및 예..

1. 문제 설명 (1) 깊이가 N미터인 우물의 맨 밑바닥에 달팽이가 있다. (2) 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우된다. (3) 날이 맑으면 하루에 2미터를 기어올라갈 수 있지만, 비가 내리면 1미터 밖에 올라가지 못한다. * 날이 맑거나 비가 올 확률은 각각 50%이다. (4) 앞으로 M일 안에 달팽이가 우물 끝까지 올라갈 확률을 찾는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 X 출력 조건 X 입력 예제 3 3 5 3 6 5 8 출력 예제 0.5 0.125 0.5 3. 제약 조건 X 4. 가정법 X 5. 기저 사례 (1) 지정한 날짜 M까지 도달한 경우 6. 코드 public class CLIMB { private static..

( 여기서 먼저 이 알고리즘을 보기전에 아래의 사이트를 먼저 학습하고 보는 것을 추천합니다. ) 삼각형 위의 최대 경로 (난이도: 하) (tistory.com) 삼각형 위의 최대 경로 (난이도: 하) 1. 문제 설명 (1) 아래의 그림과 같이 삼각형으로 배치된 자연수들이 있다고 가정한다. (2) 맨 위의 숫자에서 시작해서, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려고 한다. kind-coding.tistory.com 1. 문제 설명 (1) "삼각형 위의 최대 경로"에서는 최대 경로의 합을 구했지 경로 자체는 구하지 않았다. (2) 예를 들어, 아래의 그림 삼각형에는 세 개의 최대 경로 {9, 7, 2, 6}, {9, 7, 3, 5}, {9, 7, 3, 5}가 존재하며 합은 모두 ..

1. 문제 설명 (1) 2xN 크기의 사각형을 2x1 크기의 타일로 채우는 방법의 수를 계산하는 문제가 있다고 하자. (2) 타일들은 서로 겹쳐서는 안 되고 90도로 회전해서 쓸 수 있다. (3) 예를 들어, N=5라고 하면, 아래의 그림과 같이 여덟 가지의 방법이 있다. (4) 이때 N의 최댓 값이 100이라고 할 때 타일을 채우는 방법의 수를 찾는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C가 주어진다. (2) 그 후 각 줄에 사각형의 너비(1

1. 문제 설명 (1) 양자화(Quantization) 과정은 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. (2) 예를 들면, 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이며, 키가 161, 164, 178, 184인 학생 넷을 (160대 두명, 170대 하나, 180대 하나) 라고 축약해 표현하는 것 또한 양자화라고 할 수 있다. (3) 여기서는 1,000 이하의 자연수들로 구성된 수열을 S가지의 자연수만을 사용하도록 양자화하려고 한다. (4) 예를 들어, 수열 1 2 3 4 5 6 7 8 9 10을 두 가지의 숫자만을 써서 표현하려면, 3 3 3 3 3 7 7 7..

1. 문제 설명 (1) 원주율을 몇만 자리까지 외우는 사람들이 존재합니다. (2) 이들은 이 수를 외우기 위해 사용하는 방법 중 하나는 숫자를 몇 자리씩 끊어서 외우는 것입니다. (3) 이때 세 자리에서 다섯자리까지 끊어서 외운다고 하였을 때, 다음과 같은 난이도가 존재합니다. ( ex) 12341234 -> {123}, {41234} 또는 {1234}, {1234} 또는 {12341}, {234} ) 경우 예 난이도 모든 숫자가 같을때 333, 5555 1 숫자가 1씩 단조 증가하거나 단조 감소할 때 23456, 3210 2 두 개의 숫자가 번갈아가며 나타날 때 323, 54545 4 숫자가 등차 수열을 이룰 때 147, 8642 5 이 외의 모든 경우 17912, 331 10 (4) 원주율의 일부가 ..

( 여기서 설명하는 알고리즘은 아래의 사이트에서 LIS를 먼저 선행 후 풀는 것을 추천합니다. ) 최대 증가 부분 수열(난이도: 하) (tistory.com) 최대 증가 부분 수열(난이도: 하) 1. 문제 설명 (1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다. * 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증 kind-coding.tistory.com 1. 문제 설명 (1) 두 개의 정수 수열 A와 B에서 각각 길이 0 이상의 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부른다. * JLIS(Joined Longest Increasing Subsequenc..

1. 문제 설명 (1) 부분 순열에 포함된 숫자들이 순 증가(strictly increasing)하면 이 부분 수열을 증가 부분 수열이라고 부른다. * 순 증가란, 두 인접한 숫자 중 앞의 것이 항상 더 작을 때 수열이 순증가한다고 한다. * 단조 증가(monotonically increasing)란, 두 인접한 숫자가 같은 경우를 말한다. (2) 예를 들어, 수열 S가 '1 3 4 2 4' 라고 하면 '1 2 4'는 S의 증가 부분 수열이지만 '1 4 4'는 아니다. (3) 이때 주어진 수열에서 얻을 수 있는 증가 부분 수열 중 가장 긴 것을 찾는 프로그램을 작성하여라. * 이 문제를 최대 증가 부분 수열(LIS, Longest Increasing Subsequence)라고 부른다. 2. 입출력 조건 ..

1. 문제 설명 (1) 아래의 그림과 같이 삼각형으로 배치된 자연수들이 있다고 가정한다. (2) 맨 위의 숫자에서 시작해서, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄까지 닿는 경로를 만들려고 한다. * 경로는 아래줄로 내려갈 수 있으며 오른쪽과 아래의 숫자로 갈 수 있습니다. (3) 이때 모든 경로 중 숫자의 합을 최대화하는 경로들에 포함된 숫자들의 합은 얼마인지 찾아내는 프로그램을 작성하시오. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C(1

1. 문제 설명 (1) 와일드 카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. (2) 이때 사용하는 문자열을 와일드 카드 패턴이라고 하는데, 패턴은 일반적인 파일명과 비슷하지만 특수 문자 * 또는 ?를 포함할 수 있는 문자열이다. (3) 와일드 카드 패턴을 앞에서 한 글자씩 파일명과 비교해서 모든 글자가 일치했을 때 해당 와일드 카드 패턴이 파일명과 대응된다고 말한다. (4) 와일드 카드 패턴을에 포함된 "?"는 어떤 글자와도 대응된다고 가정하며, "*"는 0 글자 이상의 어떤 문자열에도 대응된가고 가정한다. ( 예시1) 와일드 카드 he?p는 파일명 help와 heap에 대응되지만, helpp에 대응되지 않습니다. ) ( 예시2) 와일드 카드 *p*는 파일명 help와..

1. 문제 설명 (1) 아래의 그림처럼 NxN 크기의 격자에 1부터 9까지의 정수를 쓴 게임판이 있다. (2) 이 게임의 목적은 게임판의 왼쪽 위칸에서 시작해서 게임판의 맨 오른쪽 아래칸 "끝" 쪽으로 도착하는 것이다. (3) 이때 각 칸에 적혀 있는 숫자만큼 아래쪽이나 오른쪽으로 이동할 수 있으며, 중간에 게임판 밖으로 벗어나면 안 된다. (4) 문제는 게임판이 주어질 때 시작점에서 끝점까지 도달하는 방법이 존재하는 지를 확인하는 것이다. (5) 예를 들어, 아래의 그림처럼 위의 그림에서 마지막 2를 3으로 바꾸면 방법이 없다. 2. 입출력 조건 및 예제 입력 조건 (1) 입력의 첫 줄에는 테스트 케이스의 수 C(1