코딩테스트 풀이 공식
1. 문제 분석
- 문제 읽기 및 요구사항 파악
- 입력과 출력의 형식, 제약 조건을 정확히 확인.
- 해결해야 할 핵심 목표가 무엇인지 정의.
- 예제 분석
- 제공된 예제를 통해 요구사항을 검증.
- 주어진 예제가 부족하면 추가 예제를 손수 만들어 테스트 케이스를 확장.
- 핵심 키워드 도출
- "그래프", "최단 거리", "조합", "정렬" 등 문제의 성격을 결정짓는 단서를 찾기.
2. 풀이 설계
- 문제를 작은 단위로 나누기
- 문제를 여러 단계로 쪼개서 처리해야 할 작업 목록 작성.
예) 데이터 입력 → 전처리 → 탐색 → 결과 출력.
- 적합한 알고리즘 및 자료구조 선택
- 키워드에 맞는 알고리즘 (e.g., DFS, BFS, DP) 및 자료구조 선택.
- 그래프 → DFS, BFS
- 최적화 → DP, 그리디
- 정렬 → 힙, 퀵소트
- 자료구조를 고려 (e.g., 배열, 해시맵, 스택, 큐, 트리).
- 클래스 또는 함수 설계
- 문제를 해결하는 데 필요한 클래스나 함수 정의.
- 데이터 처리: InputHandler 클래스.
- 계산/탐색: Solver 클래스.
- 결과 출력: OutputHandler 클래스.
- 설계를 통해 코드의 유지보수성과 가독성 향상.
- 의사코드 작성
- 알고리즘의 흐름을 간략히 적어서 문제 풀이의 기본 구조 설계.
3. 구현
- 입력 처리
- 입력 형식에 맞는 데이터 전처리. (e.g., 문자열 → 리스트 변환, 그래프 → 인접 리스트 생성)
- 알고리즘 구현
- 클래스/함수 호출
4. 테스트 및 디버깅
- 제공된 예제 테스트
- 문제에서 제공된 예제를 사용해 정상적으로 동작하는지 확인.
- 엣지 케이스 추가 테스트
- 예외 상황이나 극단적인 입력을 넣어 프로그램의 안정성 점검.
- 시간 복잡도 및 메모리 최적화 검토
- 입력의 범위와 제약 조건에 따라 효율성을 재검토.
5. 최종 제출
- 코드 정리 및 주석 추가
- 가독성을 위해 불필요한 코드를 제거하고 주석으로 설명.
- 최종 테스트
- 마지막으로 다시 한 번 전체 흐름을 확인 후 제출.
예제
체계적 풀이 적용 (DFS 활용)
문제: N개의 노드와 M개의 간선이 주어진 그래프에서 연결 요소의 개수를 구하라.
- 문제 분석
- 입력: 노드 수, 간선 정보 (간선의 연결 리스트).
- 출력: 연결 요소의 개수.
- 풀이 설계
- 그래프 탐색 필요 → DFS 사용.
- 방문 여부를 저장할 visited 배열 필요.
- 모든 노드에 대해 DFS를 호출하며 연결 요소 카운트.
- 클래스 설계
- Graph 클래스: 그래프 생성 및 데이터 저장.
- DFS 함수: 연결 요소 탐색.
- 구현
class Graph:
def __init__(self, n):
self.graph = [[] for _ in range(n + 1)]
self.visited = [False] * (n + 1)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def dfs(self, node):
self.visited[node] = True
for neighbor in self.graph[node]:
if not self.visited[neighbor]:
self.dfs(neighbor)
def count_connected_components(n, edges):
graph = Graph(n)
for u, v in edges:
graph.add_edge(u, v)
count = 0
for node in range(1, n + 1):
if not graph.visited[node]:
graph.dfs(node)
count += 1
return count
