동적 프로그래밍6 #1354 무한 수열 2(Dynamic Programming) 이번 문제는 #1351과 같은 문제이지만, 숫자 범위가 좀 더 커지고, 두개의 숫자 인덱스를 계산하는 것이 좀 다릅니다. 그러다 보니 제한시간이 2초에서 10초로 대폭 늘었습니다. 난이도도 Gold IV에서 Gold III로 조금 높게 평가되었습니다. 그렇지만 똑같이 동적 프로그래밍을 이용하고 있고, 동적 프로그래밍상 히트율이 많이 낮아져서 시간이 많이 걸립니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //---------------------------------------------------------- // baekjoon #1354 - Infinity Series 2 // - by Aubrey Choi // - created at 2020-02-02 //---------------.. 2020. 2. 2. #1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19. #76 합의 경우의 수(Dynamic Programming) 이번 문제는 경우의 수를 계산하는 것입니다. 보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다. 문제는 짧은 편입니다. N이란 숫자가 주어지면, 1부터 N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다. 예를 들어서 N=5라고 한다면, \( 5 = 1 + 1 + 1 + 1 + 1 \) \( 5 = 1 + 1 + 1 + 2 \) \( 5 = 1 + 1 + 3 \) \( 5 = 1 + 4 \) \( 5 = 1 + 2 +2 \) \( 5 = 2+ 3 \) 위와 같이 총 6가지가 나옵니다. 이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다. 문제의 원본.. 2020. 1. 15. [C/C++] 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기(동적 프로그래밍) 이번 프로그램은 개인적으로도 재미있을 것 같았습니다.Project Euler의 18번 문제는 삼각형 숫자 배열에서 위에서 아래로 내려오는 경로 중 합이 최대가 되는 경로를 찾는 문제입니다.문제에서 주어진 삼각형 숫자 배열에서 맨 위 숫자에서 시작하여 아래로 내려오면서 인접한 두 숫자 중 하나를 선택하여 이동합니다. 이때, 선택한 숫자들의 합이 최대가 되는 경로를 찾아 그 합을 구하는 것이 목표입니다.가장 중요한 알고리즘은 바로 동적 프로그래밍(Dynamic Programming)입니다. 실제 경로 문제 중 최적값 찾기에는 동적 프로그래밍 기법을 자주 사용하게 되는데, 이 프로그램 역시 마찬가지입니다.해당 사이트 문제에서도 그런 점을 언급하기는 했지만,동적 프로그래밍을 사용하지 않는다면, 경로의 수가 많.. 2015. 1. 14. [C/C++] 프로젝트 오일러 #14 Longest Collatz Sequence(동적 프로그래밍) 1백만보다 작은 수 중에서, 다음과 같은 콜라츠 수열을 생성할 때 가장 긴 수열을 만들어내는 초기값을 찾는 문제입니다.콜라츠 수열은 다음과 같은 규칙으로 정의됩니다:1. 어떤 정수 n 에 대해:• n 이 짝수이면, n 을 2로 나눕니다. ( n = n / 2 )• n 이 홀수이면, n 에 3을 곱하고 1을 더합니다. ( n = 3n + 1 )2. 수열은 n = 1 이 될 때 종료됩니다.예를 들어, 초기값이 13인 경우 수열은 다음과 같이 생성됩니다:\[ 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \]이.. 2014. 12. 30. [C/C++] 프로젝트 오일러 #2 피보나치 수열의 짝수항 합(동적 프로그래밍) C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다. 피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요. 꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다. 기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. \[ F_{n} = F_{n-1} + F_{n-2} \] 점화식을 보면 아주 간단한 형태입니다. 전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서 첫번째 항과 두번째 항이 초기값으로 주어져야 합니다. 첫번째 항은 1, 두번째 항은 1입니다. 자연수 .. 2014. 12. 19. 이전 1 다음
