알고리즘 스터디 2, 3일차 정리(permutation, backtracking)

python에는 순열과 조합을 구해주는 permutation과 combination 함수가 itertools에 있었다.
이렇게 간편하다닛?! 하하

import itertools

arr = ['A', 'B', 'C']
nPr = itertools.permutations(arr, 2)
print(list(nPr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

import itertools

arr = ['A', 'B', 'C']
nCr = itertools.combinations(arr, 2)
print(list(nCr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

원리도 알았으니 간편하게 함수를 사용해도 괜찮을듯 하다ㅎㅎ

백트래킹이란?

• 모든 경우의 수를 고려하는 알고리즘
• 트리 탐색 알고리즘
• 해를 찾아가다가 해가 아니면 뒤로 돌아가서 다음 쪽으로 이동해 해를 찾아나가는 방법이다.
• DFS(깊이 우선 탐색)를 하다가 얘는 답이 될 수 없겠다 하면 쳐내버리는 가지치기 방법을 사용해 탐색하는 기법