[공지사항] [‘코딩테스트 필수 알고리즘’ 강의를 듣고 이해한 내용을 바탕으로 직접 필기한 내용입니다. ] 👉🏻바로가기

백트래킹Permalink

• 모든 경우의 수를 확인해야 할때
  • for로는 확인 불가능 한 경우(깊이가 달라질때)

• Ex) 순열 :

  • M개에서 N개를 뽑을 때 순서 상관 있는 것

  • 1,2,3 중 2개를 뽑아야할 경우

• 백트래킹에서는 순열 처럼 깊이가 달라질 경우 단순히 for문 늘려서 사용 불가능

• 이러한 트리 구조로 구성되어 있음. 각 층은 for문으로 구현

• 					 0
          /   |   \
         1    2    3
        /\    /\   /\
       2  3  1  3  1  2
  

• def recur (num): #num은 재귀함수의 깊이
    if num == M:
      return
    else:
      for 1~ N :
        방문여부 확인
        1개 선택 결과값 추가
        + 방문여부 체크해줘야함.
        recur(num+1)
  

아이디어Permalink

• 1부터 N중에, 하나를 선택 (for 1 ~ N:)

• 다음 1부터 N부터 선택할 때 이미 선택한 값이 아닌경우(방문여부)

• M개를 선택할 경우 프린트

  • def recur(num):

    if num == M

    Print

시간복잡도Permalink

2억이 넘지 않으려면..

• N^N : 중복이 가능, N = 8까지 가능
• N! : 중복이 불가, N = 10까지 가능

자료구조Permalink

• 방문 여부 확인 배열 : bool[]
• 선택한 값 입력 배열 : int[]

백트래킹 기본문제 : 백준 15649Permalink

아이디어

• 백트래킹 재귀 함수 안에서, for 돌면서 숫자 선택(이때 방문 여부 확인)
• 재귀함수에서 M개를 선택할 경우 print

시간복잡도

• N! 이다. (10까지 가능), 문제에서는 8까지니깐 가능

자료구조

• 결과값을 저장 : int[]
• 방문여부 체크 bool[]

import sys
input = sys.stdin.readline

N,M = map(int, input().split(o))
result = []
chk = [False] * (N+1) # index에 바로 접근하기위해서다. chk[1-1]로 해야한는 것이 귀찮으니깐 미리 1을 더해줌

def recur(num):
  if num == M:
    print(' '.join(map(str, result)))
    return
  for i in range(1, N+1): # 1 ~ N까지 가기 위해
    if chk[i] == False:
      chk[i] = True
      result.append(i)
      recur(num+1)
      chk[i] = Flase #방문여부를 취소하고 빼주는 과정이 필요.
      result.pop()

recur(0)

TIPPermalink

• 백트래킹 문제는 N이 작음
• 재귀함수 사용할 때, 종료 시점 잊지말기!