동적 계획법 (28) 썸네일형 리스트형 [알고스팟] 두니발 박사의 탈옥 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)NUMB3RS2000ms65536kb40171670 (41%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제위험한 살인마 두니발 박사가 감옥에서 탈출했습니다. 수배지를 붙이고 군경이 24시간 그를 추적하고 있지만 용의주도한 두니발 박사는 쉽사리 잡히지 않았습니다. d일이 지난 후에야 경찰은 프로그래밍의 천재인 찰리 교수)를 찾아왔습니다. 찰리 교수는 두니발 박사가 감옥에 남겨둔 노트를 분석해 다음과 같은 가설을 세웠습니다.두니발 박사는 검문을 피해 산길로만 이동한다.두니발 박사는 교도소를 탈출한 당일, 교도소와 인접한 마을 하나로 도망쳐 은신한다.두니발 박사는 수색을 피하기 위해 그 후 매일 인접한 마을로 움직여 은신한다.. [알고스팟] 폴리오미노 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)POLY1000ms65536kb16781071 (63%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형.. [알고스팟] 삼각형 위의 최대 경로 개수 세기 문제 링크삼각형 위의 최대 경로 수 세기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TRIPATHCNT5000ms65536kb20141122 (55%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제9 5 7 1 3 2 3 5 5 6위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다.이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, 7, 2, 6}과 {9, 7, 3, 5}의 합이 모두 최대인 24.. [알고스팟] 타일링 방법의 수 세기 문제링크 타일링문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TILING21000ms65536kb28901781 (61%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요.예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있습니다.경우의 수는 n이 커지면 아주 커질 수 있으므로, 1000000007으로 나눈 값을 대신 출력하세요.입력입력의 첫 줄에는 테스트 케이스의 수(C [알고리즘] 동적 계획법(dynamic programming) - 3 이번에는 경우의 수, 확률과 동적 계획법에 대해서 알아보겠습니다!경우의 수나 확률의 경우에도 재귀적인 특징을 많이 가지고 있기 때문에 동적 계획법을 많이 이용합니다. 대표적으로, 이항 계수를 구하는 가 있습니다! 경우의 수를 세는 것도 이전의 최적 부분 구조를 이용합니다.이전까지 어떤 경로로 왔던 상관없이, 현재 진행중인 부분부터 끝까지의 경우의 수를 센 뒤에 이 값을 반환하면,이 반환된 값을 통해 더하든 곱하든 해서 처리하는 방식이 일반적인 경우의 수를 동적 계획법으로 풀어가는 방식입니다. 이 때, 다음 경로를 선택해야할 때 고려해야할 것이 2개 있습니다. 첫 번째는 모든 경로가 내가 선택하려고 하는 범위 내에 있어야 한다는 것이고,두 번째는 어떤 경우더라도 내가 선택하려고하는 선택지에 두 번 포함되면.. [알고스팟] 원주율 외우기 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)PI1000ms65536kb51531552 (30%)출제자출처분류JongMan연습문제보기문제(주의: 이 문제는 TopCoder 의 번역 문제입니다.)가끔 TV 에 보면 원주율을 몇만 자리까지 줄줄 외우는 신동들이 등장하곤 합니다. 이들이 이 수를 외우기 위해 사용하는 방법 중 하나로, 숫자를 몇 자리 이상 끊어 외우는 것이 있습니다. 이들은 숫자를 세 자리에서 다섯 자리까지로 끊어서 외우는데, 가능하면 55555 나 123 같이 외우기 쉬운 조각들이 많이 등장하는 방법을 택하곤 합니다.이 때, 각 조각들의 난이도는 다음과 같이 정해집니다:모든 숫자가 같을 때 (예: 333, 5555) 난이도: 1숫자가 1씩 단조 증가하거나 단조 .. [알고스팟] 합친 LIS 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)JLIS2000ms65536kb4301974 (22%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다.두 개의 정수 수열 A 와 B 에서 각각 증가 부분 수열을 얻은 뒤 이들을 크기 순서대로 합친 것을 합친 증가 부분 수열이라고 부르기로 합시다. 이 중 가장 긴 수열을 합친 LIS(JLIS, Joined Longe.. [알고스팟] 최장 증가 부분 수열 LIS (longest increasing subsequence) 문제링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)LIS2000ms65536kb115273146 (27%)출제자출처분류JongMan연습문제보기문제어떤 정수 수열에서 0개 이상의 숫자를 지우면 이 수열의 부분 수열 (subsequence) 를 얻을 수 있다. 예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열의 순서와 다르므로 10 7 4 9의 부분 수열이 아니다.어떤 부분 수열이 순증가할 때 이 부분 수열을 증가 부분 수열 (increasing subsequence) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.어떤 수열의 각 수가 이전의 수보다 클 때, 이 수.. 이전 1 2 3 4 다음
