[Algorithm - DP] Dynamic Programming 이란 (Programmers - N으로 표현)

1. 동적계획법 (Dynamic Programming)

• 문제에 답인지를 확인하기 위해 탐색해야하는 범위를 동적으로 결정하면서 탐색 범위를 한정할 수 있음
  (탐색범위가 굉장히 넓은 문제에서 범위를 조금 씩 좁혀가며 해를 찾을 수 있음)
• 주어진 최적화 문제를 재귀적인 방식을 이요해 작은 부문으로 나누고 해를 조합해 전체 문제의 해답에 이르는 방식임

 

2. DP의 적용 예 - 피보나치 수열

• 피보나치 수열 : 직전 두 열의 항이 해당열의 값이 되는 수열

• f(4)를 구하기 위해 재귀함수로 구현할 경우 복잡도는 지수함수의 형태로 엄청나게 증가한다.

• 동적계획법으로 구현 시 부분문제에 대한 답을 구해놓고 그 답을 이용해서 큰 문제를 풀어가면서 해를 찾아간다.
• 복잡도는 선형함수의 형태로 나타나게 된다. 

3. Programmers - N으로 표현

https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

 

• 문제 해결 과정

1. N = 5 일 때 N을 1번만 사용할 경우, 2번 사용할 경우를 구함 (2를 구하면 55, 10(5+5), 0(5-5), 25(5x5), 1(5/5) 이 나옴)

2. N을 3번 사용할 경우 1번 값과 2번 값을 연산 해서 값을 구해준다.

(+, - 연산 시 중복된 값이 나와 제외해 줘야함 ex. 5 + 55 , 55 + 5)

3. N을 4번 사용한 경우

4. N을 5번 사용한 경우

5. 문제의 해결 - 일반화 하기 (수가 늘어날 수록 엄청나게 많은 결과가 나옴)

6. Python 코드로 풀어 보기

def solution(N, number):
	s = [set() for x in range(8)]
    
    for i, x in enumerate(s, start=1):
    	x.add(int(str(N) * i)) # 반복되는 N 추가 N,NN,NNN...
    
    for i in range(len(s)):
    	for j in range(i):
            for op1 in s[j]:
                for op2 in s[i-j-1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
        	answer = i+1
            break
        
    else:
    	answer = -1

	return answer