PS 공부법, 아이디어 백트래킹 (Idea Backtracking)

[창의력에 대한 이데올로기]

근 1년간 PS(Problem Solving)를 공부하면서 저의 명확한 공부법이 없었습니다. 하지만, 지금껏 써온 블로그 글을 읽어보면 어떤 공부법이라 말할 수가 없었을 뿐이지 나름의 규칙(?)을 파악할 수 있었습니다.

 

공부법을 소개하기 앞서 PS에 대한 필자의 이데올로기를 말해드리고 싶습니다. PS나 코딩 테스트는 개개인의 알고리즘 지식과 이를 응용한 개개인의 창의력을 확인하는 대회 혹은 테스트라고 생각합니다.

 

그중에 창의력은 '자기 자신의 라이브러리'에 얼마나 많은 지식이 있으며 이를 어떻게 활용하는지에 따라 드러난다고 봅니다. 즉, '창의력은 갑자기 번뜩이는 아이디어가 아니라 개개인의 베이스에서 여러 가지가 응용 or 융합되어 나온다'는 이데올로기를 가지고 있다고 말씀드립니다. 

 

이를 바탕으로 지금 설명하려는 공부법이 나오게 되었습니다.

---

[개요]

PS를 공부하다가 안 풀리는 문제에 맞닥뜨리게 되면 구글링을 하여 해당 문제에 대한 Solution을 확인하게 됩니다. Solution에서 문제에 대한 아이디어를 알게 되고, 이를 공부하여 문제를 풀면서 기록을 하거나 기억을 하려고 하면서 학습을 하게 됩니다. 여기서는 아이디어 그 자체를 공부하게 됩니다.

 

문제에 대한 How는 풀리지만, Why는 풀릴 수가 없어서 답답한 때가 있었습니다. '어떻게 이런 생각을 한 거지?'와 같은 물음에 대해서 말입니다. 저를 포함한 대부분은 How에 대해서만 공부를 하고 넘어가게 되지만 늘 찝찝함이 남아있고, 문제를 풀수록 응용력은 미미하게만 늘어갔습니다.

 

앞서 설명드린 창의력에 대한 이데올로기에는 적합한 공부법이었지만, 효율적인 공부법은 아니었습니다.

---

[예시 및 활용]

그래서 시간을 더 쓰더라도 How에서 그치지 않고, Why에 대해 공부해봤습니다. 이 글을 쓰게 된 이유를 가지게 된 직전 포스팅을 가져와서 아이디어 백트래킹 공부법에 대한 예시를 설명해보겠습니다.

https://draw-code-boy.tistory.com/436

백준 1854번: K번째 최단경로 찾기 (C++)

 

이 문제는 풀리지 않아서 구글링하여 Solution을 참고했습니다. 참고한 Solution에 대해서는 다음과 같이 정리할 수 있었습니다.

 

How)

• dist 배열 선언이 아닌 배열 형태의 heap(Priority Queue) 선언으로 문제를 풀 수 있다.

 

간단하게 정리할 수 있었지만, Why는 풀리지 않았습니다. Why에 대해 작성해본 결과

Why)

• 기존에는 dist 배열을 선언하여 계속 노드에 대한 최솟값으로 할당을 했다.
• 문제에서는 다른 방식으로 응용하여 최솟값을 할당을 하지 않고, 각 노드마다 K개의 최솟값을 가지고 있게 해야 한다.
• 그러한 이유에서 '배열의 각 노드에 대한 최솟값 할당 -> Priority Queue의 각 노드에 대한 최솟값 push'

 

사실 이게 전부입니다. 배열이 아닌 Priority Queue를 사용했다. '왜 사용했을까?' 라는 질문에 대한 답이죠.

 

문제에 대한 Solution Flow Chart는 다음과 같이 작성할 수 있겠습니다.

(Flow Chart는 물론 Solution을 적어 올린 작성자와 다를 것입니다.)

문제 읽기 -> 각 노드마다 K개의 최솟값이 필요하다. -> 기존 Dijkstra는 배열을 사용하여 최솟값을 할당 -> 할당이 아닌 각 노드마다 Priority Queue를 만들어 K개의 값을 저장하도록 하자.

정리까지 하게 되면 저 부분에 핵심 아이디어가 있구나를 알게 되면서 추가적으로 학습할 것이 보입니다.

• 기존 Dijkstra의 응용 및 차이
• 차이점을 두는 데에 있어서 Priority Queue의 활용
• Priority Queue라는 자료 구조 존재에 대한 리마인드

 

How에서 Why로 가서 더 뜯어보면 이 문제는 되려 간단한 것들에 대한 조합입니다. 이렇게 공부하면 더욱 의미가 있게 다가왔습니다. 하나를 뜯어보니 공부할 것이 간단한 몇 개로 나뉘었다는 것입니다. 그리고, 장황하게 위에서 설명한 것에 비해 공부법이 그렇게 대단하지도 않고요:)

 

그리고, How까지만 공부했을 때 알게 된 지식은 다른 문제를 풀 때 응용할 수가 없었습니다. 제한적인 상황에서만 해당 지식을 베이스에서 가져와 사용할 수 있기도 하고, 그런 식으로 만 문제를 대하기엔 How까지의 지식은 대부분 일회용이니까요.

 

Why에서 나온 Small Idea를 가지고 앞으로 풀 문제에 대해 Idea를 던져볼 수 있습니다.

• Dijkstra를 어떻게 바꿀 수 없는가?
• 최솟값을 할당하는 게 아닌 최솟값들을 담을 수는 없는가?
• 최솟값들을 담는 데에는 어떤 자료 구조를 쓰는가?

 

커다란 복잡한 문제에 커다란 복잡한 솔루션을 갖다 대는 것이 아닌 커다란 복잡한 문제를 분할하여 작고 간단한 문제들로 두고, 작고 간단한 솔루션을 조합하여야 한다는 겁니다.

 

오히려 How 공부법은 새로운 알고리즘을 공부할 때 적합한 것 같습니다. (물론 확실한 이해를 위해서는 Why까지도 필수입니다.)

 

즉, 공부법에 대해 정리해보면

• 어떻게 풀었는가(How)에서 왜 이런 생각을 했는가(Why)까지 접근한다.
• Why에서 나온 간단한 아이디어들을 공부해라.
• 이 아이디어들을 다음 문제들에서 응용해보자.

 

설명한 공부법을 아이디어 백트래킹(Idea Backtracking)이라 한 이유는 솔루션을 제공한 사람이 어떻게 이런 생각했을까를 솔루션(Big Idea)에서 그치지 않고, 제공한 사람의 원초적인 생각(Small Idea)까지 돌아간다고 생각하여 백트래킹(Backtracking) 기법을 차용하여 이런 이름을 붙여봤습니다.

---

[마무리]

아이디어 백트래킹이란 공부법은 이미 누구나 무의식적으로 체화된 공부법으로 사용하고 있었을지도 모릅니다. 그럼에도 글을 쓰면서까지 소개를 하고 싶은 이유는 사실 모든 문제가 복잡하고, 풀 수 없을 것처럼 보이지만 열어보면 간단한 것들의 조합이라는 걸 전달하고 싶었기 때문입니다. 즉, 어려운 문제에 부딪혀서 못 풀고 있다고 할 지라도 좌절감을 가질 필요도 없다는 뜻이기도 합니다.

 

Big Idea까지 공부했을 때는 내가 이렇게 멍청한가를 체감하면서도 Small Idea까지 갔을 때는 이렇게 간단한 것이었는데 조금만 더 생각해볼 걸이라는 아쉬움과 공부할 지식까지 가져가며 더 앞을 내다볼 추진력이 생기고, 앞으로의 문제에서는 Small Idea로써 던져볼 수 있는 아이디어들이 많이 생기게 됩니다.

 

그리고, 모든 PS의 문제가 복잡해 보이지만 간단한 것들의 조합이라고 생각하니 'PS가 더 매력적으로 다가오고, 누구나 어렵지 않게 할 수 있다는 것' 이를 전달해드리고 싶기 때문은 아니었나를 생각해봅니다.