순열(Permutation)과 조합(Combination), 라이브러리 없이

코딩테스트에서 numpy와 같은 라이브러리 사용을 허가하는 경우가 많지 않아 이렇게 작성하게 되었다. 회사마다 문제 출제 경향이 조금씩 다르지만 순열과 조합이 자주 나오는 회사라면 외워두는 것이 좋겠다.

 

순열 (Permutation)

순서를 고려하여 N개 중 M개를 중복 없이 뽑는 모든 경우를 의미한다

def permutation(depth):
	if depth == m: # m 개를 다 고른 경우 종료
    	print(result)
        return
        
    for i in range(n): # 입력 리스트의 길이
    	if not visited[i]:
        	visited[i] = True # 사용한 숫자 체크
            result.append(arr[i]) # 선택한 숫자를 저장
            perm(depth+1)
            result.pop()
            visited[i] = False
            
# input example
arr = [1, 2, 3]
m = 2

 

 

조합 (Combination)

순서 없이 N개 중 M개를 중복 없이 뽑는 모든 경우를 의미한다.

 

combination 코드의 경우 visited 리스트가 없는데, 이는 순서가 상관없기 때문이다.

def combination(start, depth):
	if depth == m:
    	print(result)
        return
        
    for i in range(start, n): # start를 이용하여 중복 제거가 가능하다
    	result.append(arr[i])
        comb(i+1, depth + 1)
        result.pop()