WIL_03 : 삽질은 옳다 - [백준] 15649번 N과 M (1)

삽질은 옳다.

삽질한 시간과 기억의 깊이는 비례한다.

이번 WIL에서는 한 주 동안 풀었던 백준 문제들 중 '삽질 TOP 5' 안에 들어간 'N과 M(1)' 문제를 리뷰해 보고자 한다.

 

---

 

백준 15649번 문제

 

문제 풀이

오늘의 문제는 백트래킹 전략을 이용해 문제를 해결할 수 있다.

 

백트래킹이란 퇴각검색이라고도 하는데

상태 공간 트리를 DFS(깊이우선탐색)의 방식으로 불필요한 경우를 배제하며

원하는 해답에 도달할 때까지 탐색하는 전략이다.

 

백트래킹에서 중요한 특징은 '가지치기'다.

이는 나무에서 불필요한 가지를 제거하듯 탐색 중 불필요한 경우를 제거하여 처리속도를 빠르게 향상시키는데에 도움을 준다.

 

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


def back():
    if len(stack) == m:
        print(' '.join(map(str, stack))
        return
    for i in range(1, n+1):
        if i in stack:
            continue
        stack.append(i)
        back()
        stack.pop()

back()

 

위의 코드를 보면

'stack'이란 변수명에 빈 리스트를 만들었다.

이는 아래 위치한 'back()' 함수가 실행되는 동안 조건에 만족하는 수열을 담을 리스트다.

 

함수 안에서는 재귀호출이 이루어지기 때문에 함수 첫 부분에 재귀호출을 멈출 <조건문>을 넣어주었다.

<조건문>의 내용으로는 수열의 길이 m과 지금까지 담긴 스택이란 리스트 안의 개수가 같아지게되면

'stack' 안의 수열을 출력함과 동시에 함수를 마치도록 하였다.

 

다음으로 <반복문>을 살펴보면

조건내용이 1부터 n까지의 자연수 중에서 고르는 것이므로, 범위를 1부터 n+1까지로 설정했다.

또한 조건 내용 중 중복 없이 m 개를 골라야 하기 때문에

반복 중인 자연수가 'stack' 리스트 안에 이미 들어가 있다면 반복 중이던 자연수를 포기하고 새로운 자연수를 반복하도록 하였다.

하지만 중복되지 않는다면 다시 'back()' 함수를 실행하여 또 다른 경우의 수를 탐색하게끔 하였다.

마지막으로 'back()' 함수를 마치게 되면

'pop()' 메소드를 이용해 가장 마지막에 추가한 'stack' 리스트 안의 요소를 빼는 작업을 수행하도록 하였다.

 

마치며

아무것도 몰라 막막했던 알고리즘 문제풀이를 2주간 진행하면서 느낀 소감은

아직 한참 부족하지만, 조금은 어떻게 공부해 나아가야할지 감각을 기를 수 있었다.

2주간 하루도 빠짐없이 풀었던 백준 문제들이 거의 50문제.

파이썬 문법도 처음 접해 첫 문제부터 너무 당황했던 기억이 생생하다.

지금은 (구현은 아직 익숙지 않지만..) 문제 이해와 더불어 구현방법에 대한 아이디어가 떠오른 다는 거에 감사하다.

첫 날 문제 이해만 몇시간이 걸린 때를 생각하면 2주간 성장한 사실이 기적에 가깝지 않을까..?

 

새로운 주차가 시작됐지만 

감각을 잃지 않으려면 꾸준함은 필수!

1일 1문제는 꼭 지켜보도록 노력해본다.