본문 바로가기
  • 시 쓰는 개발자
알고리즘/코테 스터디 (2024)

15651 N과 M (3)

by poetDeveloper 2024. 7. 23.

💡문제 분석 요약

  • N, M 값을 받고 1 ~ N까지의 숫자중에서 M개의 숫자를 중복 허용하여 출력한다.
  • 오름차순으로 출력한다.

💡알고리즘 설계

💡코드

n, m = map(int, input().split())
s = []

def backTracking(): # DFS를 이용함
    if len(s) == m: # m개가 모였다면 출력
        print(*s)
        return
    for i in range(1, n+1): # m개의 숫자가 모이는 과정인데, prev를 통해 중복 출력을 방지함.
        s.append(i)  # 1~n까지 값을 넣는 것이기 때문에 굳이 list 초기화 하지 않아도 됨
        backTracking()
        s.pop()


backTracking()

💡시간복잡도

  • 중복을 포함하므로 실제 출력해보면 O(N^M)이 됨을 알 수 있었다.

💡 틀린 이유

  • vistied를 지우지 않고 그대로 사용해서 틀렸다. 이번 문제는 중복을 허용하기 때문에 visitied를 오히려 쓰면 안되는 문제였다.

💡 틀린 부분 수정 or 다른 풀이

  • visited 삭제하고, 재귀 실행 조건을 삭제함. (for문 내에서 항상 재귀)
  • 1~n까지 N개의 원소를 담는 list를 선언하지 않고 for문으로 1부터 N까지 값을 바로 append 해주는 방식으로도 진행할 수 있었다.

💡 느낀점 or 기억할정보

  • 백트래킹의 탈출 조건을 항상 생각하면서 언제 append하고 언제 pop 하는지, 그리고 그 사이 백트래킹 재귀는 어디로 들어가야하는지 코드 "순서"를 잘 짜야한다.
 
반응형

'알고리즘 > 코테 스터디 (2024)' 카테고리의 다른 글

1182 부분수열의 합  (0) 2024.07.25
6987 월드컵  (5) 2024.07.24
15663 N과 M (9)  (2) 2024.07.22
1743 음식물 피하기  (5) 2024.07.21
2178 미로 탐색  (3) 2024.07.20