1. 개념 정리
1.1 동적 계획법 (Dynamic Programming)
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 즉, 어떤 문제를 풀기 위해 문제를 여러 개의 하위 문제로 나누어 푼 다음 그것을 결합하여 최종적인 목적에 도달하는 것이다. 하지만 모든 경우에 동적 계획법을 적용할 수 있는 것은 아니며, 다음 조건을 만족할 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
동적 계획법은 얼핏 보면 분할 정복(Divide and Conquer)과 유사해 보이지만 동적 계획법은 문제들이 서로 영향을 미치고 있다는 점에서 차이를 가진다.
2. 문제 설명
2.1 N으로 표현
아래와 같이 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 함수를 작성하세요.
2.2 제한 조건
- N은 1 이상 9 이하입니다.
- number는 1 이상 32,000 이하입니다.
- 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
- 최솟값이 8보다 크면 -1을 return 합니다.
2.3 입출력 예시
| N | number | return |
|---|---|---|
| 5 | 12 | 4 |
| 2 | 11 | 3 |
3. 풀이 과정
주어진 N을 가지고 사칙 연산을 해서 number를 만들 수 있는 N의 최소 사용횟수를 구하는 문제이다. 문제 풀이 방식을 떠올리는 것이 어려웠던 문제이다. (결론적으로는 다른 분의 풀이를 조금 참고했다. )
이번 문제의 경우도 테스트 케이스가 부족하다고 생각해서 질문하기에 나와 있는 테스트 케이스 몇 개를 추가해서 풀어보았다.
3.1 2중 반복문 : 실패😂
주어진 조건에서 최솟값이 8보다 크면 -1을 반환한다는 것에 집중해보았다. 즉, 8보다 큰 경우는 고려하지 않겠다는 것이기 때문에 N을 1~8번 사용해서 만들 수 있는 모든 경우의 수를 구하고 그 중 number가 존재하는지 파악하는 방식으로 문제에 접근했다.
3.1.1 점화식 세우기
만약 주어진 N이 5라고 가정했을 경우 만들 수 있는 모든 경우의 수를 예상해보았다. N을 1번 사용할 경우는 5를 만들 수 있고, N을 2번 사용할 경우는 55와 5를 2개 사용해서 사칙 연산한 결과를 만들 수 있다. 여기에서 힌트를 얻어서 N이 2일 경우의 결과는 N을 2번 연결해서 만들 수 있는 55와 N을 i-1번 사용했을 경우의 결과에 사칙연산을 한 것으로 생각하게 되었고 다음 표처럼 되지 않을까 예상해보았다.
즉, 아래와 같은 점화식을 세워보았다.
N을i번 사용해서 만들 수 있는 수의 집합- =
N을i번 연결한 수,N을i - 1번 사용했을 때 결과에 사칙 연산
N의 사용 횟수 | 만들 수 있는 number |
|---|---|
| 1일 경우 | 5 |
| 2일 경우 | 55, 5 + 5, 5 - 5, 5 * 5, 5 // 5 |
| 3일 경우 | 555, (N이 2일 경우 결과에 사칙연산) |
| 4일 경우 | 5555, (N이 3일 경우 결과에 사칙연산) |
| 5일 경우 | 55555, (N이 4일 경우 결과에 사칙연산) |
| 6일 경우 | 555555, (N이 5일 경우 결과에 사칙연산) |
| 7일 경우 | 5555555, (N이 6일 경우 결과에 사칙연산) |
| 8일 경우 | 55555555, (N이 7일 경우 결과에 사칙연산) |
3.1.2 코드 구현
위에서 세운 점화식을 바탕으로 코드를 구현하고 실행을 돌려보았더니 일부 테스트 케이스의 경우만 통과할 수 있었다.
곱하기나 나누기 연산의 경우 연산자의 위치에 따라서 결과가 달라질 수 있다는 것을 고려하지 않았기 때문이다.
(55 + 5) / 5이런 경우가 정답일 경우에는 문제가 없지만,55 / 5 + 5 / 5이런 경우는 아래와 같은 방식으로는 만들어 낼 수 없었다.
나름대로 탐색 시간을 고려한다고 사전도 사용하고 나누기 순서도 고려해서 코드를 작성했지만, 이전의 결괏값에 그대로 사칙연산을 하는 것이기 때문에 ((((() 사칙연산) 사칙연산) 사칙연산) 사칙연산) 이런 구조가 될 수밖에 없기 때문에 실패한 것이었다.
- 전체 코드(Python)
def solution(N, number):
DP = [{} for _ in range(9)]
DP[1][N] = True
for i in range(2, 9):
DP[i][int(str(N) * i)] = True
for num in DP[i - 1].keys():
DP[i][num + N] = True
DP[i][num - N] = True
DP[i][num * N] = True
DP[i][num // N] = True
# 순서가 바뀌었을 때 고려
if num != 0:
DP[i][N // num] = True
if number in DP[i]:
return i
return -1- 실행 결과
3.2 4중 반복문 : 성공😋
이전에는 55 / 5 + 5 / 5와 같은 경우를 고려하지 못해 실패했었기에 이를 고려해서 점화식을 세워야 했다. 그러나 너무 많은 경우의 수가 생기기 때문에 어떤 방식으로 점화식을 세워야 할지 감이 잡히지 않았다. 결국 구르미님의 풀이를 일부 참고한 후에야 문제를 풀 수 있었다.
3.2.1 점화식 세우기
N의 사용 횟수를 1~8까지 반복하면서 만들 수 있는 수들을 구한 후 그 중 number가 포함되어있는지 파악하는 것은 동일했다.
차이가 생기는 부분은 N을 i번 사용해서 만들 수 있는 수를 구하는 점화식이었다.
사칙 연산으로 설명해보면 다음과 같다. 숫자 2를 만드는 방법은
1 + 1이 끝이다. 하지만 숫자 3의 경우는1 + 2,2 + 1,1 + 1 + 1이렇게 총 3가지가 있을 수 있다.기존의 방식의 경우 그런 모든 경우의 수를 고려하지 않고 아래와 같이 단순하게 구현한 것이었다.
- 2 = (1) + 1 =>
N이 2개일 경우 (N이 1개일 경우의 결과에 사칙연산)- 3 = (2) + 1 =>
N이 3개일 경우 (N이 2개일 경우의 결과에 사칙연산)- 4 = (3) + 1 =>
N이 4개일 경우 (N이 3개일 경우의 결과에 사칙연산)
그렇기 때문에 위에서의 문제점을 해결하려면 다음과 같이 더하는 모든 경우의 수를 생각해주어야 한다. (
1 + 1 + 1같은 표현이 없는 이유는1 + 2안에2 = 1 + 1이라서 이미 포함되어 있기 때문이다.)
- 2 = 1 + 1
- 3 = 1 + 2 = 2 + 1
- 4 = 1 + 3 = 2 + 2 = 3 + 1
- 5 = 1 + 4 = 2 + 3 = 3 + 2 = 4 + 1
- ...
이를 바탕으로 새로운 점화식을 세워보았다. (U는 합집합을 의미한다.)
N을i번 사용해서 만들 수 있는 수의 집합 =N을i번 연결한 수 U- (
N을1번 사용했을 때 결과)에 (N을i - 1번 사용했을 때 결과)에 사칙 연산 한 수들 U- (
N을2번 사용했을 때 결과)에 (N을i - 2번 사용했을 때 결과)에 사칙 연산 한 수들 U- (
N을3번 사용했을 때 결과)에 (N을i - 3번 사용했을 때 결과)에 사칙 연산 한 수들 U- ....
- (
N을i - 1번 사용했을 때 결과)에 (N을1번 사용했을 때 결과)에 사칙 연산 한 수들 U
3.2.2 코드 구현
위의 점화식으로 새롭게 코드를 작성해보았다. 이전의 코드에서는 set도 해시를 기반으로 만들어져 탐색 시간이 O(1)이 걸린다는 사실을 모르고 dictionary만 해시 기반이라고 생각했다. 그래서 dictionary를 사용한 것이었는데 set도 선형시간에 탐색이 가능하길래 새로운 코드에서는 set을 사용하도록 코드를 수정하였다.
for 문이 4번 반복된 코드라서 성능은 기대하지 않았었는데 반복 범위 자체가 크지 않아서 예상외로 괜찮은 성능을 보여주었다.
- 전체 코드 (Python)
def solution(N, number):
if N == number: return 1
DP = [{}, { N }] # 1번 사용했을 경우
for i in range(2, 9): # 2번 ~ 9번 사용했을 경우
temp = { int(str(N) * i) } # N을 i번 연결한 수 (ex: 555)
for j in range(1, i):
for num_1 in DP[j]: # 1 ~ i - 1번 사용했을 때 결과
for num_2 in DP[i - j]: # i - 1 ~ 1번 사용했을 때 결과
temp.add(num_1 + num_2)
temp.add(num_1 - num_2)
temp.add(num_1 * num_2)
if num_2: # 0으로 나누는 에러 방지
temp.add(num_1 // num_2)
if number in temp: return i # number가 있으면 i 반환
DP.append(temp)
return -1- 실행 결과
3.2.3 코드 개선
위에서 코드도 충분히 좋은 성능을 보여주었지만 조금 더 개선해볼 수 있지 않을까 생각해서 반복 구간을 조금 변경해보았다. 실제로 반복 구간이 줄어든 만큼 약간이지만 실행 시간이 조금 줄어들었다.
예를 들어
i = 5일 경우 아래처럼 구성되는데 절반 구간만 반복을 돌리고 내부적으로 위치를 바꿔서 추가하는 코드를 추가해보았다. (더하기와 곱하기의 경우는 앞뒤 자리를 바꾸어도 결과가 동일하기 때문에 빼기와 나누기만 자리를 바꾸어주었다.)
- 1 + 4
- 2 + 3
- 3 + 2
- 4 + 1
- 전체 코드 (Python)
def solution(N, number):
if N == number: return 1
DP = [{}, { N }]
for i in range(2, 9):
temp = { int(str(N) * i) }
for j in range(1, i // 2 + 1): # 반복 범위를 반으로 줄임
for num_1 in DP[j]:
for num_2 in DP[i - j]:
temp.add(num_1 + num_2)
temp.add(num_1 - num_2) # 순서 바꾸는 것 고려
temp.add(num_2 - num_1) # 순서 바꾸는 것 고려
temp.add(num_1 * num_2)
if num_2: temp.add(num_1 // num_2) # 순서 바꾸는 것 고려
if num_1: temp.add(num_2 // num_1) # 순서 바꾸는 것 고려
if number in temp: return i
DP.append(temp)
return -1- 실행 결과
4. 핵심 정리
4.1 🔥 최종 풀이 🔥
def solution(N, number):
if N == number: return 1
DP = [{}, { N }]
for i in range(2, 9):
temp = { int(str(N) * i) }
for j in range(1, i // 2 + 1):
for num_1 in DP[j]:
for num_2 in DP[i - j]:
temp.add(num_1 + num_2)
temp.add(num_1 - num_2)
temp.add(num_2 - num_1)
temp.add(num_1 * num_2)
if num_2: temp.add(num_1 // num_2)
if num_1: temp.add(num_2 // num_1)
if number in temp: return i
DP.append(temp)
return -14.2 핵심 포인트
- 연산자(
*,/)의 위치에 따라서 값이 달라진다는 점. set과dictionary의 경우hash구조를 사용하기 때문에O(1)의 시간에 탐색이 가능함.
4.3 주요 라이브러리
4.4 참고 링크
