"최단 거리를 구하시오." 이 문장 보자마자 다익스트라 코드를 복붙하는 습관, 나도 있었다.
코딩테스트에서 "연속된 부분 배열"이라는 문구가 나오는 순간, 머릿속에서 이중 for문이 떠오르면 이미 시간 초과 루트에 올라탄 거다. 대부분의 연속 구간 문제는 슬라이딩 윈도우 하나면 O(n)에 정리된다.
"최솟값의 최댓값을 구하시오." 이 문장을 읽고 바로 이분 탐색이 떠오르면, 이미 절반은 맞힌 거다.
"각 원소의 오른쪽에 있는 첫 번째 더 큰 수를 구하라." 이 문장을 보면 반사적으로 이중 for문을 짠다.
연결 관계를 추적하는 문제가 나오면 대부분 DFS/BFS부터 떠올린다. 간선이 정적이고 한 번만 탐색하면 되는 상황이라면 그게 맞다.
격자 위에서 (0,0)에서 (N,M)까지 최단 거리를 구하라 — 이건 누구나 BFS를 떠올린다. 근데 "문자열 A를 문자열 B로 바꾸는 최소 연산 횟수는?
회의실이 몇 개 필요한지 물어보는 문제. 코테에서 너무 자주 나오는 유형이라 대부분은 "시작 시간 정렬 → 힙으로 종료 시간 관리"로 접근한다.
프로그래머스 Lv2를 풀다가 "이거 투 포인터 아닌가?" 싶어서 left, right 잡고 짜기 시작한다.
"정렬된 배열에서 값을 찾는 거잖아." 이분 탐색을 이렇게만 알고 있으면 코딩테스트에서 이분 탐색 문제를 절대 못 알아본다.
코테에서 가장 무서운 순간이 있다. 문제를 읽자마자 "아, 이거 그리디네" 하고 자신 있게 코드를 짰는데, 제출하면 40-60% 어딘가에서 WA가 뜨는 순간.
코테에서 "다음으로 큰 원소(Next Greater Element)"를 묻는 문제를 만나면 대부분 이중 for문을 먼저 떠올린다. O(n²)이 나오고, 시간 초과가 뜨고, 그제서야 "뭔가 다른 방법이 있나?
DP 문제를 풀다 보면 가끔 "방문한 노드의 조합"이나 "선택한 원소의 집합"을 상태로 들고 다녀야 하는 순간이 온다. 배열로는 표현이 안 되고, set을 넣자니 해싱이 복잡하고.
코테 스터디에서 위상 정렬을 가르치면 구현 자체는 금방 따라온다. BFS에 진입 차수 배열 하나 붙이면 끝이니까.
Union-Find 구현해본 적은 있다. parent 배열 만들고, find 재귀 돌리고, union 호출하고.
프로그래머스에서 "상위 K개 요소"류 문제를 만났을 때, 가장 먼저 떠오르는 건 정렬이다. 리스트에 값 넣고, sort() 한 번 돌리고, 뒤에서 K번째 꺼내면 끝.
"투 포인터 패턴으로 풀었습니다" — 면접에서 이렇게 말했더니 면접관이 "그거 슬라이딩 윈도우 아닌가요?"라고 되물었다는 후기를 본 적 있다.
지난 주 스터디에서 한 문제를 같이 풀었다. "배열을 K개의 구간으로 나눌 때, 구간 합의 최댓값을 최소화하라.
N-Queen 한 번 풀어보고 "아 백트래킹 알겠다" 싶었던 적 있을 거다. 근데 코테에서 조합 생성이나 조건부 탐색 문제를 만나면 손이 멈춘다.