기업에 따라 라이브러리 사용에 제한이 있기 때문에, Python의 장점 중 하나인 itertools 사용할 수 없는 경우가 생기게 됩니다.
그렇기 때문에 코딩테스트를 앞두고 관련 알고리즘을 직접 구현하며 정리하는 시간을 가져보았습니다.
하나의 템플릿처럼 제가 자주 사용하는 형태로, 모든 구현에 재귀를 사용합니다.
이유는 처음 관련된 내용을 학습했을 때, 반복문보다 흐름이 더 직관적이었기 때문입니다.
[조합]
def c(idx, target, result): # 리스트의 현재 인덱스, 선택된 수의 개수, 만들어지 조합
if target == n:
print(result)
return
if idx == len(arr): # 숫자들이 다 선택되지 않은 상태에서 다음 숫자를 선택할 때 초과된 인덱스를 선택하는 것을 방지
return
c(idx + 1, target + 1, result + [arr[idx]]) # 현재 숫자 선택 후, 다음으로 넘어감
c(idx + 1, target, result) # 현재 숫자 선택 안 하고 다음으로 넘어감현재 숫자를 선택하고 진행, 선택하지 않고 진행이라고 생각한다면 어려움 없이 이해하실 수 있을 거라 생각합니다.
[중복 조합]
def cr(idx, target, result): # 중복 조합
if target == n:
print(result)
return
for i in range(idx, len(arr)): # 수를 중복으로 표기할 땐 반복문을 사용
cr(i, target + 1, result + [arr[i]]) # 반복문 범위가 배열의 범위이므로 인덱스를 체크할 필요 없음수를 중복으로 사용하면서도 연이은 숫자를 선택하기 위해 반복문을 사용합니다.
중복이라는 선택지가 고정이기 때문에, 선택하지 않은 함수 호출은 없습니다.
또한 순서가 없는 조합의 특성상, 동일한 조합을 만들지 않기 위해 idx를 이용해 선택 범위를 조정합니다.
가령 [1, 1, 2]와 [1, 2, 1]은 같은 조합입니다. 이를 방지하기 위해서 코드 상에서는 순서를 지정해 버리는 것입니다.
무슨 말이냐면 idx가 1인 상태로 코드가 시작되면, 반복문 문법에 의해서 다시 1이 선택되지 않게 됩니다.
ex)
1, 1, 1
1, 1, 2
1, 2, 2
2, 2, 2
2, 2, 3
[순열]
def pt(target, result, visited): # 순열
if target == n:
print(result)
return
for i in range(len(arr)): # 반복문의 범위가 배열의 범위이므로 인덱스를 체크할 필요 없음
if visited[i]: # 이미 선택된 숫자라면 다음으로 넘어감
continue
visited[i] = True # 현재 숫자 선택
pt(target + 1, result + [arr[i]], visited)
visited[i] = False숫자의 순서가 있어 중복 조합과 달리 앞에 선택했던 숫자가 앞에 나오는 경우가 발생합니다.
하지만 동일한 숫자를 다시 사용하면 안 되기 때문에 그래프 탐색처럼 사용한 숫자의 사용 유무를 체크하며 데이터를 만들어 냅니다.
[중복 순열]
def pd(target, result): # 중복 순열
if target == n:
print(result)
return
for i in range(len(arr)): # 반복문의 범위가 배열의 범위이므로 인덱스를 체크할 필요 없음
pd(target + 1, result + [arr[i]])중복 조합과의 차이는 매개변수에서 idx가 빠져 탐색 범위를 제한하지 않는다는 것입니다.
