정의

• 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

원리

• 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달
• 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결

예제

• 막대기 자르기 ( 막대기를 적절히 잘라서 가장 가격이 높게 만들어야 함)

1
2

길이(i)   0  1  2  3  4   5   6   7   8   9  10
가격(Pi)  0  1  5  8  9  10  17  17  20  24  30

• 길이가 4인 막대기로 자를 때 얻을 수 있는 최대 가격 : 길이 2인 막대기 두 개로 자름. -> 5 + 5 = 10
• 길이가 6인 막대기 : 자르지 않고 그대로
• 길이가 n인 막대기의 최대 가격 = Rn = max(Pi + Rn-i) (i는 1부터 n)
• R1 = max(P1 + R0) =1
• R2 = max(P1 + R1, P2 + R0) = 5
• R3 = max(P1 + R2, P2 + R1, P3 + R0) = 8
• R4 = max(P1 + R3, P2 + R2, P3 + R1) = 10

–> R1, R2, R3… 가 반복적으로 나옴 . 메모제이션 사용. 이전에 계산한 값들 저장.

단점

https://programmers.co.kr/learn/challenge_codes/145

풀이

1. 리스트의 값 중 최대값을 찾음

2. n이 0이 될때 까지, 그 최대값 -1

3. 최종 제곱의 합을 출력

https://programmers.co.kr/learn/challenge_codes/152

풀이

1. 두 수의 최소 공배수

   • 두 수의 곱 / 두 수의 최대공약수

2. 두 수의 최대 공약수

   

3. 10 12 14 의 최소공배수

   • (10, 12) 의 최소공배수와 14의 최소공배수

개념

유클리드 알고리즘 (from 위키백과)

- 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘.
- 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), 
- a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 
- 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 
- 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 
- 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

https://programmers.co.kr/learn/challenge_codes/153

풀이

1. 한 칸을 오르는 방법 : 1

2. 두 칸을 오르는 방법 : 2

3. 세 칸을 오르는 방법
   ​

    처음 한 칸 오르고 나머지 두 칸 오르는 방법 
   

   ​ + 처음 두 칸 오르고 나머지 한 칸 오르는 방법

4. 네 칸을 오르는 방법

    처음 한 칸 오르고 나머지 세 칸 오르는 방법
   

   ​ + 처음 두 칸 오르고 나머지 두 칸 오르는 방법

5. f(1) =1 / f(2) =2 / … / f(n+2) = f(n+1) + f(n)

개념

1. Dynamic Programming

   • 복잡한 문제를 간단한 문제로 나눠 푸는 방법.
   • 문제를 여러 하위 문제로 나눠 푼 다음, 그 결과를 이용하여 결합해 문제 해결

2. 피보나치 수열

https://www.acmicpc.net/problem/9012

풀이

1. ‘(‘ 이면 스택 push

2. ‘)’ 이면 스택 pop

3. 마지막에 스택 size 가 0 이면 VPS