공부 (145) 썸네일형 리스트형 [알고스팟] 삼각형 위의 최대 경로 개수 세기 문제 링크삼각형 위의 최대 경로 수 세기문제답안 제출통계문제 정보문제 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개 있습니다. 첫 번째는 모든 경로가 내가 선택하려고 하는 범위 내에 있어야 한다는 것이고,두 번째는 어떤 경우더라도 내가 선택하려고하는 선택지에 두 번 포함되면.. [알고스팟] Quantization 문제 링크 Quantization 문제 답안 제출 통계 문제 정보 문제 ID 시간 제한 메모리 제한 제출 횟수 정답 횟수 (비율) QUANTIZE 3000ms 65536kb 3800 1215 (31%) 출제자 출처 분류 JongMan 연습문제 보기 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 '160대 둘, 170대 둘' 이라고 축약해 표현하는 것 또한 양자화라고 할 수 있다. 1000 이하의 자연수들로 구.. [알고스팟] 원주율 외우기 문제 링크 문제 정보문제 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) 라고 한다. 주어진 수열의 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 프로그램을 작성하라.어떤 수열의 각 수가 이전의 수보다 클 때, 이 수.. [알고리즘] 동적 계획법(dynamic programming) - 2 오늘은 동적 계획법 제 2 단계를 시작하겠습니다!지난번에는 메모이제이션을 통해서 입력 값이 계산되었다면, 바로 그 값을 반환하는 것을 배웠습니다.이번에는 입력값을 어떻게하면 걸러낼 수 있을지에 대해서 한번 살펴보겠습니다. 만약, 앞에 해결한 부분의 조각들의 결과들이 뒤에 미해결된 부분 조각들에 영향을 주지 않는 문제가 있다고 합시다.(대표적으로, 수열에서 점차적으로 증가하는 부분집합의 가장 긴 개수를 찾는 LIS(longest increasing subsequence가 있습니다.) 그렇다면, 이 문제의 답은 (0~0번 까지의 답) or (0~1번 까지의 답) or (1~2번 까지의 답) 등등... + (3~5번 까지의 답) 으로 나눠서 구할 수 있습니다.(현재의 답 + solve(3,5) 의 형식으로 나.. 이전 1 ··· 13 14 15 16 17 18 19 다음
