백트래킹 문제 풀어보기

백트래킹 자체보다는, 내가 이 문제를 어떻게 접근했고, 무엇을 실수했으며, 개선해야할게 무엇인지 위주로 정리하겠다.

최초는 백준의 단계별 풀어보기 > 백트래킹에서 N과 M 이란 제목으로 비슷한 문제의 일부를 변형한 백트래킹 문제를 보고 풀어보려했다.

처음 보는 유형 임을 간과하고, 일단 머리 박치기로 풀어보았다. 또 너무 코드가 길게 나오지 않다보니 풀이를 잘 보지 않고 풀기도 했다.(이는 저번에도 내가 지적한 문제) 이전 풀이를 보긴 했으나 이도 ‘상위 몇개만’ ‘구글링해서만’ 보기도 했었다. (다들 직관적으로 생각할 수 있는 풀이였지만 문제를 낸 사람이 의도한바 와는 다소 빗겨나가는?)

문제는 N과 M(10)에서 발생했다. 어찌저찌 문제를 풀었지만, 내가 푼 방법을 설명하자니 뭔가 직관적으로 설명하기 어려운 느낌이자, 나도 약간 느낌적으로 이렇게 하면 풀리지 않을까 하고 풀었기에 다소 찜찜한 느낌이었다.

그러나 이번 문제의 경우에는 구글에서 다소 기존과 다르게 작성된 풀이가 많았다. 게다가 문제의 접근방식도 나와 다른 건지 이해하기 많이 힘들었고, 한시간쯤 문제를 읽어가며 겨우겨우 어떻게 작동하는지는 이해했으나, 왜 굳이 이렇게 짰지? 하는 의문이 많이 들었었다. 그래서 비슷한 풀이를 다 보았고, 이 접근법을 사용하는 유튜브 채널을 확인 할 수 있었다.

이번 문제 접근의 실책은, N과 M(1) 같이, 각 알고리즘 대표격의 유형이거나, 문제를 푼 사람이 굉장히 많아서, 양질의 코드와 영상을 쉽게 접할 수 있는 문제 였음에도 불구하고, 다른 접근성이 좋지 않은 활용 문제처럼 소수의 풀이만 접한 것이 문제였다.

다시 적자면 위처럼

• 특정 알고리즘의 대표격인 문제 (ex) N - queen ) 처음부터 대표적 풀이를 찾아보거나 문제의 접근 방법정도는 알고 효율적으로 풀자. 활용 문제가 아니라 기초부터 대가리박는건 크게 지식적 이득이 없는 것 같음.

• 사람들이 중요하다고 많이들 삽입해두거나 유명한 문제 일수록, 풀이를 많이 찾아보고, 유튜브 같은 플랫폼도 많이 뒤져보자. 이럴 수록 양질의 글, 영상 관련 컨텐츠가 많이 모여있어서, 이런 유형의 문제를 접근하는 이해가 잘되는 논리적 흐름, 타당한 근거등을 많이 알 수 있었음.

• 개발 블로그라고 너무 맹신하지말자. 그냥 직관적으로 풀어놓고 올리는 경우도 많고, 그거 배껴서 대충 올린 경우도 좀 많은 것 같음