[BOJ]N과 M(3)_15651_분할정복

• 알고리즘 유형 : 백트래킹
• 풀이 참고 : 블로그
• 문제 링크 : https://www.acmicpc.net/problem/15651

늘 언급하지만 해당 내용은 정확하지 않아 개발 공부에 도움이 되지 않습니다. 

그래서 당연히 귀한 시간 내주시어 지적해 주시면 감사 드리겠습니다. 

---

DFS와 백트래킹 정리

참고 링크 : https://chanhuiseok.github.io/posts/algo-23/

---

풀이 요약

1. 반복문 안에서 재귀를 하여 반복문이 한번 들어갈때마다 n개의 반복을 하게 된다.

2. 프린트 모양에 대한 부분은 join함수와 pop을 통해 구현 하였다.  

---

코드(python)

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

arr = []
def go():
    if len(arr) == m:           # 3.arr 리스트의 길이가 m이면 출력하고 회기
        print(' '.join(map(str,arr)))
        return
    
    for i in range(1, n+1):     # 1.출력 해야할 수가 1부터 n까지기 떄문에
        arr.append(i)           # 2.예를 들어 1이 처음 들어가고 해당 1을 기준으로 재귀를 돌며 반복
        go()
        arr.pop()               # 4.재귀가 들어갔다 나오면 1번째 인덱스 값 추출하여 다시 for 문을 돌게 한다. 

go()

---

배운 점, 배울 점

단순하지만 재귀에 대한 동작 플로우와 리턴조건 등 기본적인 개념이 많이 들어간 코드인 것 같다. 

아직 가슴으로 와닿지는 않는다. 더 공부하도록 하자.