게시됨

나의 LeetCode 41 집착: 첫 번째로 빠진 양수 퍼즐에 대한 심층 탐구

작성자

LeetCode의 "First Missing Positive" 문제(41번)가 최근 제 코딩에 대한 열정을 불태우고 있습니다. 속임수처럼 간단해 보이는 퍼즐이지만, 제 생각을 사로잡아 그 복잡함을 탐구하고 가능한 가장 효율적인 TypeScript 솔루션을 만들도록 이끌었습니다. 이 글은 단순히 코딩 면접을 잘 보기 위한 것만이 아닙니다(물론 그 부수적인 이점도 있습니다). 문제 해결의 순수한 기쁨, 최적화의 스릴, 그리고 효율적인 코드의 우아한 아름다움에 관한 것입니다. 그리고 제가 수학광이기 때문에, 솔루션의 수학적 기반까지도 자세히 파고들 것입니다.

문제: 양의 탈을 쓴 늑대

이 문제는 정렬되지 않은 정수 배열을 제시합니다. 여러분의 과제: 가장 작은 누락된 양의 정수를 찾으세요. 간단해 보입니까? 다시 생각해 보세요. O(n) 시간과 O(1) 공간 복잡도의 제약 조건은 이처럼 간단해 보이는 작업을 어려운 알고리즘 퍼즐로 변환합니다.

초기 어려움: 무차별 대입의 함정

제 초기 시도는 정렬(O(n) 시간 제약 조건 위반)과 해시 집합(O(1) 공간 제한 초과)을 포함했습니다. 분명히, 더 정교한 접근 방식이 필요했습니다.

유레카 순간: 제자리 변환

핵심 통찰력은 입력 배열 자체를 해시 테이블로 사용할 수 있다는 것을 깨달은 것이었습니다. 요소를 재배열하여 숫자 x를 인덱스 x - 1에 배치할 수 있습니다(1 ≤ x ≤ n, 여기서 n은 배열 길이). 이 제자리 변환은 효율적인 솔루션으로 가는 길을 열어줍니다.

코드 진화: TypeScript 서사시

다음은 자세한 설명과 수학적 통찰력을 포함한 제 코드 진화의 연대기입니다.

버전 1: 단순한 접근 방식(중복된 교환 포함)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // [1, n] 범위에 있는 경우 각 숫자를 올바른 위치에 배치합니다.
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // 교환
    }
  }

  // 첫 번째 누락된 양의 정수를 찾습니다.
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // 모든 숫자가 올바른 위치에 있는 경우 누락된 숫자는 n + 1입니다.
  return n + 1
}

이 버전은 기능적이지만 중복된 교환으로 인해 문제가 있습니다. 최악의 경우 시나리오에서 교환 횟수는 O(n²)에 가까워지지만, 평균적인 경우는 O(n)에 가깝습니다.

설명:

  1. 배열 재배열: 각 숫자 nums[i]는 [1, n] 범위 내에 있고 이미 올바른 위치에 있지 않은 경우 "올바른" 인덱스(nums[i] - 1)에 배치됩니다.

  2. 누락된 양의 정수 식별: 재배열 후, nums[i] !== i + 1인 첫 번째 인덱스 i는 i + 1이 누락된 양의 정수임을 나타냅니다.

  3. 필요한 경우 n + 1 반환: 1부터 n까지의 모든 숫자가 올바른 위치에 있는 경우 누락된 숫자는 n + 1입니다.

주요 사항:

  • 제자리 재배열: 추가 공간을 사용하지 않도록 배열 자체를 수정합니다.
  • 효율성: 재배열과 최종 검색 모두 O(n) 시간이 걸리므로 최적의 성능을 보장합니다.

버전 2: 성능 향상(중복된 교환 제거)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // 가능한 경우 숫자를 올바른 위치로 재배열합니다.
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // 임시 변수를 사용하지 않고 교환합니다.
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // 첫 번째 누락된 양의 정수를 식별합니다.
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

설명:

  1. 효율적인 재배열:

    • while 루프는 숫자가 유효한 범위 [1, n] 내에 있고 이미 올바른 위치에 있지 않은 경우에만 요소를 올바른 위치(nums[idx] - 1)로 직접 교환합니다.
    • if 조건은 잘못된 숫자 또는 이미 올바른 숫자를 건너뛰므로 불필요한 교환을 방지합니다.

  2. 직접 인덱스 확인:

    • 재배열 단계에서 nums[idx]의 범위와 값을 확인하여 잘못된 교환과 중복된 연산을 방지합니다.

  3. 메모리 효율적인 교환:

    • 구조 분해([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]])를 사용하면 임시 변수가 필요 없어 메모리 사용량을 최소화합니다.

  4. 최소 루프:

    • 알고리즘은 두 개의 선형 패스만 사용합니다.
      • 하나는 배열을 제자리에서 재배열합니다.
      • 다른 하나는 첫 번째 누락된 양의 정수를 찾습니다.

복잡도 분석:

  • 시간 복잡도:
    • while 루프와 for 루프 모두 O(n)으로 실행되므로 총 시간 복잡도는 O(n)입니다.
  • 공간 복잡도:
    • 알고리즘은 보조 데이터 구조를 사용하지 않고 제자리에서 작동하므로 공간 복잡도는 O(1)입니다.

이 코드가 최적인 이유:

  • 성능: 간소화된 while 루프는 최소한의 중복 연산을 보장하여 속도를 극대화합니다.
  • 메모리 효율성: 제자리 교환과 추가 변수 회피를 통해 최저 메모리 공간을 보장합니다.

버전 3: 메모리 최적화(최소 공간 사용)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

주요 메모리 최적화:

  1. 최소 임시 변수를 사용한 제자리 업데이트:

    • 교환을 위한 temp 변수를 사용하는 대신 이 코드는 nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1로 배열을 직접 수정합니다.
    • 이를 통해 임시 변수가 필요 없어져 상수만큼 메모리 오버헤드가 줄어듭니다.

  2. 루프 내 임시 값 최소화:

    • 코드는 루프 내에서 correctIdx를 직접 계산하여 핵심 로직 외부에 추가 중간 변수를 저장할 필요가 없습니다.
    • 변수 할당이 적을수록 반복당 메모리 사용량이 약간 줄어듭니다.

  3. 재배열을 위한 단일 패스:

    • while 루프에서 중첩된 조건을 사용하는 첫 번째 코드와 달리 이 구현은 더 간소화된 방식으로 교환을 완료하거나 인덱스를 진행하여 런타임 스택 깊이와 메모리 사용량을 줄입니다.
    • 루프 구조(while과 단일 증분 또는 재배열)가 더 직접적이어서 보조 값이 적게 필요합니다.

  4. 중복 확인 없음:

    • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]에 대한 확인은 간결하며 결과에 기여하지 않는 연산으로 인한 불필요한 오버헤드를 방지합니다.
    • 이를 통해 추가 리소스를 할당할 필요가 없습니다.

  5. 중복 확인 없음:

    • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]에 대한 확인은 간결하며 불필요한 연산을 방지합니다. 이로 인해 결과에 영향을 주지 않는 연산에 대한 추가 리소스 할당이 필요 없습니다.

메모리에서 차이를 만드는 이유:

  • 임시 저장소 감소: temp 변수에 의존하지 않고 중간 계산을 최소화함으로써 메모리 공간이 줄어듭니다.
  • 간소화된 실행: 단계가 적고 논리가 간단할수록 연산당 메모리 사용량이 줄어듭니다.
  • 개선된 캐시 활용: 알고리즘의 선형적이고 예측 가능한 액세스 패턴은 CPU 캐시 성능을 향상시켜 간접적으로 메모리 오버헤드를 줄입니다.

이 솔루션은 직접적인 제자리 업데이트, 최소 변수 사용 및 효율적인 메모리 액세스 패턴에 중점을 두어 메모리 효율 측면에서 최상의 성능을 제공합니다. 절약되는 양은 상수(O(1))이지만, 특히 대규모 데이터 세트의 경우 LeetCode와 같은 경쟁 플랫폼에서 충분히 인식할 수 있을 만큼 중요합니다.

버전 4: 최적화된 걸작 (제자리 교환, 임시 변수 없음)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

이 최종 버전은 임시 변수 없이 우아한 제자리 교환을 통해 최적의 성능과 최소 메모리 사용량을 모두 달성합니다. 시간 복잡도는 이제 확실히 O(n)이고, 공간 복잡도는 O(1)이며 모든 요구 사항을 충족합니다. 수학적으로, 우리는 요소를 "올바른" 위치에 배치하기 위해 배열 내에서 일종의 순환 순열을 수행하고 있습니다.

nums[i] === nums[nums[i] - 1] 확인을 추가하여 불필요한 교환을 방지합니다. 이를 통해 성능이 크게 향상되어 시간 복잡도가 원하는 O(n)에 더 가까워집니다.

구현의 주요 차이점:

  1. 중복된 교환 방지:

    • 제공된 코드는 교환을 수행하기 전에 nums[i] === nums[nums[i] - 1]인지 명시적으로 확인합니다. 이렇게 하면 숫자가 이미 올바른 위치에 있거나 중복이 있는 경우 불필요한 교환을 방지합니다.
    • 첫 번째 구현에서는 이 확인이 생략되어 불필요한 경우에도 중복된 교환이 발생할 수 있습니다. 각 추가 교환은 특히 배열이 클 경우 오버헤드를 추가합니다.

  2. 직접 인덱스 비교:

    • 제공된 코드는 while (nums[i] !== i + 1)을 사용하여 숫자가 올바르게 배치되거나 잘못된 조건을 충족할 때까지 반복적으로 올바른 위치로 교환되도록 합니다. 이를 통해 불필요한 루프 반복이 제거됩니다.
    • 첫 번째 코드는 루프 조건 내에서 숫자와 의도된 인덱스를 명시적으로 비교하지 않습니다. 숫자의 이동이 최소한으로 필요한 경우 더 많은 연산을 수행할 수 있습니다.

  3. 최적화된 조건 확인:

    • 단일 if 블록(예: nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1])에 조건을 결합하여 불필요한 확인이나 계산으로 인한 추가 오버헤드를 방지합니다.

LeetCode에서 중요한 이유:

  • 일관된 실행 시간:

    • LeetCode의 실행 시간 측정은 중복된 교환이나 추가 비교와 같은 불필요한 연산에 민감할 수 있습니다.
    • 제공된 코드는 이러한 연산을 최소화하여 평균적으로 더 빠른 실행 시간을 제공합니다.

  • 캐시 효율성:

    • 교환이 적고 루프 논리가 간단할수록 CPU 캐시 활용이 개선됩니다. 최신 프로세서는 예측 가능하고 간소화된 액세스 패턴으로부터 이점을 얻는데, 제공된 코드가 바로 이를 보여줍니다.

결과

표 형식으로 요약한 내용은 다음과 같습니다.

시도실행 시간메모리 사용량참고
4 (최적화)1ms58.8MB성능과 메모리의 최상의 균형.
3 (최상의 메모리)2ms58.5MB약간 느리지만 메모리 사용량이 적습니다.
2 (최상의 성능)1ms58.9MB더 빠른 실행 시간.
1 (초기 시도)3ms59MB가장 느리고 메모리 사용량이 가장 높습니다.

이 표는 절충점과 최종 솔루션의 최적성을 보여줍니다.

요약하면 최상의 성능과 메모리를 위한 시도가 실제로 가장 최적화되어 다음을 달성합니다.

  • 1ms 실행 시간: 성능 면에서 가장 빠른 결과와 일치합니다.
  • 58.9MB 메모리 사용량: "최상의 메모리" 복제본보다 약간 높지만 다른 시도보다 낮습니다.

분석:

  1. 실행 시간:

    • 1ms 실행 시간은 최적화된 접근 방식이 중복 확인과 불필요한 교환을 제거함을 보여줍니다.
    • O(n)의 일관된 시간 복잡도는 대규모 데이터 세트에 대한 확장성을 보장합니다.

  2. 메모리:

    • 58.9MB는 빠른 실행에도 불구하고 메모리 공간이 적다는 것을 보여주는 경쟁력 있는 수치입니다. "최상의 메모리"(58.5MB)보다 약간 증가한 것은 구조 분해 또는 엔진별 최적화의 차이 때문일 수 있습니다.

  3. 절충점:

    • "최상의 메모리" 솔루션은 메모리 사용량을 줄이기 위해 실행 시간을 약간 희생합니다.
    • "최상의 성능" 솔루션은 속도에 더 중점을 두지만 약간 더 많은 메모리를 사용합니다.

결론:

최적화된 솔루션은 좋은 균형을 이룹니다.

  • 1ms 실행 시간은 최고 성능 코드와 동일하게 빠릅니다.
  • 58.9MB 메모리 사용량은 최상의 메모리 결과와 거의 비슷하며 오버헤드가 무시할 수 있습니다.

특히 성능과 메모리가 모두 중요한 시나리오에 적합한 선택입니다.

수학적 기반: 순환 순열과 비둘기집 원리

핵심 아이디어는 순환 순열의 개념을 중심으로 합니다. 각 숫자 x를 인덱스 x - 1에 배치하는 순환을 만드는 것을 목표로 합니다. while 루프는 이러한 순환을 효과적으로 순회하여 각 요소가 지정된 위치를 찾도록 합니다.

비둘기집 원리가 여기서 미묘하게 작용합니다. n개의 가능한 위치(인덱스 0에서 n-1)가 있고 [1, n+1] 범위 내에서 누락된 양의 정수를 찾고 있으므로, 1부터 n까지의 모든 숫자가 있는 경우 누락된 숫자는 n + 1이어야 합니다.

집착은 계속됩니다...

LeetCode 41에 대한 제 매력은 여전히 남아 있습니다. 저는 끊임없이 더 나은 최적화와 더 깊은 통찰을 추구하고 있습니다. 이 여정에 함께 참여하세요! 여러분의 생각, 여러분 자신의 솔루션을 공유하고 수학과 알고리즘의 우아한 교차점을 함께 탐구해 봅시다.

트위터에서 논의하기

공유