문제
코드
순열 사용
from itertools import permutations as pm
def solution_by_permutation(n, k):
n = 2
answer = list(pm(list(range(1,n+1)),n))
answer.sort()
return list(answer[k-1])
위의 코드는 논리적으로 반드시 맞는 코드이다. 그러나 시간 초과가 발생했다. 이는 즉, 최적화가 필요하다는 뜻이다. 그러나 시간 초과가 발생한 경우에는 다양한 접근 방법이 있는데, 나는 일단 수학적인 공식을 통해 함축적으로 논리를 압축하는 방향으로 접근해야겠다고 생각했다. 나의 문제 접근 방법 3-4 참고
실제 내가 문제를 풀 때 생각했던 사고의 흐름
문제의 로직은 아주 간단한 순열이다. 그러나 시간 복잡도와 공간 복잡도를 낮춰야만 한다. 그렇게 하기 위해서 주어진 문제를 함축적인 수학 공식으로 표현해본다. 모든 경우의 수는 일단 n개의 군으로 나뉜다. 그리고 각각의 군은 다시 n개의 군으로 다시 나뉜다. 즉, 트리 구조를 띈 형태로 순서가 존재하는 것이다. 그렇다면 이를 트리 구조로 곧이곧대로 구현할 것인가? 노드의 개수는 n!개가 필요하다. 순열을 이용한 것에서 전혀 복잡도가 낮아지지 않았다. 그러나 트리 구조를 띈다는 것을 이용해서 수학 공식을 추론해본다. 일단 작은 스케일에서 추론해본다.
규칙 찾기
import sys
sys.setrecursionlimit(10**8)
cache = dict()
def factorial(n):
if n in cache.keys():
return cache[n]
if n <= 1:
return 1
else:
result = n * factorial(n-1)
cache[n] = result
return result
def solution(n, k):
numbers = list(range(1,n+1))
answer = []
visited = [0 for _ in range(n)]
for i in range(1, n + 1):
# print(f"numbers {numbers}")
value1 = k // factorial(n-i)
value2 = k % factorial(n-i)
# print(f"{value1} {value2}")
k = value2
if value2 == 0:
answer.append(numbers[value1-1])
del numbers[value1-1]
else:
answer.append(numbers[value1])
del numbers[value1]
return answer먼저 수학적인 공식을 찾기 위해선 일단 관찰을 해야만 한다. 공식이란 일종의 규칙이므로 수의 패턴을 관찰해야만 그 패턴을 알 수 있기 때문이다. 이때 패턴을 찾기 위해서 나의 귀납 추론 방법을 사용했다. 즉, 작은 스케일에서 간단한 규칙을 찾고 이를 통해 연역 추론의 영역까지 확장 시키는 것이다. 나의 문제 접근 방법 2-3 참고
그래서 일단 관찰을 해봤다.
n=1 (1, ) n = 2 (1, 2) (2, 1) n = 3, k = 5 [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1] (3-1)!*2 + (3-2)!*1 + 0 n = 4, k = 15 (1, 2, 3, 4) (1, 2, 4, 3) (1, 3, 2, 4) (1, 3, 4, 2) (1, 4, 2, 3) (1, 4, 3, 2) (2, 1, 3, 4) (2, 1, 4, 3) (2, 3, 1, 4) (2, 3, 4, 1) (2, 4, 1, 3) (2, 4, 3, 1) (3, 1, 2, 4) (3, 1, 4, 2) (3, 2, 1, 4) (3, 2, 4, 1) (3, 4, 1, 2) (3, 4, 2, 1) (4, 1, 2, 3) (4, 1, 3, 2) (4, 2, 1, 3) (4, 2, 3, 1) (4, 3, 1, 2) (4, 3, 2, 1) 15 = (4-1)!*2 + (4-2)!*1 + (4-3)!*1 () 1 2 3 4 (3, ) 1 2 4 (3, 2, ) 1 4 (3, 2, 1, ) (3,2,1,4) 규칙을 찾았다! lst = [] lst.append(k//(n-1)! + 1) k = k % (n-1)! ... if (n-i)! == 0! 종료
먼저 규칙을 찾기 위해 n이 1부터 4까지 상황에서 어떤 값들이 나오는지 확인했다. 그리고 이를 통해 n과 k의 관계를 생각하기 위해 최대한 n과 k의 관점에서 패턴을 관찰했다. 일단 첫 번째로 찾은 패턴은 수의 나열들은 군을 이룬다는 것이다. n개의 군으로 나눠지고 각각의 군은 (n-1)!개로 구성되어 있다. 그리고 군 안 속에서는 n-1개의 군이 있고 각각의 군은 다시 (n-2)!개로 구성되어 있다. 이것이 계속 반복되는 구조였다.
이때 나는 해당 수가 몇 번째 군에 속하는지만 알 수 있다면 문제를 풀 수 있다고 생각했다. 그래서 (n-1)!으로 나눠서 첫 번째 군을 찾아내고 (n-(n-1))!까지 같은 방법으로 진행했다. 여기서 중요한 것은 다음 군에서는 k의 값이 다르게 갱신되어야 한다는 점이다. 이를 간단하게 위에 코드로 정리해놨다.
그리고 실제로 몇 번 실행을 해보고 마지막에 추가 조건이 있어야 한다는 사실을 찾아내어 문제를 풀 수 있었다.
느낀 점
내가 만든 문제 접근 체계가 유효하다는 것을 깨닫게 해준 문제였다.
그래서 접근법 자체에서는 막힘 없이 생각을 전개해나갈 수 있었다.
계속해서 문제 접근법은 업그레이드 해 나갈 예정이다.
문제 접근법
여기서 적용된 나의 문제 접근법
- 1번 접근법 (순열 구현)
- 시간초과 발생
- 3번 접근법 (최적화가 필요한 상황)
- 일단 어떻게 최적화 해야 할 지 감조차 잡히지 않는다.
- 그러나 감각적으로 수학적인 공식을 통해 알고리즘을 압축해봐야겠다는 생각이 들었다. (2-3번 접근법)
- 2-3번 접근법 (규칙을 찾아본다.)
- 귀납 추론을 하기 위해 작은 스케일에서 간단한 규칙을 찾도록 노력한다. (n = 1, 2, 3, 4)
- 군에 대한 규칙 발견
- 찾은 규칙을 큰 스케일에서 적용해본다.
- 만약 적용된다면 해당 규칙을 통해 연역 추론이 가능하다고 판단하고 코드를 작성한다.
- 귀납 추론을 하기 위해 작은 스케일에서 간단한 규칙을 찾도록 노력한다. (n = 1, 2, 3, 4)
신기할 정도로 문제 접근법이 체계적으로 적용된 문제다... 뿌듯!!
