순열 조합 생성하기

분야

프로그래밍/소프트웨어 개발

대상자

Python 개발자, 알고리즘 설계에 관심 있는 개발자, 재귀 알고리즘 이해를 원하는 개발자

난이도: 중급 (재귀 구조 및 제너레이터 활용 이해가 필요)

핵심 요약

• *재귀 구조와 제너레이터를 활용한 순열/조합 생성**
• yield from을 사용해 재귀적으로 순열과 조합을 생성할 수 있음
• 순열은 원소 순서가 중요 (예: (A,B,C) ≠ (B,A,C))
• 조합은 순서를 무시하고 유일성 보장 (예: (A,B,C)는 중복 없음)
• 중복 데이터 처리는 Counter를 사용해 개수 제한 적용

섹션별 세부 요약

1. 순열 생성기 구현 원리

• 첫 번째 원소를 고정하고, 나머지 원소로 재귀적으로 순열 생성
• permutations(xs, n=0) 함수는 재귀 함수 _helper를 통해 구현
• yield from으로 중첩된 제너레이터 결과를 반환
• 예: A = [1,2,3,4]에서 3개 원소로 만들 수 있는 순열 출력

1. 조합 생성기 구현 원리

• 순열과 유사하지만, 중복 제거를 위한 정렬 처리 필요
• _helper 함수에서 tail[i+1:]로 다음 원소만 선택
• combinations(xs, n=0) 함수는 조합 유일성 보장
• 예: [1,2,3,4]에서 3개 원소로 만들 수 있는 조합 출력

1. 중복 데이터 처리 방안

• Counter를 사용해 중복된 원소 개수 제한 (예: [A,A,B]에서 A는 최대 2번 사용)
• 순열 생성 시 중복 요소를 조합으로 처리하고, 나머지 원소로 순열 생성
• 재귀 구조는 동일하지만, 중복 처리 로직이 달라짐

결론

• *재귀 제너레이터를 활용한 순열/조합 생성**은 알고리즘 설계에 유용한 패턴으로,
• 순열은 yield from으로 중첩된 결과 반환,
• 조합은 정렬 처리로 유일성 보장,
• 중복 데이터는 Counter로 개수 제한 적용해야 함

실무에서는 itertools 모듈 대신 직접 구현할 필요는 없지만, 알고리즘 이해에 도움이 됨.