dynamic programming28 [C/C++] 프로젝트 오일러 #67 최대 경로의 합 난이도는 5%로 별로 높지 않은 문제입니다. 그러나 A* 알고리즘 등 기초 알고리즘을 이용해서 짤 수 있는 문제이고, 또, 많은 게임 프로그램에서 활용 가능한 문제입니다. Maximum path sum II 어떤 한 곳에서 갈 수 있는 길은 2가지이므로, 높이가 10이면, 2의 9승인 512가지의 길이 존재합니다. 이 길 중 상당부분은 부분경로가 같기 때문에, 이러한 경로의 합을 구하는 방법으로는 동적프로그래밍(dynamic programming)이라는 알고리즘 기법을 이용해서 풀면 좋습니다. 동적 프로그래밍은 메모리를 추가로 사용해야 하지만, 저는 그냥 기존의 데이터 저장공간을 그대로 사용했습니다. 그렇게 하여도 큰 문제가 없겠죠. 중간에 한 지점에 대해서 올 수 있는 경로는 최대 2가지입니다. .. 2016. 6. 30. [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 2 3 4 5 다음 728x90
