알고리즘
순열과.조합. 무슨 말인지...알겠어요...? (feat. 순열과 조합 구현하기)
김치말이삼겹살
2024. 4. 13. 09:07
갑자기 고등학교 다닐 때 확률과 통계 선생님과 수학학원 선생님이 생각나서
두 분의 명언을 짬뽕해본 제목...
오늘 다룰 내용은 순열 조합 구현하기다 !!
BIG SPECIAL SHOUT OUT TO...
TIL: itertools 없이 순열과 조합
삼성 코테에서는 sys 도 못쓰고 itertools도 못쓴다니. deque 쓰게해줘서 고마울지경.
tommyjr1.github.io
itertools 없이 순열과 조합을 구현해야하는 삼성 코테...
한번 같이 풀어뿌삐 해보자구요.
우선?
조합부터...
조합:
주어진 배열 array = [1,2,3,4] 가 있고, n = 2 가 있을 때
combinations([0,1,2,3], 2) = [[0] + combinations([1,2,3],1)] + [[1] + combinations([2,3],1)] + [[2] + combinations([3],1)]
def combinations(array,n):
result = []
# n이 0이면 빈 이중 배열 리턴
if n == 0:
return [[]]
# 그렇지 않으면
for i in range(0, len(array)):
# 아까봤던대로 i번째 요소 빼주고
elem = array[i]
# 나머지요소만 사용해서
rest = array[i+1:]
# 모든 요소들에 대해 조합 진행
for j in combination(rest,n-1):
result.append([elem]+j)
return result
# itertools 쓴다면
from itertools import combinations
combs = list(combinations([1,2,3],2))
print(combs)
#[(1,2), (1,3), (2,3)]
그리고 순열 함 보실까요...?
순열과 조합의 한끝 차이는 바로 나머지 요소를 살짝만 twik하면 된다는 것 !!
왜냐면 순열은 그 앞의 것도 고려를 해야하기 때문
def permutations(array,n):
# 초기 result 초기화
result = []
# 만약 n이 0이면
if n == 0:
return [[]]
# 그렇지 않으면 아까 진행했던 것 그대로 진행
for i in range(len(array)):
# i 번째 요소 빼주고
elem = array[i]
# i를 제외한 모든 요소 더해줌
rest = array[:i] + array[i+1:]
# 모든 남은 요소들에 대해
for P in permutations(array, n):
result += [[elem] + P]
# 덧셈이 append와 같은 기능을 하려면
# result.append([elem] + P) 도 가능 !!
return result
# 다른 코테에서는 이 한 줄로 ~~
from itertools import permutations
perm = list(permutations([1,2,3],2))
print(perm)
# [(1,2), (1,3), (2,3), (2,1), (3,1), (3,2)]
반응형