일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |
Tags
- 빅테크 이슈
- 이진분류
- Bottom Tab Navigator
- NISQ
- 나의 첫 머신러닝/딥러닝
- 양자역학
- 단일큐빗
- 알고리즘
- 양자우위
- 트리의지름
- 전자중첩
- 리나칸
- 다중큐빗
- 다중 레이블 분류
- Lv3
- Amazon's Antitrust Paradox
- 머신러닝
- 얽힘상태
- 머신러닝 검증
- qubit
- Top Tab Navigator
- 파이썬
- 플랫폼 독점
- 검증 데이터
- 트리
- 머신러닝 교재
- 다중분류
- 줄 서는 방법
- 아마존의 반독점 역설
- 프로그래머스
Archives
- Today
- Total
엄지척 블로그
[프로그래머스][줄 서는 방법] 본문
프로그래머스 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12936
문제를 풀다가 우연히 수학공식을 발견하게 되어서 위 글을 쓰게 된다.
숫자가 [1,2,3]
이 있을시
1 2 3
1 3 2
2 1 3
3 1 2
이 순으로 나열할수 있는데
조금더 n 을 크게 하여서 일반화를 시킬수 있다.
예를 들어 1 ,2 , 3, 4 ,5 가 있으며
49번째 수를 구할때에는
1 이 가장 앞에나올때는 4! 의 경우가 있으며
2 가 가장 앞에나올때는 4! 의 경우가 있으며
다음 3이 나올때의 49 - 4!*2 번째 수를 구하면 된다.
이를 생각을 하다가
n! = (n-1)*(n-1)! + (n-2)*(n-2)! + (n-3)*(n-3)! + ......... 1*1! + 1 이라는 것을 알게 되었다.
증명은 k! - (k-1)*(k-1)! = (k-2)! 이라는것을 계산하기만 하면 자연스럽게 증명을 할수있다.
각설하고...
위를 토대로 n 장의 숫자카드로 만들수있는 경우는 n! 인데
n! 은 팩토리얼 의 합으로 나타낼수있다는 것을 알아냈다.
이는
가장 앞에 나오는 카드의 숫자를 구한다음에 기존에 가지고있는 배열에
그숫자를 뺸 이후 ,
새롭게 얻을 배열과 , 새롭게 얻어진 k번쨰의 숫자를 구하여 재귀함수 형식으로 구할시 코드를 빠른시간안에 완성시킬수 있다는 것을 알수있게 된다.
코드는 다음과 같다.
import math
def get_array(array, n, k):
if n==1:
return array
tmp_factorial = math.factorial(n-1)
for i in range(1,n+1):
if k <= i*tmp_factorial:
# i 번째수 빼고 뒤로가면댐
target_number = array[i-1]
array.remove(target_number)
return [target_number] + get_array(array,n-1, k- (i-1)*tmp_factorial)
def solution(n, k):
array = [i for i in range(1,1+n)]
return get_array(array, n, k)
'Algorithm' 카테고리의 다른 글
[프로그래머스 - 순위] [그래프][DFS] (0) | 2021.11.26 |
---|---|
(백준 1967번) 트리의 지름 증명 (2) | 2020.12.20 |
Comments