파이썬 코테 문제를 풀다보면 종종 활용하는 라이브러리인 itertools.
이 라이브러리에서 제공하는 대표 메소드 combinations의 동작을 알아보려한다.
0. 발단
프로그래머스에서 제한된 라이브러리를 쓰려하면 위와 같이 에러가 뜬다.
쓸 수 있는 라이브러리를 기업마다 다르게 제한하는 것 같은데,
이로 인해 최근 시험 도중 난항을 겪었다...
평소처럼 itertools.combinations을 통해 완전 탐색으로 문제에 접근했는데,
위 에러를 맞닥뜨린 것이다😂😂
당황한 나는 그 자리에서 직접 DFS 기반 순회 코드를 구현했으나,
평소 연습했던 알고리즘이 아니어서 그런지 자잘한 실수가 있었다.
결국 30분의 디버깅 끝에 겨우 원하는 기능을 구현해 풀 수 있었다..
비록 답은 맞았을지 모르나, 여기서 버린 시간 때문에
다른 마지막 문제는 풀어보지도 못하고 제출할 수 밖에 없었다.
(제출 직후 내 표정)
이런 실수가 재발하는 것을 방지하고자,
이참에 combinations의 직접 구현 방법을 정리하려 했다.
포스팅 작성 버튼을 누르려던 찰나, 갑자기 든 생각.
파이썬의 itertools에서는 어떻게 combinations를 구현했을까?
최근 면접에서 자꾸 라이브러리 소스코드를 뒤져본적이 있냐고 물어보던데..
이 질문에 대답할 거리도 만들어볼겸 itertools.combinations 코드를 뒤져보려 마음먹었다.
1. 소스코드를 찾아서
먼저 만만한 vscode에 가서 itertools를 import 하고,
ctrl + 좌클릭으로 combinations 메소드의 선언부로 타고 들어갔다.
그러나 추상화된 클래스만 있고 진짜 코드는 숨겨져 있었다.
이에 직접 itertools 파일을 찾아가 코드를 뜯어보려 라이브러리 위치를 찾아봤다.
inspect를 통해 라이브러리 파일 위치를 보려하니 위와 같은 에러가 떴다.
stack overflow에 해당 에러를 찾아보니, 원인은 CPython이었다.
파이썬에서는 몇몇 표준 라이브러리를 C언어로 구현해 매우 빠르게 실행 가능하도록 해놓았다.
따라서 코드를 보려면 C파일을 뜯어봐야하는 것이었다..
결국 python itertools 라이브러리 공식 문서에 있는 코드로 동작을 이해해보기로 했다.
2. Combinations 코드의 동작
자, 그럼 긴말할 것 없이, 공식 문서에 있는 코드를 보자.
def combinations(iterable, r):
# combinations('ABCD', 2) → AB AC AD BC BD CD
# combinations(range(4), 3) → 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)깔끔하다.. 아름답다.. 그럼 코드를 자세히 분석해보자.
pool 생성
pool = tuple(iterable)예외상황 제거
n = len(pool)
if r > n: # 뽑으려는 수(r)가 원소 수(n)보다 많으면
return # 함수 종료(return)indices 생성
indices = list(range(r))이 indices의 의미는 다음과 같이 생각하면 편하다.
"pool의 몇 번째 원소를 뽑을 것인가?"
예를 들어, 5개의 원소를 가진 pool이 있고 r이 3이라하자.
그럼 indices는 위 코드에 의해 [0, 1, 2]로 초기화될 것이다.
이는 pool의 첫 번째, 두 번째, 세 번째 원소를 뽑는 경우를 지칭한다고 보면 된다.
그럼 여기서 indices가 [0, 1, 3]으로 바뀐다면?
pool의 첫 번째, 두 번째, 네 번째 원소를 뽑는 경우를 지칭하게 되는 것이다.
이처럼 indices의 값을 바꿔가며 pool의 원소들을 tuple 형태로 내보내는게 기본적인 아이디어이다.
첫 번째 결과값 반환
yield tuple(pool[i] for i in indices)이 부분을 이해하려면 먼저 파이썬의 yield 함수를 이해해야한다.
파이썬은 generator라는 특수한 형태의 iterator 타입이 있는데,
일반적인 iterator와는 달리 동적으로 값을 추가할 수 있다.
예를 들어, 원래라면 ["A", "B", "C"] 이렇게 완성된 결과를 return하는게 일반적이다.
하지만 generator를 사용하면, ["A"] > ["A", "B"] > ["A", "B", "C"] 이렇게 동적으로 값을 반환하는게 가능하다.
이렇게 generator 반환 결과에 "A"나 "C" 등 원소를 추가하는
과정이 yield라는 것이다.
따라서 위 코드는 다음과 같이 이해할 수 있다.
내가 반환할 결과는 generator<tuple> 자료형인데,
그 첫 번째 원소(tuple)를 지금 반환할게.
또한 위에서 언급한대로, indices는 처음 초기화된 인덱스들을 골라 결과에 추가하게 된다.
반복문을 돌며 tuple 반환
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)맨 아래줄 코드를 보면, indices 값을 기준으로
pool에서 원소를 골라 yield 하는 것을 볼 수 있다.
윗 부분 코드는 모두 indices의 값을 변경하는 부분으로,
예를 들면서 정리해보겠다.
방금 제시했던 n = 5, r = 3인 경우를 생각해보자.
여기서 반복문이 시작되며, 코드를 따라가보겠다.
pool = [A, B, C, D, E]
indices = [0, 1, 2]
i = 2부터 시작
if indices[2] != 2 + 5 - 3 에서 break문 진입
indices[2] += 1 실행
pool = [A, B, C, D, E]
indices = [0, 1, 3]
i = 2이므로 아래 for문은 실행되지 않음.
for j in range(2+1, 3):
pool = [A, B, C, D, E]
indices = [0, 1, 3][A, B, D] 반환
다음 반복문을 따라가보자.
pool = [A, B, C, D, E]
indices = [0, 1, 3]
i = 2부터 시작
if indices[2] != 2 + 5 - 3 에서 break문 진입
indices[2] += 1 실행
pool = [A, B, C, D, E]
indices = [0, 1, 4]
i = 2이므로 아래 for문은 실행되지 않음.
for j in range(2+1, 3):
pool = [A, B, C, D, E]
indices = [0, 1, 4][A, B, E] 반환
한 번만 더 따라가보자.
pool = [A, B, C, D, E]
indices = [0, 1, 4]
i = 2부터 시작
if indices[2] != 2 + 5 - 3 에서 다음 순회로 진행
i = 1
if indices[1] != 1 + 5 - 3 에서 break문 진입
indices[1] += 1 실행
pool = [A, B, C, D, E]
indices = [0, 2, 4]
i = 1이므로 아래 for문이 실행됨.
for j in range(1+1, 3):
indices[j] = indices[j-1] + 1indices[2] = indices[1] + 1 실행
pool = [A, B, C, D, E]
indices = [0, 2, 3][A, C, D] 반환
눈치 챘는가?
결국 while문 내부의 두 for문은 다음과 같은 역할을 하는 것이다.
[0, 1, 4] 에서 다음 조합인 [0, 2, 3]으로 변화시킬 때
위 for문: 1 -> 2로 바꾸는 역할
아래 for문: 4 -> 3으로 바꾸는 역할
3. 정리
단순한듯 단순하지 않은 코드였다..
솔직히 나보고 구현하라고 하면 저렇게 절대 못할 것 같다ㅋㅋㅋ
하지만 이렇게 잘 짜여진 코드를 보는 것만으로도
개발자로서의 시야가 넓어지지 않았을까 싶다.
다음엔 나만의 방식으로도 구현해봐야겠다.
