- Input: 어떤 모양의 데이터가 들어오는가?
- Storage: 그 데이터를 어떤 형태로 저장할 것인가? (예: 2차원 리스트)
- Process: 저장된 데이터를 어떻게 요리할 것인가? (1. 다 칠하기 → 2. 전체 순회하며 찾기)
- 문제 잘 읽기 (조건, 범위)
- 제약 조건과 Input 범위 보기 (m, n)
- 숫자의 크기가 작을수록 ‘가장 단순하고 직관적인 방법’이 정답일 확률이 높다
- 멍청한 방법 생각하기(브루트 포스(Brute Force), 시뮬레이션): 손으로 칸을 하나씩 색칠하는 게 가장 쉽다면, 컴퓨터에게도 그 일을 시키는 것이 가장 버그가 적고 빠를 수 있다
- 추상화보다는 시각화
- 격자: 교집합보단 칸 체크 개념 - 단순한 ‘숫자 더하기’나 ‘상태 체크’ 문제로 바뀜
- 문제 유형끼리 모아 외우기
- 그리드(격자) 문제: 주로 시뮬레이션, BFS/DFS 탐색.
- 범위/구간 문제: 정렬, 스위핑(Sweeping).
- Edge case (엣지 케이스) 찾기
1. 입력 경계값 지표 (Boundary Value Analysis)
내 코드는 가장 작은 입력과 가장 큰 입력에서도 동일하게 작동하는가?
2. 순서와 중복 지표 (Order & Redundancy)
입력 데이터의 순서를 무작위로 섞어도(Shuffle) 결과가 변하지 않는가?
3. 상태의 독립성 지표 (Independence of State)
프로그램의 각 단계가 이전 단계의 결과에 우연히 의존하고 있지 않은가?
ex) “4839_이진탐색”처럼, middle == var 때 time이 올라가지 않아도 우연히 답은 나오지만 조건 바뀌면 다 바꿔야 함
리팩토링이 쉬운가?
ex) “4836_색칠하기”에서 칠하는 로직을 수정했을 때, 개수를 세는 로직까지 수정해야 하는가?
- 초기화 확인: 테스트 케이스 가 바뀔 때마다 배열이 완전히 깨끗하게(0으로) 비워지는가?
- 역할 분담: “칠하는 기능”과 “세는 기능”이 서로의 내부 사정을 몰라도 잘 돌아가는가?
4. 제약 조건의 ‘부정(Negative)’ 테스트
문제의 제약 조건 덕분에 내가 생략한 로직은 무엇인가? 그 생략은 안전한가?
ex) “4836_색칠하기”
- 문제 조건: “같은 색인 영역은 겹치지 않는다.”
- 나의 의문: “만약 같은 색이 겹친다면 내 코드는 그걸 보라색으로 오해하지 않을까?”
결론: Case를 최대한 쪼개서 모든 경우의 수를 생각하자.
- ex) #4831 전기버스: 충전소 거리 간 차이 계속 더함
- n 더하는 순간 (… n-1 + n) → 모든 경우는 충전 없이 갈 수 있는 거리 보다 작을 수도, 같을 수도, 클 수도 있음 (<, =, >)
- 엣지 케이스 유의 → 충전소 거리 n 자체가 충전 없이 갈 수 있는 거리보다 길면 아예 실패. → 동적계획법: 큰 문제를 잘게잘게 쪼개고, 같은 계산 더 안 하게 미리 저장