software

LeetCode에서 머리가 하얘지나요? 여기 탈출 계획이 있습니다

발행: (2025년 12월 13일 오후 03:21 GMT+9)
8 min read
원문: Dev.to

Source: Dev.to

소개

문제는 이해하지만 시작할 방법을 전혀 모를 때가 있습니다. 이런 마비는 고칠 수 있습니다. 이 가이드는 전혀 아이디어가 없을 때 접근법을 만들어내는 구체적인 단계별 프레임워크를 제공하여 “아무것도 없어”를 “시작점은 있잖아”로 바꿔줍니다.

핵심 문제

빈 머리 마비는 최적해를 바로 찾으려다 아무것도 시작하지 않으려는 데서 비롯됩니다. “완벽하게 풀어라”는 불가능한 과제에 뇌가 멈추지만, “우리가 아는 것을 기술해라”는 실현 가능한 과제에는 작동합니다.

왜 중요한가

면접에서는 잘못된 접근보다 침묵을 더 크게 처벌합니다. 생각 과정을 말로 풀어내면(비록 완전하지 않더라도) 문제 해결 능력을 보여줄 수 있지만, 멍하니 바라보는 표정은 미지의 상황을 다루지 못한다는 신호가 됩니다.

프레임워크 (7‑단계 체계적 접근)

  1. 문제 다시 말하기
  2. 구체적인 예시 풀어보기
  3. 우선 브루트포스
  4. 병목 찾기
  5. 패턴 매칭
  6. 제약 조건 분석
  7. 의사코드 골격

초보자 흔한 실수

코드를 작성하기 전에 완전한 해결책을 먼저 만들어야 한다고 믿는 것. 부분적인 진행이 완벽한 침묵보다 언제나 낫습니다.

배울 내용

  • 생각을 촉발하는 질문 템플릿(예: “n = 1이면 어떻게 될까?”)
  • 브루트포스를 사고의 골격으로 활용하기
  • 전문가들이 익숙하지 않은 문제를 풀 때 사용하는 내부 대화 모델을 단계별 힌트 시스템으로 제공

막혔을 때의 내부 대화

“이건 O(n log n)… 어떻게 만들지?”
“두 포인터를 써야 할까… 아니면 해시맵… 혹은 DP?”
“우아한 해법은 뭘까?”

첫 번째 벽돌을 놓기 전에 대성당을 설계하려는 겁니다. 완벽한 경로가 보이지 않으면 뇌가 멈춥니다.

단계별 프로세스

1. 해결하려고 하지 말고 이해부터 시작

아래와 같이 적거나 큰 소리로 말하세요:

  • “나는 …을 찾아야/계산해야 한다”
  • “주어지는 …”
  • “반환한다 …”

예시: 중복 문자 없이 가장 긴 부분 문자열

재진술:
“문자열이 주어진다. 문자 중복 없이 가장 긴 연속 구간을 찾아 그 길이를 반환한다.”

2. 작은 예시를 손으로 풀어보기

입력: abcabcbb

수동으로 가장 긴 부분 문자열을 추적하면:

  • a → 길이 1
  • ab → 길이 2
  • abc → 길이 3 (중복 없음)
  • abca → 중단, ‘a’가 중복

각 시작 위치마다 이렇게 하면 최대 길이가 3임을 알 수 있습니다.

통찰: 문자를 추적하고 중복이 나타나면 다시 시작하는 과정을 직접 수행했으며, 이것이 알고리즘이 됩니다.

3. 브루트포스 솔루션 작성

def lengthOfLongestSubstring(s: str) -> int:
    max_len = 0
    n = len(s)

    # 모든 가능한 부분 문자열을 시도
    for i in range(n):
        for j in range(i, n):
            substring = s[i:j+1]

            # 모든 문자가 고유한지 확인
            if len(substring) == len(set(substring)):
                max_len = max(max_len, len(substring))

    return max_len
  • 정확성: O
  • 복잡도: O(n³) (n²개의 부분 문자열 × O(n) 고유성 검사)

비록 최적은 아니지만, 빈 머리를 깨고 실행 가능한 코드를 얻을 수 있습니다.

4. 병목 찾기

가장 비용이 많이 드는 부분은 각 부분 문자열에 대해 set(substring)으로 고유성을 검사하는 것입니다.

5. 패턴 매칭

브루트포스 구조가 전형적인 패턴을 드러냅니다:

  • 부분 배열을 순회
  • 상태 유지(고유성)
  • 결과 업데이트

이는 슬라이딩 윈도우 / 두 포인터 패턴과 일치합니다.

6. 제약 조건 분석

일반적인 제약: 1 ≤ s.length ≤ 5 × 10⁴.

  • O(n³)은 절대 통과 못 함.
  • O(n²)도 한계에 걸릴 수 있음.
  • O(n) 또는 O(n log n)이 이상적.

7. 의사코드 초안 (슬라이딩 윈도우)

left = 0
max_len = 0
freq = empty hash map

for right in range(0, n):
    add s[right] to freq

    while any character count > 1:
        decrement freq[s[left]]
        left += 1

    max_len = max(max_len, right - left + 1)

return max_len

여기서부터 구현은 직관적입니다.

완전히 멍할 때 스스로에게 던지는 질문

  • n = 1이면? → 기본 사례.
  • 모든 원소가 동일하면? → 가장자리 사례 ("aaaa" → 답 1).
  • 입력이 정렬돼 있으면? → 정렬이 도움이 될까?
  • 종이에 어떻게 풀어볼까? → 코드가 아니라 과정에 집중.
  • 어떤 정보를 추적해야 할까? → 상태/변수 식별.
  • 언제 결정을 내려야 할까? → 조건문 결정 시점.
  • 작은 하위 문제로 나눌 수 있을까? → 예: “각 시작점마다 가장 긴 부분 문자열 찾기”.
  • 더 간단한 버전을 먼저 풀 수 있을까? → 예: “고유한 부분 문자열이 존재하는가?”
  • 시간/공간 제약을 무시하면? → 올바른 해를 찾고 나중에 최적화.
  • 입력이 작다고 가정하면 (n ≤ 10) 어떻게 할까? → 브루트포스가 허용됨.

인터뷰에서 유효한 시작 방식

  1. 알려진 비효율성을 가진 브루트 포스
    “중첩 루프로 O(n²) 해결은 가능하지만 더 좋은 방법이 있을 것 같습니다. 먼저 이 코드를 짜볼게요.”

  2. 의사코드 개요
    “구현은 아직 완벽하지 않지만 제 생각은 이렇습니다:” (의사코드 작성)

  3. 예시 walkthrough
    “예시를 하나 풀어보고 어떤 패턴이 보이는지 살펴볼게요.”

이러한 접근은 진행 상황, 구조화된 사고, 그리고 반복하려는 의지를 보여줍니다—면접관이 정확히 원하는 모습입니다.

Back to Blog

관련 글

더 보기 »