7월 24일 월요일 코테 : 알고리즘 강의 - backtracking

재귀함수

1. 어떤 파라미터가 필요할지 (어떤 상태로 재귀호출을 만들지) 
2. 어떤 종료조건을 확인할지 
3. 재귀호출 내부를 어떻게 채울지

 

1과 관련해서 .. 과거엔 어떤걸 했고

지금부턴 어떤걸 할지 명시해줘야함 

No. 1

 

 

-  문제 : K개 중 하나를 N번 선택하기(Simple) / k개 중에 1개를 n번 뽑기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 (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)

 

새롭게 알게된것 

 

 

 

주의할점

 

 

함수를 작성하고... 

함수를 호출해야 .. 아름다운수를 찾기시작함. 

 

func(0) # 아름다운수 찾기 시작.. 함수 호출 해야함..

 

 

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을 먼저 넣도록 하자