❗ 순열과 조합의 차이는 순서를 고려하느냐의 차이 !
path : 뽑은 원소들을 저장하는 리스트
used : 원소들의 사용 유무를 체크하는 리스트
level : 뽑은 카드 번호 (0 ~ r-1
)
뽑아야 할 원소가 있는 경우 (level < r
), 카드 배열 순회
used[i] == 0
)path[level] = card[i]
) 다음 카드 뽑으러가기 (level+1
)4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,
# 순열
# 중복 허용 x, 순서가 다르면 다른 경우의 수
# 4장의 카드 중에서 3장 뽑기
card = ['A', 'B', 'C', 'D']
path = [0]*3
# used 배열 사용하여 카드 중복 사용 유무 확인
used = [0]*4
def dfs(level):
# 3장 모두 뽑았으면 출력하고 return
if level == 3:
print(*path)
return
# 카드 4장 확인하기
for i in range(4):
if used[i] == 0: # 아직 사용하지 않은 카드이면
used[i] = 1 # 사용 체크 하고
path[level] = card[i] # 카드 뽑기
dfs(level+1) # 다음 카드 뽑으러 가기
used[i] = 0 # 리턴 이후에는 다시 사용 체크 해제
path[level] = 0 # 뽑은 카드 초기화
dfs(0)
path : 뽑은 원소들을 저장하는 리스트
level : 뽑은 카드 번호 (0 ~ r-1
)
뽑아야 할 원소가 있는 경우 (level < r
), 카드 배열 순회
path[level] = card[i]
) 다음 카드 뽑으러가기 (level+1
)4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,
# 중복 순열
# 중복 허용, 순서가 다르면 다른 경우의 수
# 4장의 카드 중에서 3장 뽑기
card = ['A', 'B', 'C', 'D']
path = [0]*3
def dfs(level):
# 3장 모두 뽑았으면 출력하고 리턴
if level == 3:
print(*path)
return
for i in range(4):
path[level] = card[i] # 카드 뽑고
dfs(level+1) # 다음 카드 뽑으러 가기
path[level] = 0 # 리턴 이후 뽑은 카드 초기화
dfs(0)
path : 뽑은 원소들을 저장하는 리스트
level : 뽑은 카드 번호 (0 ~ r-1
)
start : 뽑기 시작할 카드 인덱스
뽑아야 할 원소가 있는 경우 (level < r
)
i
를 뽑은 경우를 확인했으면, 0번째에서 원소 i+1
를 뽑았을 때 1번째에서 원소i
를 뽑는 경우는 제외 해야함start
를 사용하여 뽑기 시작할 원소 인덱스 정하기path[level] = card[i]
) 다음 카드 뽑으러 가기 (level+1
, start ← i + 1
)4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,
# 조합
# 중복 허용 X, 순서가 달라도 같은 경우의 수
# 4장의 카드 중에서 3장 뽑기
card = ['A', 'B', 'C', 'D']
path = [0]*3
def dfs(level, start):
# 3장 모두 뽑았으면 출력하고 리턴
if level == 3:
print(*path)
return
for i in range(start, 4):
path[level] = card[i] # 카드 뽑기
dfs(level+1, i+1) # 직전에 뽑은 카드의 다음 인덱스의 카드 부터 카드 뽑기
path[level] = 0 # 리턴 이후 뽑은 카드 초기화
dfs(0, 0)
card = ['A', 'B', 'C', 'D']
path = ['']*4
cnt = 0
def abc(level, start):
global cnt
cnt += 1 # 함수 진입할 때마다 cnt +1
if level == 4:
return
for i in range(start, 4):
path[level] = card[i]
print(*path) # 카드 새로 뽑을 때마다 출력
abc(level+1, i+1) # 직전에 뽑은 카드의 다음 인덱스의 카드 부터 카드 뽑기
path[level] = '' # 리턴 이후 뽑은 카드 초기화
abc(0, 0)
print(cnt)
path : 뽑은 원소들을 저장하는 리스트
level : 뽑은 카드 번호 (0 ~ r-1
)
start : 뽑기 시작할 카드 인덱스
뽑아야 할 원소가 있는 경우 (level < r
)
i
를 뽑은 경우를 확인했으면, 0번째에서 i+1
를 뽑았을 때 1번째에서 i
를 뽑는 경우는 제외 해야함start
를 사용하여 뽑기 시작할 원소 인덱스 정하기path[level] = card[i]
) 다음 카드 뽑으러 가기 (level + 1
, start ← i
)4장의 카드 (A, B, C, D) 중에서 3장을 뽑는다고 가정하면,
# 중복 조합
# 중복 허용 O, 순서가 달라도 같은 경우의 수
card = ['A', 'B', 'C', 'D']
path = [0]*3
def dfs(level, start):
# 3장 모두 뽑았으면 출력하고 리턴
if level == 3:
print(*path)
return
for i in range(start, 4):
path[level] = card[i] # 카드 뽑기
dfs(level+1, i) # 직전에 뽑은 카드와 같은 인덱스부터 카드 뽑기
path[level] = 0 # 리턴 이후 뽑은 카드 초기화
dfs(0, 0)
감사합니다 도움이 되었습니다.