2025.03.19

TIL(TODAY I LEARN)

---

정글에서 내준 문제를 다 풀고 백트래킹과 재귀함수 등 이해가 완전하게 되지않아서 추가적으로 백준에서 문제를 풀었다.
재귀함수랑 백트래킹 완전탐색 아직 내겐 너무 어려운 친구들이다.

📖 완전탐색과 백트래킹, 재귀함수

알고리즘 문제를 추가로 풀어보았는데 너무 어렵다.
수열이나 조합은 파이썬 내장 라이브러리가 존재한다. 여기서 오름차순이나 여러가지 조건이 추가되면 직접 구현을 하는게 편한거 같다.

[Silver III] N과 M (4) - 15652

문제 링크

import sys

input = sys.stdin.readline


def recursion(depth,n,m,current):
    if len(current) > 1  and (current[-1] - current[-2]) < 0:
                return
    if depth == m:
        print(' '.join(map(str,current)))
        return
    
    for i in range(n):
        recursion(depth+1,n,m,current+ [a[i]])

N, M = map(int,input().split())

a = [i for i in range(1,N+1)]

recursion(0,N,M,[])

• 내가 짠recursion 함수
• 첫번째 if : 비내림차순임을 검증 / 하나의 세트라도 내림차순이면 더이상 찾아 볼 필요없으므로 리턴
• 두번째 if : 재귀의 종료조건 / m개의 수를 골라냈으면 끝
• for문 : 다음 깊이에 출력할 옳은 배열을 인자로 하는 다음 재귀
• 중복이 가능하기 때문에 방문처리를 해줄 필요 없음

백트래킹 문제를 풀려면?

출처 : 주니온TV 아무거나 연구소

• 상태공간트리를 생각
• 다음 가지로 갈만한가?(유망한가?(promising?))
• 유망하다면 종료조건 / 재귀를 수행 구현
• 유망함수 구현
• 출력

알고리즘을 대하는 자세

오후에는 코치님께서 알고리즘에 대해 강의를 잠깐해주셨다.

• 프로그램 = 알고리즘 + 자료구조
• 알고리즘은 재능보다는 노력이 중요하다. 포기하지 마라.
• 재귀함수는 중요하다. 지금은 어렵더라도 조금만 연습하면 쉽게 할 수 있을 것이다.
• 재귀함수에서 점화식을 찾는 연습을해라 점화식이 곧 재귀함수다.
• n=3 정도일때를 생각하고 구현하면 좀 더 이해가 쉬울 것이다.

좋은 말씀을 많이 해주셨고 나도 더 노력해서 슈슈슉 문제를 풀고싶다.
재귀함수는 같은 구조가 결국 반복이 된다.
이런게 반복되는구나!는 알아차릴 수 있는데 이걸 코드로 구현하는 그런 능력이 아직 부족한 것 같다.
재귀 변수에 어떤게 들어가야 되는지, 종료조건을 어떻게 설정해야 하는지, 여러가지 능력이 부족한 것같다.