알고리즘 문제 구현 순서

0️⃣ 문제 재정의 (Problem Reframing)

“어떤 방법으로 무엇을 계산해야 하는가?”를 일반화하는 단계

❗ 구현 방법을 정하는 단계가 아니다
❗ 알고리즘 이름을 붙이는 단계도 아니다

해야 할 일

1. 입력 / 출력 명확화
2. 핵심 요구사항 추출
3. 제약 조건 해석
   • 제약 조건은 선택지를 줄이고 알고리즘을 강제한다
4. 엣지 케이스 식별
5. 알고리즘적 재정의
   • “무엇을 계산하는 문제인가?”를 한 문장으로 치환

예

N개의 수가 주어진다.
→ 각 위치 i에서 끝나는 최대 연속합을 구한다
→ 그 중 최댓값을 선택한다

📌 이 단계의 산출물
→ 문제의 방향 (O(N)? 상태 개수? 중복 여부?)

---

1️⃣ 의사코드 작성 (Behavior-Only)

“무엇을 한다”만 남기고 “어떻게 한다”는 비워둔다

규칙

• 반복, 조건, 흐름만 표현
• 자료구조/라이브러리/언어 문법 금지

초기 상태를 설정한다
상태를 하나 꺼낸다
다음 상태로 이동한다
조건을 만족하면 결과를 갱신한다

📌 목적
→ 행위의 흐름을 고정
→ 구현 선택의 자유 유지

---

2️⃣ 데이터 추출 (State Extraction)

문제를 풀기 위해 “반드시 기억해야 하는 정보”를 나열

추출 대상

• 상태(state): 위치, 값, 시간, 방향, 인덱스 등
• 비교 기준: 최대 / 최소 / 방문 여부
• 중복 가능성: 같은 상태 재방문 의미 있는가?

이 단계에서 드러나는 것

• 상태 개수 규모
• 상태 전이 방식
• 메모리 요구량

📌 이 단계는 자료구조 선택의 근거를 만든다

---

3️⃣ 알고리즘 · 자료구조 선택 (Forced Decision)

선택이 아니라 귀결

판단 기준

• 상태 중복 → DP / visited
• 최단/최대 → BFS / Dijkstra / PQ
• 순서 중요 → stack / queue
• 키 기반 조회 → map / unordered_map
• 정렬 유지 → set / priority_queue / sorted vector

📌 핵심 원칙

의사코드 + 데이터 형태가 결정되면
알고리즘과 자료구조는 자동으로 좁혀진다

 

 

이 흐름은 크게 [데이터의 순서] → [정렬 유지 여부] → [검색 및 수정 위치] 순으로 진행된다.

---

1단계: 데이터의 출입 순서가 중요한가? (Order is Important)

• YES (특정한 출입 규칙이 필요한 경우):
  • 나중에 들어온 게 먼저 나가야 하나요? (LIFO) → stack
  • 먼저 들어온 게 먼저 나가야 하나요? (FIFO) → queue
  • 우선순위가 높은 게 먼저 나가야 하나요? → priority_queue
• NO (일반적인 저장 및 탐색이 목적인 경우): 2단계로 이동

---

2단계: 데이터를 항상 정렬된 상태로 유지해야 하는가? (Keep Sorted Elements)

• YES (항상 정렬되어 있어야 함):
  • 주된 목적이 순차적 순회(In-order Traversal)인가요? → vector (sorted)
  • 주된 목적이 키(Key)를 이용한 빠른 검색인가요? → 4단계(정렬형 검색)로 이동
• NO (정렬이 필수적이지 않음): 3단계로 이동

---

3단계: 데이터의 삽입/삭제가 어디서 일어나는가? (Insertion/Erasure)

• 중간(Middle)에서 빈번하게 일어나는가?
  • YES → 데이터의 위치(Iterator)가 고정되어야 하고 순회가 잦은가요? → list
• 맨 앞(Front)에서 빈번하게 일어나는가?
  • YES → deque
  • NO → 크기 변화가 심하지 않다면? → vector

---

4단계: 키(Key)를 이용한 검색이 필요한가? (Look-up Keys)

2단계에서 '정렬형 검색'을 선택했거나, 1단계에서 순서가 중요하지 않다고 판단된 경우입니다.

• 중복 데이터(Duplicates)를 허용하는가?
  • NO (유일한 키):
    • 정렬이 필요한가요? → YES: map / set | NO: unordered_map / unordered_set
  • YES (중복 허용):
    • 정렬이 필요한가요? → YES: multimap / multiset | NO: unordered_multimap / unordered_multiset

---

요약: 결정적인 질문 순서

1. 동작 규칙: 스택/큐 형태인가?
2. 검색 방식: 키(Key)를 써서 찾는가, 그냥 데이터를 쌓아두는가?
3. 정렬 여부: 데이터가 항상 정렬되어 있어야 하는가? (정렬 여부에 따라 unordered 결정)
4. 수정 위치: 주로 어디에 데이터를 넣고 빼는가? (앞, 뒤, 중간)
5. 중복 여부: 같은 데이터를 여러 번 넣을 수 있는가? (multi 결정)

---

4️⃣ 함수 도출 (Responsibility Split)

구현을 시작하기 전에 “책임 단위”를 먼저 나눈다

해야 할 일

• 기능을 더 이상 쪼갤 수 없을 때까지 분리
• 함수 시그니처만 작성

InitializeState()
UpdateState()
IsValidState()
GetResult()

📌 목적
→ 테스트 가능성 확보
→ 구현 난이도 감소

---

5️⃣ 클래스 분리 (Structure Design)

데이터와 행위를 묶되, 책임은 겹치지 않게

기준

• 데이터만 가지는 객체
• 로직만 담당하는 객체
• 생명주기 기준 분리

📌 PS에서는 선택
📌 C++ / UE 프로젝트에서는 거의 필수

---

6️⃣ 구현 (Implementation)

이미 결정된 것을 코드로 옮기는 단계

• 새로운 판단 ❌
• 설계 변경 ❌
• 예상 못 한 조건 나오면 → 위 단계로 되돌아감

---

7️⃣ 테스트 (Validation)

• 최소 입력
• 최대 입력
• 엣지 케이스
• 정상 / 비정상 흐름

📌 이 단계에서 버그가 나오는 건 정상
📌 구조가 잘못됐으면 이미 3~5단계에서 드러난다

---

8️⃣ 리팩토링 · 검증 (Stabilization)

• 중복 제거
• 함수 책임 재점검
• 디버그 코드 제거
• 조건식 단순화

📌 결과
→ 읽히는 코드 + 재사용 가능한 구조

---

🔑 전체 핵심 요약 (한 문장)

문제 재정의는 “방향 결정”,
의사코드·데이터 추출은 “형태 고정”,
알고리즘·자료구조는 “자연스러운 귀결”,
그 이후는 “안전한 구현”이다.

이 흐름이 몸에 배면

• 문제를 보는 순간 구조가 보이고
• 구현은 가장 마지막 일이 된다.