AtCoder 2818문제를 GPT-5.5로 분석하여 테크닉 체계를 정리했다

요약

• AtCoder ABC 2818문제로부터, 문제를 풀 때의 고찰 태도를 16장 112규범의 테크닉 체계로 정리했습니다.
• 각 문제의 해법에 이르는 흐름을 GPT-5.5로 DAG(Directed Acyclic Graph, 유향 비순환 그래프)화하여, 공통되는 수법을 추출하고 있습니다.
• 알고리즘 명칭이나 데이터 구조 명칭이 아니라, 고찰 태도를 정리한 것이 필요했기에 만들었습니다.
• URL: https://ohatakenji.github.io/atcoder-techniques/

배경

필자는 몇 년 전에 AtCoder를 했었지만, 알고리즘을 외우는 것만으로는 문제를 풀 수 없었고, 그 어려움 때문에 금방 그만두었습니다.

그런데 최근 AI(이 문장에서는 LLM이나 주변 기술을 AI라고 부르기로 하겠습니다)의 발전으로 인해, 어느 정도의 정밀도로 AI가 경쟁 프로그래밍(Competitive Programming) 문제를 풀 수 있게 되었습니다.

그래서 AI에게 AtCoder 문제를 풀게 하고, 그 과정을 언어화함으로써 필요한 테크닉을 체계화할 수 있지 않을까 생각하여 시도해 보았습니다.

결과물

크게 나누면 규범, 수법, 문제의 3개 파트로 나뉩니다.

규범

문제를 풀 때의 고찰 태도를 정리한 것입니다. 어떤 상황이 보였을 때 어떤 선택지가 있는지를 정리하고 있습니다. 상황에 따라 GROUP BY(그룹화)한 수법이라는 위치를 가집니다.

수법

문제를 풀 때 자주 사용되는 수법에 대해 게재하고 있습니다.

문제

각 문제에 대해, 풀이 방법을 떠올리는 과정을 DAG로서 정리하고 있습니다.

참고로, URL 중 호스트명 부분 등을 atcoder.jp <-> ohatakenji.github.io/atcoder-techniques/로 전환함으로써, 문제문과 해석 DAG를 오갈 수 있도록 되어 있습니다.

제작 과정

대략 다음과 같은 파이프라인을 거쳐 테크닉 체계를 정리했습니다.

1. 각 문제를 풀기까지의 과정을 DAG로 해석하기

각 문제에 대해 해법에 이르는 흐름을 DAG로 작성하게 합니다.

노드는 고찰을 진행했을 때의 주요 포인트입니다. 에지는 그 포인트에 이르기까지의 전이(Transition)와 그 난이도 정보를 가지고 있습니다.

이용한 문제는 ABC001부터 ABC456까지의 2818문제입니다. 테크닉 체계의 추출 원천으로서 타당해 보였습니다.

ABC를 통해 필요한 지식을 한 차례 모두 커버할 수 있도록 설계되어 있습니다.

2. DAG에서 필요해 보이는 고찰 태도에 대해 「수법」 추출하기

전체 문제에 대한 DAG 형식의 해석이 끝나면, 공통적으로 사용할 수 있는 사고방식에 대해 수법으로서 추출합니다.

3. 상황 -> 수법 후보군이 되도록 「규범」으로 정리하기

추출된 수법을 상황별로 정리합니다. 어떤 상황이 왔을 때 무엇을 생각해야 하는지를 떠올릴 수 있게 해두면 좋을 것 같기 때문입니다.

이 단계에서 112개의 규범으로 정리할 수 있었습니다.

4. 가까운 「규범」을 「장」으로 정리하기

웹사이트로서 정리함에 있어 112개의 규범을 평면적으로 나열하는 것은 너무 많다는 점 때문에, 가까운 규범을 장으로 다시 정리했습니다. 결과적으로 16장 112규범으로 정리되었습니다.

제작에는 Codex를 이용했습니다. 합계로 $100/월 플랜의 weekly limit 2회분 미만의 토큰을 사용했습니다.

마치며

AtCoder ABC 2818문제로부터, 문제를 풀 때의 고찰 태도를 16장 112규범의 테크닉 체계로 정리했습니다. 지금까지 다루기 어려웠던 고찰 태도가 정리됨으로써 학습의 막막함이 경감된 것 같습니다.

그런데 필자는 AI를 이용하여 생데이터(Raw Data)를 공격적으로 변환·합성해 나가는 방향성에 가능성을 느끼고 있습니다. 이번에는 AtCoder 문제집으로부터 체계를 만들어 나가는 형태로 이 뒷주제(裏テーマ)를 다루었지만, 문제로부터 고찰 체계까지 다소 비약이 있는 것을 좋은 형태로 정리해 낼 수 있었다고 생각합니다.

Discussion