알고리즘 (104) 썸네일형 리스트형 [알고스팟] 최장 증가 부분 수열 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) 의 형식으로 나.. [알고스팟] 삼각형 위의 최대 경로 문제 링크 삼각형 위의 최대 경로문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)TRIANGLEPATH5000ms65536kb51662592 (50%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제6 1 2 3 7 4 9 4 1 7 2 7 5 9 4위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.입력입력의 첫 줄에는 테스트 케이스의 수 C(C [알고스팟] 와일드카드 문제링크 Wildcard문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)WILDCARD2000ms65536kb68572050 (29%)출제자출처분류JongMan연습문제보기문제와일드카드는 다양한 운영체제에서 파일 이름의 일부만으로 파일 이름을 지정하는 방법이다. 와일드카드 문자열은 일반적인 파일명과 같지만, * 나 ? 와 같은 특수 문자를 포함한다.와일드카드 문자열을 앞에서 한 글자씩 파일명과 비교해서, 모든 글자가 일치했을 때 해당 와일드카드 문자열이 파일명과 매치된다고 하자. 단, 와일드카드 문자열에 포함된 ? 는 어떤 글자와 비교해도 일치한다고 가정하며, * 는 0 글자 이상의 어떤 문자열에도 일치한다고 본다.예를 들어 와일드 카드 he?p 는 파일명 help 에도, .. [알고스팟] 외발 뛰기 문제링크 외발 뛰기문제답안 제출통계문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)JUMPGAME3000ms65536kb86743140 (36%)출제자출처분류JongMan알고리즘 문제 해결 전략보기문제땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문.. [알고리즘] 동적 계획법(dynamic programming) - 1 오늘은 동적 계획법에 대해서 설명하겠습니다.동적 계획법은 분할 정복과 유사합니다.동적 계획법 또한, 문제를 더 작게 나눈 다음에 각 조각의 답을 구한 뒤에 이 답들로부터 원래 문제에 대한 답을 계산하기 때문입니다.다만, 동적 게획법의 부분 문제는 두 개 이상의 부분 문제를 푸는데 사용될 수 있습니다!따라서, 해당 부분 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 다시 사용해서 속도의 향상을 가져올 수 있습니다.이를 위해서, 각 부분 문제의 답을 메모리에 저장하는 방식을 취합니다!!이를 메모이제이션 (memoization) 이라고 합니다. 여담이지만, 메모이제이션을 메모리제이션과 햇갈리는 경우가 굉장히 많습니다! 실은 저도 최근에서야 메모리제이션이 아니라 메모이제이션인걸 알았습니다.... [분할정복/카라츠바 알고리즘] 곱셈 최적화! 카라츠바 알고리즘에 대해 알아보자 기본 단계 카라추바 알고리즘의 기본 단계는 큰 두 수 x와 y의 곱을 자릿수가 x, y의 절반인 수들의 곱 3번과 덧셈과 시프트 연산을 이용해 계산하는 것이다. x와 y를 B진법의 n자리수라고 하자. n보다 작은 양수 m에 대해 다음과 같이 x, y를 쪼갤 수 있다. x = x1Bm + x0 y = y1Bm + y0 (단, x0과 y0는 Bm보다 작다.) z2 = x1y1 z1 = x1y0 + x0y1 z0 = x0y0 라고 할 때, x와 y의 곱은 xy = (x1Bm + x0)(y1Bm + y0) = z2 B2m + z1 Bm + z0 이 식은 4번의 곱셈을 해야한다. 카라추바는 덧셈을 몇 번 함으로써, xy를 3번의 곱셈을 통해 구할 수 있다는 걸 알았다. z2 = x1y1 라 하자. z0 = x0y.. [알고스팟] 팬 미팅 문제 링크 문제 정보문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)FANMEETING15000ms65536kb4020560 (13%)출제자출처분류YongrokRUN Programming Contest, Fall 2009보기문제가장 멤버가 많은 아이돌 그룹으로 기네스 북에 올라 있는 혼성 팝 그룹 하이퍼시니어가 데뷔 10주년 기념 팬 미팅을 개최했습니다. 팬 미팅의 한 순서로, 멤버들과 참가한 팬들이 포옹을 하는 행사를 갖기로 했습니다. 하이퍼시니어의 멤버들은 우선 무대에 일렬로 섭니다. 팬 미팅에 참가한 M명의 팬들은 줄을 서서 맨 오른쪽 멤버에서부터 시작해 한 명씩 왼쪽으로 움직이며 멤버들과 하나씩 포옹을 합니다. 모든 팬들은 동시에 한 명씩 움직입니다. 아래 그림은 행사 과정의 일부를 보여줍.. 이전 1 ··· 9 10 11 12 13 다음
