BAEKJOON 15649, 15650, 15651, 15652
15649 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
나의 처음 코드
백트래킹에서는 중요한 포인트 3가지 가 있다. 첫 번째 로는, 재귀로 계속 depth가 깊어져 갈 때 특정 조건으로 return하는 조건문을 만들어주는 것. 두 번째 로는, 재귀로 진입 한 후에 검사하는 것이 아니라 진입 하기 전에 적합한지 여부를 따져주는 것. 세 번째 로는, 적합여부를 판단하는 변수에 대한 적용과 해제이다. 세 번째 설명은 잘 와닿지 않겠지만, 전체 코드에서 다음과 같은 부분을 뜻한다.
check_list[i] = True #~~~ check_list[i] = False
전체 코드는 다음과 같다.
m, n = list(map(int, input().split()))
#m(숫자 범위), n(출력 갯수)
print_list = [] #출력할 숫자를 담고있는 리스트
check_list = [False] * (m+1) #적합여부를 판단해줄 리스트
def bt(depth : int):
if depth == n: #위에서 언급한 첫 번째 포인트
print(*print_list)
for i in range(1, m+1):
if check_list[i] == True: #위에서 언급한 두 번째 포인트
continue
check_list[i] = True
print_list.append(i)
bt(depth+1)
print_list.pop()
check_list[i] = False
bt(0) #함수 호출
결과는 정답입니다. 백트래킹이 어떻게 돌아가는지 이해를 한다면, 나머지 15650, 15651, 15652 문제들도 식은 죽 먹기이다.
15650 문제 코드
m, n = list(map(int, input().split()))
check_list = [False] * (m+1)
print_list = []
idx = 1
def bt(cnt : int):
if cnt == n:
print(*print_list)
return
for i in range(1, m+1):
if check_list[i] == True:
continue
#len(print_list) 조건이 앞인 이유는 뒤에껄 먼저 했을 경우 out of range error 가 난다.
#처음 n/m 문제와 다른 조건이 print_list[len(print_list)-1] > i 이다.
#문제를 읽어보면 알겠지만, 앞으로 새로 넣을 원소가 넣기 전 마지막 idx에 들어있는 값보다 크면 안된다.
if len(print_list) != 0 and print_list[len(print_list)-1] > i:
continue
print_list.append(i)
check_list[i] = True
bt(cnt + 1)
print_list.pop()
check_list[i] = False
bt(0)
15651 문제 코드
m, n = list(map(int, input().split()))
check_list = [False] * (m+1)
print_list = []
idx = 1
def bt(cnt : int):
if cnt == n:
print(*print_list)
return
for i in range(1, m+1):
print_list.append(i)
check_list[i] = True
bt(cnt + 1)
print_list.pop()
check_list[i] = False
bt(0)
15652 문제 코드
m, n = list(map(int, input().split()))
check_list = [False] * (m+1)
print_list = []
idx = 1
def bt(cnt : int):
if cnt == n:
print(*print_list)
return
for i in range(1, m+1):
#문제를 읽어보면 알겠지만, 앞으로 새로 넣을 원소가 넣기 전 마지막 idx에 들어있는 값보다 크면 안된다.
if len(print_list) != 0 and print_list[len(print_list)-1] > i:
continue
print_list.append(i)
check_list[i] = True
bt(cnt + 1)
print_list.pop()
check_list[i] = False
bt(0)
위 문제들은 코드 1~2줄만 차이나는 응용문제이다. 백트래킹의 기초를 이해하기 위해서는 꼭 풀어봐야할 문제이다.