다이나믹2 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍은 동적계획법이라고도 불리며 짧게 DP라고 많이 사용합니다. DP의 중점은 "작은 문제를 해결하고 이를 이용해 큰 문제를 해결하자 / 큰 문제를 작은 문제로 쪼개서 해결하자."입니다. DP를 배우지는 않으셨더라도 피보나치 수를 재귀로 구하는 방법은 한번쯤 들어보셨을 거라 생각합니다. 이를 DP를 사용하는 방법으로 한 번 바꿔보겠습니다. int fibo(int n){ if(n==1 || n==0) return n; return fibo(n-1) + fibo(n-2); } 일단 기존 방법의 재귀 소스코드는 위와 같습니다. 4번째 피보나치 수를 구하려면 위와 같이 함수를 호출하게 되는데 2번째 피보나치 수를 구하는 함수를 중복해서 호출하게 됩니다. 2번째 피보나치 수는 상황에 따라서 변하는 .. 2020. 2. 22. 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31. 이전 1 다음
