7월 24일 월요일 코테 : 알고리즘 강의 - backtracking
재귀함수
1. 어떤 파라미터가 필요할지 (어떤 상태로 재귀호출을 만들지)
2. 어떤 종료조건을 확인할지
3. 재귀호출 내부를 어떻게 채울지
1과 관련해서 .. 과거엔 어떤걸 했고
지금부턴 어떤걸 할지 명시해줘야함
No. 1
- 문제 : K개 중 하나를 N번 선택하기(Simple) / k개 중에 1개를 n번 뽑기
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
코드
#재귀함수
#1. 현재 상태
#2. 종료조건
#3. 재귀함수 부분 작성
K,N = map(int,input().split())
arr=[]
def func(idx): # 0~ (idx-1) 번째 자리까지는 정했고,
# idx ~ N-1 번지 자리까지 정할예정
#종료조건 : 0 ~ N-1 번지 자리까지 정하면 종료
if idx == N :
print(*arr, sep=" ")
return
for i in range(1,K+1):
arr.append(i) # 값추가
func(idx+1) #다음자리 탐색
arr.pop() # 추가한값 빼기
func(0)쌤코드
새롭게 알게된것
재귀함수를 쓰는 경우 1 : for 문을 쓸수도 있지만.. for 문을 몇번 돌아야하는지가 계속 바뀔때 .. 비효율적이라 재귀함수 쓴는게 낫다..
* 재귀함수의 파라미터 개수는 상태복잡도와 같다.
*재귀함수를 짤때는.. 유일하게 중요한건.. 어디까지를 봤고, 어디를 결정할 차례인지 보는게 중요하다
-> 어디를 결정할지를 보여주는 idx 만 파라미터로 들고있으면 됨
개념 설명
쌤코드
n 자리 이진수 출력 연습한거
#재귀함수
#1. 현재 상태
#2. 종료조건
#3. 재귀함수 부분 작성
#이진수 문제
arr= []
n=3
def func(idx): # 0 ~ (idx-1) 자리 까지 작성한 상태
# idx ~ (n-1) 자리 까지 작성할예정
# 종료조건 : 0~ (n -1) 자리 까지 작성하면 종료
if idx == n :
print(*arr, sep="")
return
#재귀함수 부분
for i in range(2):
arr.append(i)
#다음자리 추가
func(idx+1)
arr.pop()
#함수시작
func(0)
No. 2
- 문제 : K개 중 하나를 N번 선택하기(Simple) / 아름다운 수
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)
코드
ㅇ# 호출 상태
# 종료 조건
# 호출 함수 내부 작성
n= int(input()) #n 자릿수의 아름다운 수
cnt = 0 #아름다운 수의 개수
# answer = [ 0 for _ in range(n)] # 아름다운 수 자체를 출력할필요없어서 필요없는 구문 인듯
def func(idx): # 0 ~ (idx-1) 까지는 아름다운 수를 채웠다.
# idx ~ (n-1) 자리 까지 아름다운수를 채울 예정이다.
#종료조건
if idx == n : # 0~ n-1 까지 아름다운 수를 채웠다면 끝
global cnt
cnt +=1
return
#재귀 호출 내부
#숫자를 추가한다.
for num in range(1,5) : # 1부터 4까지의 수를 해당 개수만큼 추가하겠다
if idx +num > n: #이부분에 idx+num > n 을 써야 답이 나오는게 잘이해가 안감..
break
#for i in range(num): # 출력할필요가 없는 부분이라.. 이거 적을필요가 없음..
# answer[idx+i] = num #값 추가
func(idx+num)
func(0) # 아름다운수 찾기 시작.. 함수 호출 해야함..
print(cnt)
새롭게 알게된것
주의할점
No. 3
- 문제 : K개 중 하나를 N번 선택하기(Conditional) / 특정 조건에 맞게 k개 중에 1개를 n번 뽑기
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)
코드
K,N = map(int,input().split())
#현재상태 조건
#종료조건
#호출함수 작성
answer = [0 for _ in range(N)]
def func(idx): # 0 ~ (idx-1) 까지는 조건만족하게 잘 정한 상태
# idx ~ (N-1) 번째 까지 조건만족하게 잘 정해야한다.
#종료조건 : 0 ~ (N-1) 까지 조건 만족하게 잘 정한경우
if idx == N:
print(*answer)
return
# 재귀 호출문
for num in range(1,K+1):
if idx <= 1 or answer[idx-1] != num or answer[idx-2] !=num :
answer[idx] = num #해당 번지에 숫자를 넣는 구문
func(idx+1) #다음번 재귀호출
answer[idx] = -1 #삭제의 의미
func(0)
새롭게 알게된것
이문제에서.. 0인덱스 와 1인덱스에는 아무거나 다 넣을수있다!!
=> ( idx <= 1 ) 이라는 문장으로 표현가능
주의할점
No. 1
- 문제 : N개 중에 M개 고르기(Simple) / n개 중에 m개 뽑기
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (codetree.ai)
코드
n,m = map(int,input().split())
#실행 조건
#종료조건
#재귀 호출 내용 작성
answer = [0 for _ in range(n)]
def func(idx): # 0 ~ (idx-1) 까지 정한상태
# idx ~ (n -1 ) 까지 정해야함
#종료조건 : 0 ~ n-1 까지 정하면 종료
if idx == n :
if sum(answer) == m:
#1 이 적힌자리의 인덱스넘버 +1 을 출력
for i in range(len(answer)):
if answer[i] ==1:
print(i+1,end=" ")
print()
return
#재귀 호출 : 1 개수가 m개가 되도록.. .해야함
#리스트에 추가
for j in range(1,-1,-1): # 맨처음에 0먼저 넣으면 오답나옴.. 처음부터 1을 먼저 넣도록 하자
if sum(answer) + j <= m :
answer[idx] = j
# 다음인덱스에 들어갈 숫자 재귀호출
func(idx+1)
answer[idx] = -1 #취소하는 의미
#함수 호출
func(0)
새롭게 알게된것
강사님 풀이 .. 0 을 기준으로 했고,,, 0의 위치를 새로운 배열에 넣어줬음.
새로운 배열의 길이가 3개( m개) 인거만 출력
주의할점
for j in range(1,-1,-1): # 맨처음에 0먼저 넣으면 순서가 반대로 나옴.. 처음부터 1을 먼저 넣도록 하자