코딩테스트/알고리즘 (10) 썸네일형 리스트형 동적계획법 DP(Dynamic Programming) 동적계획법 - 큰 문제의 답을 얻기 위해, 작은 문제로 나누어 답을 저장하고 재활용한다. - 분할정복 알고리즘과 비슷하지만, 작은문제로 나누어 해결하고 답을 재활용하며 반복해나간다는 점에서 차이가 있다. - DP는 나누어진 모든 작은문제들을 한번씩 풀고 그 답을 저장해놓는다. 그다음 큰 문제를 위해 저장해둔 작은 문제를 활용하여 풀어나간다. - DP를 이용하려면, 작은 문제가 반복적으로 일어나야한다. Memoization - 동일한 계산을 반복하는경우, 한번 계산한 결과를 메모리에 저장해 두었다가 필요할때 꺼내쓰는 기법이다. - 일반적으로 반복계산을 했을때 메모리 할당의 중복 비용을 줄여주고, 계산에 소요되는 시간 비용을 줄여준다. - DP의 핵심기법 DP 의 예시) 피보나치수열 피보나치 수열 fib(n.. 최대공약수와 최소공배수 Swift 최대공약수 GCD 두 자연수의 공통된 약수 중 가장 큰 수 ex) 30 과 45 의 최대공약수는 15 최소공배수 LCM 두 자연수의 공통된 배수 중 가장 작은 수 최소공배수 = 두 자연수의 곱 / 최대공약수 ex) 6과 10의 최소공배수는 30 유클리드 호제법 2개의 자연수 a,b에 대해 (a > b) a를 b로 나눈 나머지를 r이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다 이 성질을 이용해, b를 r로 나눈 나머지를 r0라 하고, r을 r0으로 나누는 과정을 반복해서 나머지가 0일때 나눈수가 a와 b의 최대공약수가 된다. func gcd(num1: Int, num2: Int) -> Int { if num2 == 0 { return num1 } else { return gcd(num1:.. 이전 1 2 다음