백트래킹
[Algorithm] 백트래킹 (Backtracking)
[Algorithm] 백트래킹 (Backtracking) 백트래킹이란, 주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 말한다. 답을 찾는 도중 답이 아니어서 막히면, 되돌아가서 다시 답을 찾아간다. 단, "조건을 만족" 할때 만이다. 즉, 모든 경우의 수를 모두 찾는 것보다 경우에 따라 훨씬 빠를 수 있다. 주로 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현한다. 백트래킹 기법의 유망성 판단 어떤 값이 해가 될만하다면 유망하다(promising)고 하며, 유망하지 않은 값에 가지 않는 것..
[BaekJoon] 백준 6603번 로또
[BaekJoon] 백준 6603번 문제이름 문제: www.acmicpc.net/problem/6603 내코드 이 문제는 백트래킹으로 풀었다. 주어진 숫자들에서 6개의 숫자를 선택해서 사전순으로 나열하고 출력하면 된다 out 변수에 선택된 6개의 숫자를 차곡차곡 넣어준다. visited 리스트에 해당 순서의 숫자가 선택되었는지, 안되었는지 true, false로 기록해준다. dfs와 비슷한 방식이다. out[0]을 1이라고 선택하면, out[1]을 2로 선택한 경우를 쭉 보고, out[1]을 3으로 선택한 경우를 쭉 확인하는 방식으로 간다. 각각의 경우를 확인하면 pop을 해서 다음 경우를 확인하게 된다. out의 길이가 6이 되면 출력을 해준다. # BaekJoon 6603.py 로또 def solve..