[템플릿] 백준 문제 힌트, 풀이 및 코드 템플릿

앞으로 쓸 백준 문제의 힌트와 관찰 과정, 풀이를 쓰는 과정에서 어떤 생각으로 어떻게 작성할 것인지 기본적인 템플릿을 작성합니다.

백준 문제풀이 글의 목표는 다음과 같습니다.

 

1. 문제 풀이 과정 기록: 제가 문제를 풀 때 어떤 방식으로, 어떻게 생각하면서 해답에 도달했는지 기록합니다.

문제의 핵심 아이디어에 도달하는 데 어떤 과정을 거쳤는지, 어떤 포인트를 중점으로 보며 문제를 해결했는지 기록하며 비슷한 문제가 나왔을 때 더 쉽게 풀 수 있도록 합니다.

 

2. 알고리즘 학습자 및 문제 풀이자에게 힌트 제공: 문제를 풀다 보면 직접적인 정답이 아니라 약간의 힌트가 필요할 때가 있을 수 있습니다.

문제 풀이 시에 초기 접근 방식부터 핵심적인 아이디어를 찾는 과정까지, 미약하게나마 문제의 힌트를 제공하여 아예 처음부터 답안을 보기보다는 조금 더 본인 스스로 풀 수 있는 능력을 발전시킬 수 있게 합니다.

 

3. 문제 풀이 과정 공유: 단순 풀이뿐만 아니라 풀이 시에 어떤 접근 방식을 거쳤는지, 핵심적인 아이디어를 얻기 위해 관찰했던 과정은 무엇인지, 풀이 시에 유의할 점은 어떤 점들이 있을지 등 풀이 과정에서 있는 생각 절차들을 모두 작성합니다.

"대체 저런 생각은 어떻게 하는 걸까?"가 아닌, "저래서 저런 생각이 나왔구나" 싶은 정도까지 최대한 세세하게 풀이로 가는 길을 작성하고자 합니다.

물론 일부 문제들은 반짝이는 아이디어가 필요한 경우가 있겠지만, 그런 경우에도 어떤 관찰들을 통해 인사이트를 얻을 수 있었는지까지 작성합니다.

 

 

쓰는 글들의 대상 독자는 다음과 같습니다.

 

1. 골드 하위권~플레 하위권 수준의 문제를 풀고자 하는 사람들: 제가 이정도 실력이라.. ㅎㅎ

2. 풀이를 생각하다가 접근 방식부터 막힌다거나, 핵심적인 아이디어를 도저히 찾을 수 없는 사람들: 힌트만 보고 빠질 수 있도록 했습니다.

3. 문제 풀이뿐만 아니라 풀이 과정 및 증명 과정이 궁금한 사람들: 전 (대회가 아닌 이상) 웬만하면 전부 다 증명하면서 풀이를 전개하기 때문에, 대부분의 풀이 과정 및 증명을 찾을 수 있을 것 같습니다.

 

다만, 풀이 과정에 중점적으로 맞춰진 포스팅들이기에, 코드 자체에 대한 고찰은 많이 없을 것 같습니다.

가령, 세그먼트 트리를 사용하는 문제에서 세그먼트 트리의 구현을 어떻게 해야 하는지 등에 대한 내용은 따로 작성하지 않습니다.

또한, 특정 알고리즘을 단순히 구현하는 문제나 너무 웰-노운인 문제들은 따로 풀이를 작성하지 않습니다.

 

 

 

 

아래부터는 풀이 포스팅의 템플릿입니다.

어떤 부분들이 내용에 들어가고, 어떤 생각들을 중점으로 글을 작성하는지를 나타냅니다.

 

 

 

 

[템플릿]

 

https://acmicpc.net/problem/{문제 번호}

 

- 문제 링크를 답니다.

 

1. 문제

- 문제를 간략히 추상화하여 작성합니다.

- 문제를 풀기 위해 필요한 최소한의 조건들만 나열합니다.

- 문제를 너무 추상화하거나 조건을 풀어서 설명하여 문제 파트를 읽기만 해도 힌트가 되는 경우는 발생하지 않도록 주의합니다.

 

 

2. 힌트

 

- 문제 풀이에 필요한 힌트가 들어가는 곳입니다.

- 총 세 가지 힌트가 주어지며, 각 힌트는 접은 글 안으로 넣습니다.

- 힌트 1부터 힌트 3까지, 점점 더 자세한 힌트를 작성합니다.

- 구현 방식에 대한 내용은 그 자체가 중요한 아이디어가 아닌 이상 힌트로 기술하지 않습니다.

- 각 힌트에서 주로 어떤 내용이 들어가는지 접힌 글 안에 작성합니다.

 

힌트 1

문제를 풀기 위해 필요한 아주 기초적이고 기본적인 접근 방식을 서술합니다.

가령, "모든 경우를 전부 순회하기에는 너무 시간복잡도가 높다. 중복되는 경우를 어떻게 제거할 수 있는지 생각해 보자", "예제 입력을 직접 풀어 보며 규칙을 찾아보자" 등 문제에 직접적인 힌트가 되는 내용 작성을 지양하고, 풀이 초기에 할 수 있을법한 내용을 작성합니다.

아예 잘못된 방향으로 문제 풀이를 생각하고 있는 경우에 유효한 힌트입니다.

문제 풀이의 약 20%정도에서 생각할 수 있을만한 내용을 서술합니다.

 

힌트 2

문제를 풀기 위해 알아야 하는 기본적인 도구와 관찰 방식을 간접적으로 제시합니다.

당연하지만 놓치기 쉬운 관찰 내용이나 조건들을 서술하거나, 핵심적인 관찰을 하기에 앞서 중점적으로 보아야 하는 기본적인 내용들을 서술합니다.

또는, 특정 알고리즘을 알아야 하거나 수학 공식들이 사용되는 경우에 해당 알고리즘의 내용과 공식들을 작성합니다.

이때, 특정 알고리즘을 사용해야 하는 것이 너무나도 뻔한 것이 아닌 이상 알고리즘의 내용을 직접 설명하는 것은 지양합니다.

문제 풀이의 약 40~50% 사이쯤에 생각할 수 있을만한 내용을 서술합니다.

 

힌트 3

문제를 풀기 위해 필요한 핵심적인 아이디어를 간접적으로 제시합니다.

충분한 관찰 이후에 나오는 인사이트를 얻기 위해 중점적으로 살펴보아야 하는 내용들을 서술합니다.

이미 독자가 충분한 관찰을 했다고 가정하고 작성하기에, 아예 처음 열어보면 약간 뜬금없어 보일 수 있습니다.

핵심적인 아이디어에 접근하기 위하여 필요한 중요한 관찰 및 질문을 통해 힌트를 제공합니다.

아예 직접적으로 핵심 아이디어를 제시하는 것은 지양합니다.

문제 풀이의 약 70~80% 사이쯤에 생각할 수 있을만한 내용들을 서술합니다.

 

 

3. 문제 관찰 과정 및 풀이

 

3-1. 문제 관찰 과정

- 문제 관찰 과정을 상세하게 기록합니다.

- 필자가 문제를 풀면서 처음에 가졌던 생각부터, 어떤 순서대로 관찰을 했는지 작성합니다.

- 주로 예제 입력을 토대로 관찰하는 방식을 서술하거나, 어떻게 특정 관찰을 시도하게 되었는지까지 상세하게 기록합니다.

- 간단한 예시부터 생각하기, 순서를 바꿔서 생각하기, 순서를 정해서 생각하기 등, 문제를 풀 때 의식하고 사용할 수 있는 문제 풀이 기법도 서술합니다.

 

3-2. 문제 풀이

- 직접적인 풀이를 제시합니다.

- 문제 관찰이 모두 끝난 후에, 어떤 테크닉이나 어떤 구현 방식을 사용하여 구현해야 하는지를 기술합니다.

- 풀이 방식과, 그렇게 풀이해도 되는 이유를 증명하거나 납득할 수 있도록 설명합니다.

- 보통은 문제 관찰 과정과 문제 풀이가 한 단락 안에 함께 들어있지만, 풀이가 길어지거나 관찰과 구현이 거의 유사한 수준으로 구현의 비율이 높은 경우에는 나눠질 수 있습니다.

- 구현 시에 주의해야 할 점들이나, 실수하기 쉬운 점들도 제시합니다. (문제 제한 조건에 따른 자료형 선택 등)

 

4. 코드

- 해답 코드를 작성합니다.

- 보통 따로 주석을 작성하지는 않으나, 풀이 시에 필자가 작성한 주석의 경우 들어있을 수 있습니다.

// 코드는 이렇게 코드블럭에 삽입됩니다.
// 코드에 대한 자세한 설명은 일반적으로 생략합니다.
// 코드가 너무 길어지거나 필자가 보기에도 너무 더러워 보인다면, 간략하게 의사 코드로 작성할 수 있습니다.
// 보통 의사 코드는 <코드> 부분이 아니라, <풀이> 부분에 있을 예정입니다.

 

5. 여담

- 풀이 중에 필자가 실수한 점들이나, 풀이 중에 생각했던 잘못된 풀이 등 실제 풀이 과정에는 큰 영향이 가지 않는 소소한 내용들을 작성합니다.

- 다른 풀이가 있다거나, 정해가 아니지만 그래도 풀리기는 하는 방식을 이곳에 서술합니다.

- 문제 풀이 꼼수도 이곳에 작성합니다. (예: "그냥 1번부터 10번까지 규칙을 대강 나열하면 ~~수열과 비슷해 보이므로, 이를 구현하여 대충 제출해도 Proof By AC로 맞았습니다!!를 받을 수는 있습니다." 와 같은...)

- 그냥 심심해서 써놓은 잡담들도 여기에 들어갑니다.