💡문제 분석 요약
- N, M 값을 받고 1 ~ N까지의 숫자중에서 M개의 숫자를 중복 허용하여 출력한다.
- 오름차순으로 출력한다.
💡알고리즘 설계
- 이전에 풀었던 N과 M(9) 문제처럼, DFS를 이용한다.
- m개의 원소가 모이면 print해주는 탈출조건을 작성해준다.
💡코드
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 |