[프롬프트] 특정 알고리즘(예: 다익스트라) 단계별 풀이 프롬프트 - 최적 프롬프트 레시피
💡 한 줄 요약: "다익스트라 설명하고 코드 짜줘"라는 단순 요청 시 발생하는 중간 상태 추적 생략(Step-skipping), O(V²) 비효율적 배열 탐색, 경로 역추적 누락을 방어하고, 상태 전이 테이블(State Transition Table)과 최소 힙(heapq) 기반 O((V+E)log V) 최적 구현 및 최단 경로 복원(Path Reconstruction)을 완전하게 도출하는 실전 프롬프트 레시피입니다.
1. 페인포인트 & 작업 목표
- 실제 작업 시나리오: Cursor, Claude Code, Windsurf, Copilot, ChatGPT 등 AI 코딩 환경에서 코딩 테스트 대비, 네트워크 라우팅 최적화, 최단 경로 길찾기 엔진 구현을 위해 다익스트라(Dijkstra) 알고리즘의 단계별 분석과 구현 코드를 요청하는 상황.
-
단순 프롬프트 요청 시 발생하는 4대 실패 원인:
- 중간 상태 추적 생략 (Step-skipping): 우선순위 큐(PQ)와 방문 집합, 거리 테이블 갱신 과정 없이 완성된 코드만 툭 던져 원리 학습 불가능.
- 비효율적 자료구조 채택 (O(V²) 배열 탐색): 최소 힙(heapq) 대신 1차원 리스트 선형 탐색 코드가 생성되어 대규모 그래프에서 타임아웃(TLE) 발생.
- 최단 경로 역추적 (Path Reconstruction) 누락: 단순 거리 숫자만 리턴하고 실제 지나간 경로(A ➔ C ➔ D ➔ E) 복원 로직 누락.
- 음수 가중치 한계 무시: 다익스트라의 그리디 특성상 음수 간선 적용 불가 한계를 사전 방어하지 않음.
-
최종 해결 목표:
- 상태 전이 테이블 (State Transition Table) 강제: 노드별 큐 변화와 거리 갱신 과정을 마크다운 표로 시각적 추적.
- 최소 힙(heapq) 기반 O((V+E)log V) 최적화: 프루닝(Pruning) 로직이 포함된 견고한 파이썬 구현체 도출.
- 선행 노드(prev) 기반 경로 복원 유틸리티 완비: 시작 노드부터 목표 노드까지의 실제 최단 경로 자동 복원.
2. 프롬프트 레시피 비교
3. 실행 결과 비교: 5개 노드 가중치 그래프 실전 추적
노드 A에서 출발하여 E까지 도달하는 가중치 방향 그래프 [A➔B: 4, A➔C: 2, C➔B: 1, C➔D: 5, B➔D: 1, B➔E: 3, D➔E: 1]의 레시피 B 실행 결과입니다.
📋 레시피 B가 자동 생성한 상태 전이 테이블 (State Transition Table)
| Step | 추출 노드 (Cost) | 우선순위 큐 (PQ) 상태 | 방문 집합 | 최단 거리 테이블 (A, B, C, D, E) |
|---|---|---|---|---|
| 0 (초기화) | - | [(0, A)] | {} | A:0, B:∞, C:∞, D:∞, E:∞ |
| 1 | A (0) | [(2, C), (4, B)] | {A} | A:0, B:4, C:2, D:∞, E:∞ |
| 2 | C (2) | [(3, B), (4, B), (7, D)] | {A, C} | A:0, B:3 (갱신), C:2, D:7, E:∞ |
| 3 | B (3) | [(4, D), (6, E), (4, B), (7, D)] | {A, C, B} | A:0, B:3, C:2, D:4 (갱신), E:6 |
| 4 | D (4) | [(5, E), (6, E), (4, B), (7, D)] | {A, C, B, D} | A:0, B:3, C:2, D:4, E:5 (갱신) |
| 5 | E (5) | [(6, E), (4, B), (7, D)] | {A, C, B, D, E} | A➔E 최단 거리: 5 / 최단 경로: A ➔ C ➔ B ➔ D ➔ E |
📊 프롬프트 품질 비교 체크포인트
| 품질 검증 항목 | ❌ 레시피 A (기본형) | ⚡ 레시피 B (실무 종결형) |
|---|---|---|
| 단계별 상태 테이블 | 생략 (블랙박스 줄글 설명) | 완전 명시 (큐/방문/거리 변화 추적) |
| 시간 복잡도 | O(V²) 위험 (단순 1차원 리스트 탐색) | O((V+E)log V) 보장 (heapq 최소 힙) |
| 최단 경로 역추적 | 누락 (최단 거리 스칼라 값만 리턴) | 완비 (prev 기반 실제 노드 시퀀스 복원) |
| 음수 가중치 방어 | 무시 (음수 사이클 시 무한 루프 위험) | 입력 검증 + 벨만-포드 대안 안내 |
4. 메커니즘 심층 분석 (왜 차이가 나는가?)
1. "State Transition Table" 지시어가 만든 체인 오브 소트(CoT) 강제 효과
LLM에게 마크다운 표 형태의 스텝별 상태 기록을 요구하면, 모델이 내부적으로 각 노드의 완화(Relaxation) 조건을 순차적으로 연산한 후에 최종 코드를 도출합니다. 이는 논리적 건너뛰기나 중간 연산 할루시네이션을 원천 차단합니다.
2. 최소 힙(heapq)과 스튜(Stale) 엔트리 프루닝의 성능 보장 원리
파이썬의 heapq는 decrease-key를 직접 지원하지 않으므로 기존 노드의 갱신된 거리값이 큐에 중복 삽입됩니다. if current_cost > dist[curr]: continue 프루닝을 강제해야만 중복 엔트리가 즉시 무시되어 O((V+E)log V) 복잡도가 완벽히 지켜집니다.
5. 실전 응용 팁 & 커스텀 가이드
🛠️ 바로 쓰는 범용 알고리즘 분석 플레이스홀더 템플릿
You are a Principal Algorithm Engineer. Trace and implement {ALGORITHM_NAME} for {PROBLEM_DESCRIPTION}.
Strict Requirements:
1. Provide a step-by-step state transition table showing all data structure changes per iteration.
2. Provide production-grade implementation in {LANGUAGE} targeting O({TIME_COMPLEXITY}) time and O({SPACE_COMPLEXITY}) space.
3. Validate edge cases: {EDGE_CASES_LIST}. Include complete test cases with assertions.
💡 실무 팁: 음수 가중치가 포함될 수 있는 금융/차익거래 네트워크에서는 다익스트라 대신 벨만-포드(Bellman-Ford)를 요청하고, 지도 길찾기 서비스에서는 휴리스틱 거리를 더한 A* (A-Star) 알고리즘으로 프롬프트의
{ALGORITHM_NAME}을 교체하여 재사용하세요.
