[코드트리 챌린지] K개 중 하나를 N번 선택하기(Simple) / k개 중에 1개를 n번 뽑기

 

하아.. 또 백트래킹에서 막혔다 

001 010 100 보자마자 느꼇다. 아 이거 이해하기 어려워서 넘겼던 문제가 나오네..

그리고 처참한 실력 진단 후 코드트리에서 2달후에 삼성코테에 합격할수있다고했다.

아니 당장 다음달에 삼성 코딩테스트 시작인데.......................................

천천히 너무 여유롭게 풀어서 문제였던걸까 아니면 하고 까먹고 하고 까먹고를 반복해서 그런가..

실력체크를 하고 상당히 착잡해졌다. 특히나 재귀함수 < bfs,dfs에서 필수인데 아직도 이부분을 이해못해서는 참..

bfs,dfs의 경우 재귀함수라기보단 탐색느낌이 강해서 크게 이해없이 하다보니 익힐수있엇는데

백트래킹같은경우는 아직도 헷갈린다. 

 

https://www.codetree.ai/missions/2/problems/n-permutations-of-k-with-repetition?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

그림으로 보면 

 

 

아래같은 느낌인데 솔직히 이걸 코드로 어떻게 구현하라고 물어보면 걍 한숨부터 나온다  

 

그러니 문제 조건에 따라 내가 풀수있을지 모르겠지만, 토론탭을 보니 어려워하는사람이 한트럭인것 같다.

즉 나만 어려운게 아니니 한번 다시 보자. 

 

 

1이상 k이하의 숫자를 고르는 행위를 N번 반복한다, 

K가 3이고, N이 2면, 

11

12

13

K가 5고 N이 3이면

111

112

113

114

115

121

122

123

124

이렇게 갈것이다. 

 

이걸 재귀함수 개념없이 푼다면 어떻게 할까? 

for문을 쓰면서 배열값을 차례대로 바꾸게 하고 넣고 빼고 이러면 될것같은데. 

재귀함수로 하면 더 쉽게 할수있다고한다. 

 

 

k,n = map(int,input().split())

answer = []

def debug():

    for elem in answer:

        print(elem,end=' ')

    print()

def choose(num) :

    if num == n +1 :

        debug()

        return

    for i in range(1,k+1) :

        answer.append(i)

        choose(num +1)

        answer.pop()

    return

choose(1)

 

 

choose(num) 함수에서 

answer.append(i) 배열에 넣은다음, 

그다음 choose (num+1)을 하는데

choose 에서 가리키는 num+1 은 그다음 에 해당하는 수를 넣는다고 보자.  

 

 

 

 

 

 

 

코드 트리에서는 이런식으로 순차적으로 이해할수있게 영상을 제공해줬는데 

솔직히 따라가면서 내가 문제를 풀면서 저걸 머리속에서 설계 할 수 있을까? 

간단화되게 이해해 본다면, 

k,n = map(int,input().split())

answer = []

def debug(): -> 그냥 배열에있는값출력 

 

    for elem in answer:

        print(elem,end=' ')

    print()

 

def choose(num) :

 

    if num == n +1 : -> 그다음 자리수일때 끝내게 한다. 

        debug()

        return

    for i in range(1,k+1) :

        answer.append(i) -> 출력할 배열값을 머리속에서 생각한다. 

        choose(num +1) -> 그다음 자리로 이동, 이녀석이 return 될때를 생각한다. 

        answer.pop() -> 출력한거 뺀다. 

    return

 

그렇다면 위에는 for 문이 있으니 

answer에 1,2,3,4,5 값이 차례대로 들어갈꺼고 그다음 자리수로 이동하고 1,2,3,4,5 가 들어간다. 그리고 필요없는 값은 pop으로 빠진다. 

그러면 위 구조를 알고있다면, 

(1,2,3,4,5)(1,2,3,4,5)(1,2,3,4,5) 의 자리수대로 배열을 각자 다 넣어볼수있다는것이다. 

이게 for 문보다 더 빠를지는 모르겠는데 적어도 backtracking 개념을 알아야하는게 필수니.. 

for문으로 떼우거나 하는짓은 최대한 지양해보자.

 

for문으로 해보려고하니 더 이상해진다 ㅋㅋ

그냥 백트래킹 익히자.