티스토리 뷰
프로그래머스 고득점킷 중 완전탐색에서 소수 문제를 풀 때 "n개의 카드를 이용해 만들 수 있는 숫자"를 구할 수 있어야 풀 수 있는 문제가 나옵니다.
https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3
이 문제는 '순열'을 구하는 알고리즘을 응용해 풀어야 합니다. 예를들면 0, 1, 1로 만들 수 있는 모든 숫자는 0, 1, 10, 11, 101, 110이 있습니다. 만들어진 숫자를 보면 일종의 '순열'입니다.
먼저 1, 2, 3을 이용해 구할 수 있는 모든 순열을 구해보겠습니다. 다음 코드는 주어진 배열에 있는 숫자를 이용해 순열을 구하는 코드 입니다.
def permutation(nums, current_nums):
if len(current_nums) == len(nums):
print(current_nums)
for num in nums:
if num not in current_nums:
permutation(nums, current_nums + [num])
permutation([1, 2, 3], [])
결과
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
'순열'은 '순'서가 있는 나'열' 이라는 뜻으로 순서가 중요합니다. 조합은 순서는 고려하지 않기 때문에 [1, 2, 3], [2, 1, 3]이 같은 것으로 취급 하지만 순열은 위와 같이 1, 2, 3을 가지고 총 6개의 순열을 만들어 낼 수 있습니다.
위 문제에서는 예시로 0, 1, 1과 1, 7을 이용해 만들 수 있는 소수를 구하라고 합니다. 소수인지는 후에 판별 하면 되고 만들 수 있는 모든 숫자를 먼저 만들어야 합니다. 이 문제에서 해결하기 어려운 부분은 0, 1, 1이 각각 1개의 카드라는 것입니다. 순열을 구하는 알고리즘은 current_nums에 이미 들어있는 숫자를 제외하고 재귀호출을 하지만 0, 1, 1의 경우는 1이 두개이기 때문에 이 조건을 이용해 재귀를 구성하면 안됩니다.
해법은 다음과 같이 nums를 모두 반복하지만 1개씩 빼서 넣는 방법을 이용합니다. 탈출(escape)조건은 nums의 길이가 0이면 탈출하게 구성합니다.
def permutations(nums, current_nums, result_set):
print(current_nums)
con = ''.join(current_nums)
if con != '':
result_set.add(int(con))
if len(nums) == 0:
return
for n in nums:
nums.remove(n)
permutations(nums, current_nums + [n], result_set)
nums.append(n)
s1 = set()
permutations(["0", "1", "1"], [], s1)
print(s1)
결과
{0, 1, 101, 10, 11, 110}
재귀 호출을 통해 만들어진 순열 중 ''를 제외하고 int로 변환한 후 set에 넣으면 중복이 제거된 만들 수 있는 모든 숫자를 구할 수 있습니다.
소수인지를 판별하고 싶다면 에라토스테네스체 알고리즘을 이용해 소수들을 만들어 낸 뒤 in 연산을 이용해 소수인지 판별 할 수 있습니다.
- Total
- Today
- Yesterday
- 싱가폴
- 도커티슈케이스
- docker container tissue
- 도커각티슈박스
- 도커컨테이너
- 개발자
- docker container
- docker container case
- 이직
- docker container whale
- 도커티슈박스
- Linux
- 2017 티스토리 결산
- docker container tissue box
- shellscript
- vim
- 도커각티슈케이스
- Sh
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 | 31 |