코딩 테스트는 입력 크기부터 읽는다

핵심 요약

• 코딩 테스트의 첫 단계는 문제를 읽는 일이 아니라 제약 조건으로 가능한 시간 복잡도를 정하는 일임
• 입력 크기는 풀이의 상한을 알려주는 역설계 문서이며, N = 100,000에서 모든 쌍을 비교하는 식의 접근을 초기에 제거할 수 있음
• 시간 복잡도 표는 합격을 보장하는 기준이 아니라 후보를 줄이는 휴리스틱이며, 언어·상수항·테스트 케이스 수·입출력 비용을 함께 고려해야 함
• 문제의 키워드와 입력 형태는 정답을 알려주는 표식이 아니라 자료구조와 알고리즘 후보를 세우는 단서임
• 실전에서는 제약 확인 → 단순 풀이 정의 → 병목 계산 → 알고리즘 선택 → 반례 검증 순서가 가장 재현 가능한 접근임

코딩 테스트는 제약 안에서 답을 만드는 시험임

• 코딩 테스트는 알고리즘 이름을 맞히는 퀴즈보다 제한된 시간과 메모리 안에서 정확한 프로그램을 만드는 작업에 가까움

  • 같은 정답을 계산하더라도 O(N²) 풀이와 O(N log N) 풀이는 입력 크기가 커지는 순간 전혀 다른 결과를 만듦
  • 풀이를 떠올린 뒤 복잡도를 계산하는 습관보다 허용 복잡도를 먼저 정한 뒤 풀이를 찾는 습관이 안정적임

• 알고리즘 지식은 필요하지만 문제를 코드로 옮기는 구현 능력도 같은 비중으로 필요함

  • 배열과 맵을 자연스럽게 다루고, 경계 조건을 코드로 표현하고, 작성한 반복문의 비용을 즉시 계산하는 능력이 기반이 됨
  • 특정 유형을 알아도 인덱스 범위와 상태 전이를 정확히 구현하지 못하면 정답으로 이어지지 않음

• 코딩 테스트 준비의 실용적인 목표는 모든 알고리즘을 외우는 것이 아니라 낯선 문제를 분해하는 절차를 만드는 것임

  • 문제 상황을 입력·상태·연산·출력으로 나누면 서술이 길어도 프로그램이 해야 할 일은 단순해짐
  • 이 관점은 참고 글인 코딩 테스트 이모저모의 문제 접근 전략과 학습법에서 많은 도움을 받았음

입력 크기가 가능한 풀이를 먼저 걸러냄

• 입력 제한은 출제자가 허용한 계산량을 간접적으로 공개한 정보임

  • N이 작으면 완전 탐색이나 상태를 세밀하게 나누는 풀이를 검토할 수 있음
  • N이 커지면 한 번 순회하거나 정렬한 뒤 선형으로 처리하는 풀이부터 검토해야 함

• 다음 표는 단일 테스트 케이스와 일반적인 실행 제한을 가정한 1차 판단표임

• 표의 가능은 통과를 보장하지 않으며 불가능은 미세 최적화로 뒤집기 어렵다는 의미임

  • O(N log N)이라도 비교 함수가 무겁거나 같은 작업을 여러 번 반복하면 제한을 넘을 수 있음
  • O(N²)이라도 N = 1,000이면 약 백만 번의 비교이므로 충분히 현실적인 후보가 될 수 있음
  • O(N³)에서 N = 1,000이면 약 10억 번의 조합이므로 표의 주의 필요보다 실제로는 매우 엄격한 최적화나 구조적 가지치기가 필요한 경우가 많음

• 실제 계산량은 최대 입력의 곱으로 확인해야 함

  • 테스트 케이스가 T개라면 전체 비용은 대체로 O(T × f(N))으로 봐야 함
  • 정점 V와 간선 E가 따로 주어지면 그래프 탐색의 기준은 O(V + E)로 봐야 함
  • 문자열 길이의 합이 제한되어 있다면 개별 문자열의 최댓값보다 전체 길이 합이 더 중요한 기준이 됨

제약 조건에서 알고리즘 후보를 역산함

• 가장 단순한 풀이를 먼저 정의하면 무엇을 줄여야 하는지가 드러남

  • 모든 쌍을 비교하는 풀이가 O(N²)이라면 같은 정보를 맵에 저장해 한 번에 찾을 수 있는지 검토함
  • 매 구간의 합을 다시 계산하는 풀이가 O(N²)이라면 누적 합으로 중복 계산을 제거할 수 있는지 검토함
  • 매번 최솟값을 선형 탐색하는 풀이가 병목이라면 힙이나 정렬된 구조로 교체할 수 있는지 검토함

• 입력 형태와 요구 연산은 다음과 같은 후보를 시사함

  • 정렬된 배열에서 특정 값이나 경계를 찾는 요구는 이진 탐색을 시사함
  • 연속 구간의 합·개수·최댓값을 다루는 요구는 누적 합, 슬라이딩 윈도우, 투 포인터를 시사함
  • 연결 관계와 최단 이동 횟수를 다루는 요구는 그래프 탐색과 너비 우선 탐색을 시사함
  • 매 순간 가장 작거나 큰 원소를 꺼내는 요구는 힙을 시사함
  • 작은 N에서 선택 여부를 모두 비교하는 요구는 비트마스크와 부분집합 탐색을 시사함
  • 이전 선택이 이후 결과에 반복해서 영향을 주는 요구는 동적 계획법을 시사함

• 키워드는 확정 답안이 아니라 검증해야 할 가설임

  • 최단 거리라는 표현이 있어도 간선 가중치가 없으면 너비 우선 탐색, 음수 가중치가 있으면 전혀 다른 접근이 필요함
  • 정렬이라는 표현이 있어도 실제로 정렬이 필요한지, 정렬된 성질만 이용하면 되는지 구분해야 함
  • 후보 알고리즘을 정한 뒤에는 입력 조건이 그 알고리즘의 전제와 일치하는지 다시 확인해야 함

풀이 순서는 아이디어보다 재현 가능한 절차가 중요함

• 첫 번째 단계는 입력과 출력의 계약을 한 문장으로 다시 쓰는 것임

  • 무엇이 하나의 상태인지, 어떤 연산을 반복하는지, 최종적으로 무엇을 출력하는지 분리함
  • 예시 입출력은 설명을 대신하지 않으므로 규칙과 충돌할 때 문제 본문의 정의를 우선함

• 두 번째 단계는 가장 단순한 정답 풀이의 복잡도를 계산하는 것임

  • 완전 탐색이 제한 안에 들어오면 더 복잡한 알고리즘을 찾을 이유가 없음
  • 제한을 넘는다면 반복문 중 어떤 축을 없애야 하는지 수치로 확인함

• 세 번째 단계는 제거할 반복을 자료구조나 전처리로 바꾸는 것임

  • 조회 반복은 해시 맵, 범위 계산 반복은 누적 합, 정렬된 경계 탐색은 이진 탐색으로 치환할 수 있음
  • 이 과정에서 시간 비용을 줄이는 대신 추가 메모리를 쓰는 선택이 자주 발생함

• 네 번째 단계는 코드를 쓰기 전에 불변식과 종료 조건을 정하는 것임

  • 투 포인터라면 각 포인터가 언제 이동하고 이미 제외된 구간을 왜 다시 보지 않아도 되는지 설명할 수 있어야 함
  • 이진 탐색이라면 답이 존재하는 구간과 mid 판정 후 남겨야 할 구간을 명확히 해야 함

• 다섯 번째 단계는 작은 반례로 가설을 깨보는 것임

  • 빈 구간, 원소 하나, 모든 값이 같음, 오름차순·내림차순, 최댓값·최솟값을 우선 확인함
  • 정수 합과 곱은 자료형 범위를 넘는지 확인하고, 그래프는 단절과 중복 간선을 확인함

구현에서는 정답성과 복잡도를 함께 보존함

• 자료구조를 선택한 이유가 코드에 그대로 드러나야 함

  • 존재 여부만 필요하면 집합, 키별 집계가 필요하면 맵, 양 끝 처리가 필요하면 덱을 선택함
  • 편의상 배열을 선택한 뒤 중간 삭제를 반복하면 의도한 O(N) 풀이가 실제로 O(N²)이 될 수 있음

• 루프마다 총 실행 횟수를 설명할 수 있어야 함

  • 중첩 반복문이 항상 O(N²)인 것은 아니며, 두 포인터가 각각 끝까지 한 번만 이동하면 전체는 O(N)임
  • 반대로 한 줄짜리 라이브러리 호출도 내부에서 정렬하거나 배열을 복사하면 숨은 비용이 발생함

• 입출력과 자료형도 알고리즘의 일부로 취급해야 함

  • 입력이 매우 크면 토큰 파싱과 출력 결합 방식이 실행 시간에 영향을 줄 수 있음
  • 합의 최댓값은 최대 원소 × 원소 수로 먼저 계산해 안전한 정수 범위를 선택해야 함

• 제출 전에는 다음 항목을 짧게 확인하면 됨

  • 최악 입력에서 시간 복잡도가 제한 안에 있는지 확인함
  • 추가 메모리가 메모리 제한 안에 있는지 확인함
  • 인덱스의 시작과 끝, 포함·미포함 경계를 확인함
  • 입력을 변경해도 되는지와 같은 값이 여러 번 등장할 수 있는지 확인함
  • 디버그 출력과 불필요한 변환이 남아 있지 않은지 확인함

학습은 풀이 수보다 복기 품질이 결정함

• 문제를 푼 뒤에는 정답 코드보다 결정 과정을 기록하는 편이 효과적임

  • 어떤 제약이 완전 탐색을 배제했는지 기록함
  • 어떤 문장이 알고리즘 후보를 떠올리게 했는지 기록함
  • 처음 풀이가 실패한 이유와 다시 틀리지 않기 위한 반례를 기록함

• 모르는 유형은 오래 버티기보다 해설을 학습 재료로 사용하는 기준이 필요함

  • 충분히 시도한 뒤에도 핵심 전환을 찾지 못하면 해설에서 알고리즘 이름만 확인하지 말고 전환 근거를 찾아야 함
  • 해설을 읽은 직후 코드를 복사하기보다 닫아두고 자신의 언어로 다시 구현해야 함
  • 며칠 뒤 같은 문제나 유사 문제를 다시 풀어야 지식이 문제 인식 능력으로 바뀜

• 구현 문제와 유형 문제는 다른 방식으로 훈련해야 함

  • 구현 문제는 상태를 작게 나누고 예외를 통제하는 코딩량이 중요함
  • 유형 문제는 자료구조와 알고리즘의 전제, 복잡도, 적용 신호를 함께 익히는 것이 중요함

결론은 제약에서 시작하는 한 문장 풀이임

• 좋은 실전 습관은 코드를 쓰기 전에 이 풀이는 O(...)이고, N이 ...이므로 가능하다라고 말하는 것임
• 이 문장을 설명할 수 없으면 풀이가 아직 아이디어 단계에 머물러 있다는 신호임
• 매 문제에서 제약 확인 → 단순 풀이 → 병목 제거 → 불변식 정의 → 반례 검증을 반복하면 처음 보는 문제에도 적용 가능한 자신만의 절차가 만들어짐