유형 이름을 먼저 맞히는 것보다 입력과 원하는 결과를 읽고 필요한 연산을 찾는 것이 중요합니다. 같은 유형도 제한 조건에 따라 풀이가 바뀝니다. 다음 다섯 유형을 작은 예제로 익히고, 새 문제에서 왜 그 방법을 택했는지 설명해 보세요.
1. 해시: 빠른 조회와 빈도
같은 값이 몇 번 나오는지, 특정 항목이 이미 있는지 반복해서 확인하는 문제를 먼저 의심합니다. 키와 값을 어떻게 구성할지 정하고 중복·누락 입력을 시험하세요.
2. 스택·큐: 처리 순서
최근 들어온 것을 먼저 꺼내면 스택, 먼저 들어온 것을 먼저 처리하면 큐가 자연스럽습니다. 작업 취소와 대기열처럼 순서가 답을 바꾸는 예제로 차이를 확인하세요.
3. 정렬: 순서로 단순해지는 조건
값을 정렬한 뒤 인접한 항목을 비교하면 중복이나 구간 문제를 단순하게 만들 수 있습니다. 원래 순서가 필요한 문제인지 확인하고 정렬 비용도 고려해야 합니다.
4. 그래프 탐색: 연결과 방문
노드 사이의 도달 가능 여부를 묻는다면 방문 기록과 탐색 순서를 정합니다. 시작점이 없거나 연결되지 않은 노드가 있는 경우를 함께 시험하세요.
5. 동적 계획법: 중복 계산 줄이기
큰 문제를 작은 상태의 결과로 표현할 수 있는지 살핍니다. 상태의 뜻과 이전 상태에서 현재 상태로 오는 규칙을 문장으로 설명하지 못한다면 코드를 쓰기 전에 예시를 더 줄이세요.
프로그래머스 고득점 Kit에서 유형별 문제를 연습할 수 있습니다. Python을 사용한다면 공식 자료구조 문서에서 기본 동작을 확인하세요. 제한 조건을 읽는 법은 코딩테스트 난이도 비교에서 이어서 살펴보세요.