동적계획법 개념
1. 동적 계획 알고리즘
- 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
- 작은 부분 문제들의 해들을 구함 + 해를 이용하여 보다 큰 크기의 부분 문제를 해결 + 최종적으로 원래 주어진 문제 해결
- Memoization 기법 (프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 바르게 하는 기술
2. 분할정복과의 비교
- 분할 정복 : 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻음
- 공통점 : 문제를 잘개 쪼갬
- 차이점 : 동적계획법은 부분문제가 중복되어 상위 문제 해결시 재활용 (memoization) ex)피보나치 수열
- 분할정복은 부분문제가 중복 안됨. memoization기법 사용 안함 ex)병합정렬, 퀵정렬
3. 피보나치 수열
fibonacci(0):0 fibonacci(1):1 fibonacci(2):1 fibonacci(3):2 fibonacci(4):3 fibonacci(5):5 fibonacci(6):8 fibonacci(7):13 fibonacci(8):21 fibonacci(9):34
파이썬 구현
def fibo_dp(num):
cache = [ 0 for index in range(num + 1) ]
cache[0] = 0
cache[1] = 1
for index in range(2, num + 1):
cache[index] = cache[index - 1] + cache[index - 2]
return cache[num]
IN : fibo_dp(10)
OUT : 55
문제 설명
아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다.
12 = 5 + 5 + (5 / 5) + (5 / 5)
12 = 55 / 5 + 5 / 5
12 = (55 + 5) / 5
5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다.
이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요.
제한사항
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
입출력 예
Nnumberreturn
| 5 | 12 | 4 |
| 2 | 11 | 3 |
입출력 예 설명
예제 #1
문제에 나온 예와 같습니다.
예제 #2
11 = 22 / 2와 같이 2를 3번만 사용하여 표현할 수 있습니다.
첫번째 풀이
#N은 1이상 9이하 -> NN, N의 숫자 나올 수 있음
#number가 1 일때 : N=1이면 1, N=2이면 2/2, N=3이면 3/3
#결국 아무것도 안떠오름...
다른 사람 풀이 참고한 두번째 풀이
#N=5인 경우로 놓고 생각
|
1
2
3
4
|
arr=[set() for i in range(8)] #8개 이상 쓰이면 return -1
for i, num in enumerate(arr,start=1):
num.add(int(str(5)*i))
|
cs |
#arr배열 :
#arr[1]부터 어떻게 구성할 지 생각해보자.
대충 55, 5+5, 5-5, 5*5, 5//5 이런 게 있을 거
|
1
2
3
4
5
|
for op in arr[0]:
arr[1].add(op+op)
arr[1].add(op-op)
arr[1].add(op*op)
arr[1].add(op//op)
|
cs |
#arr[1]:
즉, arr[0]원소와 arr[0]원소를 사칙연산 한 것
#arr[1]~arr[2]를 구상해보자.
arr[2] : 555, 55+5, 5+5+5 뭐 이런게 있을 것 : arr[0]과 arr[1]의 사칙연산 일 것!
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
for op in arr[0]:
arr[1].add(op+op)
arr[1].add(op-op)
arr[1].add(op*op)
arr[1].add(op//op)
for op1 in arr[1]:
for op2 in arr[0]:
arr[2].add(op1+op2)
arr[2].add(op1-op2)
arr[2].add(op2-op1) arr[2].add(op1*op2)
arr[2].add(op1//op2)
arr[2].add(op2//op1) print(arr)
|
cs |
#빼기, 나누기는 교환법칙 성립x
현재 arr:
#arr[3](5 4개짜리)=arr[2](5 3개짜리 =arr[1]과 arr[0]의 연산)와 arr[1](5 2개짜리 =arr[0]과 arr[0]의 연산)의 연산
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def solution(N, number):
arr=[set() for i in range(8)] #8개 이상 쓰이면 오류이므로
for i, num in enumerate(arr,start=1):
num.add(int(str(N)*i))
for i in range(1,len(arr)): #제일 먼저 arr[0]만들어야
for op1 in arr[0]:
for op2 in arr[i-1]:
arr[i].add(op1+op2)
arr[i].add(op1-op2)
arr[i].add(op2-op1)
arr[i].add(op1*op2)
if op2!=0:
arr[i].add(op1//op2)
if op1!=0:
arr[i].add(op2//op1)
for i in range(0,len(arr)):
if number in arr[i]:
answer=i+1;
break;
else:answer=-1
return answer
|
cs |
#또 기본케이스는 성공하고 3개 실패함
채점을 시작합니다.
정확성 테스트
| 테스트 1 〉 | 통과 (1.23ms, 11.1MB) |
| 테스트 2 〉 | 통과 (0.20ms, 10.9MB) |
| 테스트 3 〉 | 통과 (0.59ms, 11MB) |
| 테스트 4 〉 | 통과 (1.39ms, 11.1MB) |
| 테스트 5 〉 | 실패 (1.21ms, 11.1MB) |
| 테스트 6 〉 | 실패 (1.24ms, 11.1MB) |
| 테스트 7 〉 | 실패 (1.32ms, 11.2MB) |
채점 결과
정확성: 57.1
합계: 57.1 / 100.0
'Algorithm > 🔎 Problem Solving' 카테고리의 다른 글
| [DFS / 중급] 네트워크 (프로그래머스, Python, Level3) (0) | 2022.06.28 |
|---|---|
| 파이썬 코테 : 백준 3085 (브루스포스) (0) | 2021.04.04 |
| 파이썬 코테 : 프로그래머스 주식가격 (스택) (0) | 2021.04.04 |
| 파이썬 코테 : 프로그래머스 구명보트 (그리디) (0) | 2021.03.25 |
| [JAVA] java 출력 모음 백준 2557 / 백준 JAVA 제출 시 주의 사항 (0) | 2019.12.31 |
댓글