KSum 가족 문제 전개

Mar 09 2023

1장: 투 포인터 접근법에 대한 심층 조사

목차 드디어 주말입니다. 당신에게 긴 한 주였습니다.

Canva의 작가가 찍은 사진.

드디어 주말입니다. 당신에게 긴 한 주였습니다. 당신은 집을 청소하고 저녁 식사를 위해 식료품을 샀습니다. 그러나 이 만찬은 여느 만찬과 달랐다. 당신의 고등학교 친구들이 당신과 합류하기 위해 올 것이기 때문입니다. 한 시간 후, 친구들이 도착했고 어린 시절의 연인이 거기 있었습니다! 그녀는 당신이 문에서 처음 만난 사람이었습니다. 당신은 그녀를보고 달 이상했다. 식사를 시작하기 전에 짧은 대화를 나눴습니다.

Unsplash의 Dan Gold 사진

저녁 식사를 마친 후 어린 시절 연인이 "음식 추측" 게임을 제안했습니다. 하지만 이번에는 음식 이름을 추측하는 대신 이 신비한 음식의 재료를 하나 이상 말해야 합니다. 당신은 그녀에게 깊은 인상을 주고 싶었기 때문에 다음 질문을 생각하고 있었습니다.

얼음처럼 차가운 물 한 통을 머리에 쏟아 붓기 전에 어떻게 이 재료들의 이름을 빨리 추측할 수 있습니까?

이 게시물이 해당 재료를 빠르게 찾는 효율적인 접근 방식을 개발하는 데 어떻게 도움이 되는지 살펴보겠습니다.

KSum 가족 문제 로 이 시리즈를 시작하겠습니다 . 거의 모든 다른 알고리즘 문제 중에서 볼 수 있는 여러 솔루션 패턴이 포함되어 있기 때문에 면접관들 사이에서 가장 많이 묻는 질문 중 하나입니다. 또한 면접관이 한 유형의 KSum 문제에서 다른 버전의 KSum 문제로 질문을 쉽게 확장할 수 있습니다.

이러한 유형의 문제에서 우리는 다음과 같습니다.

정수 목록이 주어졌을 때 주어진 대상 에 합산되는 K개의 숫자 그룹을 모두 찾고자 합니다 . 이러한 방식으로 이러한 그룹은 모두 고유해야 합니다.

수학적으로 이것은 다음과 같이 공식화될 수 있습니다.

좋아, 시작하자!

2. 1합

1.1 문제 설명

이것은 검색 문제 로 간주되는 KSum의 첫 번째 버전 이지만 여기서는 KSum의 가장 간단한 버전으로 재정의합니다 . (1차원)

이 문제에서:

우리는 고유한 숫자 목록을 받았고 주어진 목표와 일치하는 숫자의 인덱스를 찾고자 합니다 .

A + 0 = 대상

1.2 예

입력: 숫자 = [6,2,5,4,11], 대상 = 4

출력: 색인은 3입니다.

그래서 여기에 우리 알고리즘에 대한 입력과 그것이 반환해야 하는 것의 예가 있습니다. 알고리즘이 목록 nums = [6,2,5,4,11] 및 대상 = 4 를 수신하는 경우 이 대상이 목록 내에서 발견되면 알고리즘은 인덱스(여기서는 3 ) 를 반환해야 합니다 .

1.3 무차별 대입 솔루션

이 문제에 대한 간단한 해결책은 목록 내의 모든 숫자를 반복하고 해당 대상을 찾는 것입니다. 찾으면 해당 인덱스를 반환합니다. 자, 코드는 다음과 같습니다.

이 솔루션의 시간 복잡도는 다음과 같습니다.

최악의 시나리오에서 대상은 목록 끝에 있거나 존재하지 않으며 모든 목록 번호를 반복합니다.

이 솔루션의 공간 복잡성은 다음과 같습니다.

추가 공간이 사용되지 않습니다!

1.4 최적화된 솔루션

숫자 목록이 정렬되어 있다고 가정해 보겠습니다 . 그런 다음 이진 검색 알고리즘을 사용하여 시간 복잡도를 O(log n) 으로 줄일 수 있습니다 . 그러나 이 게시물의 문제 개념의 상호 의존성을 위해 다른 솔루션에 대해 논의할 것입니다.

이 솔루션은 시간 복잡성 측면에서 순진한 솔루션보다 훨씬 빠릅니다. 그래도 이진 검색 알고리즘이 더 좋습니다. 이제 이 솔루션을 추측하셨나요?! 예, 정확합니다. 브라보! 투포인터 방식 입니다 .

2점 접근 방식은 목록 ( 정렬 여부 ) 또는 컬렉션에서 검색 작업이 있을 때 가장 널리 사용되는 기술 중 하나로 간주됩니다2 포인터 접근 방식의 기본 아이디어는 하나의 루프 변수(포인터) 대신 두 개의 변수를 사용하여 목록이나 컬렉션을 순회하는 것입니다. 이 문제에 대해 다음과 같이 적용합니다.

두 개의 포인터를 초기화합니다. 값이 left = 0 인 왼쪽 포인터 와 right = n-1 인 값을 가진 오른쪽 포인터 입니다 . 여기서 n = 배열 크기입니다 .
그런 다음 nums[left] == target 인지 확인한 다음 왼쪽 포인터를 1씩 늘립니다.
또한 nums[right] == target 인지 확인한 다음 오른쪽 포인터를 1씩 감소시킵니다.

1Sum 문제의 시각적 삽화.[GIF by Author]

실제 코드는 다음과 같습니다.

다시 말하지만, 시간 복잡도는 여전히 다음과 같습니다.

최악의 시나리오이지만 두 개의 포인터를 사용하여 동시에 검사를 수행하기 때문에 순진한 접근 방식에 비해 훨씬 빠릅니다.

공간 복잡도는

추가 공간 없이.

1.5 패턴

이 문제에는 다음과 같은 패턴이 있습니다.

Two Pointers : 목록 ( 정렬 여부 ) 또는 컬렉션 에서 검색 작업이 있는 경우 해당 컬렉션을 빠르게 탐색하기 위해 항상 두 포인터 접근 방식을 사용하는 것에 대해 생각하십시오.

2Sum 문제의 시각적 그림.[GIF by Author]

2.1 문제 설명

이것은 KSum 가족의 두 번째 구성원입니다. 이 문제에서:

우리는 고유한 정수 목록을 받았고 주어진 목표 에 합산되는 두 숫자 의 인덱스를 찾고자 합니다 . 대상을 형성하는 고유한 쌍이 하나만 있다고 가정합니다 .

A + B = 대상

2.2 예

입력: 숫자 = [6,2,4,3,11], 대상 = 15

출력: [2,4] — > nums[2] + nums[4] = 15

이것은 알고리즘의 입력 및 출력의 예입니다. 알고리즘이 목록 nums = [6,2,5,4,11] 및 대상 = 15 를 수신 하는 경우 이 대상이 목록 내에서 발견되면 알고리즘은 합계가 다음과 같은 두 숫자의 인덱스를 반환해야 합니다. 여기서는 2 와 4 입니다 .

2.3 무차별 대입 솔루션

이 문제를 해결하기 위한 직관적인 접근 방식은 두 개의 루프 변수 (i, j) 를 만드는 것입니다 . 그런 다음 목표 값에 합산되는 두 숫자의 조합을 찾습니다. 우리가 이것을 코딩하는 방법을 보자:

시간 복잡도는 다음과 같습니다.

두 개의 중첩된 루프를 사용했기 때문에 최악의 시나리오에서 이 시간 복잡도가 발생합니다.

공간 복잡성은 다음과 같습니다.

최적화 기회: 이 알고리즘은 공간 복잡도 O(1) 측면에서는 효율적이지만 시간 복잡도 측면에서는 실용적이지 않습니다. 그렇다면 O(n²) ⇾ O(n) 에서 시간 복잡도를 줄일 수 있을까요 ?

2.4 최적화된 솔루션

프로그래머가 사용하기 좋아하는 가장 유용한 데이터 구조 중 하나는 Hashmap 입니다 . 내부의 거의 모든 요소의 검색 작업에 대해 O(1) 시간 복잡도를 갖습니다 . 공간 복잡성에 의존하여 무차별 대입 솔루션의 비효율성을 해결할 수 있습니다.

따라서 Hashmap 안에 모든 숫자를 저장할 수 있습니다 . 그런 다음 목록을 반복할 수 있으며 언제든지 target — nums[i] 와 같은 값을 가진 키를 사용하여 Hashmap을 쿼리합니다 . 여기서 i 는 루프 변수이고 nums 는 숫자 목록입니다. 이것을 어떻게 코딩하는지 봅시다:

그러면 시간 복잡도는 다음과 같습니다.

그러나 공간 복잡성은 다음과 같습니다.

네, 알아요, 알아요! 시간 복잡도 최적화와 공간 복잡도 간의 절충입니다.

2.5 패턴

Hashmap: 일반적으로 중간 값을 저장하거나 컬렉션의 검색 시간을 최적화하려는 경우 항상 Hashmap 사용을 고려하십시오.

3Sum 문제의 시각적 그림.[GIF by Author]

3.1 문제 설명

이것은 KSum 문제 계열 의 또 다른 버전입니다 . 이 문제에서:

우리는 고유하지 않은 정수 목록을 받았고, 합이 0이 되는 세 개의 숫자를 찾고자 합니다 . 그런 식으로 세 쌍둥이는 모두 고유 해야 합니다 .

A + B + C = 0

3.2 예

입력: 숫자 = [-1,0,1,2,-1,-4], 대상 = 0

출력: [ [-1,-1,2], [-1,0,1] ] , [ [-1,-1,2], [-1,0,1], [1,0,- 아님 1],]

이것은 알고리즘의 입력 및 출력의 예입니다. 알고리즘이 목록 nums = [-1,0,1,2,-1,-4] 및 대상 = 0 을 수신 하는 경우 이 대상이 목록 내에서 발견되면 알고리즘은 세 숫자의 인덱스를 반환해야 합니다. 합계가 0 인 경우 [ [-1,-1,2], [-1,0,1] ]입니다.

3.3 무차별 대입 솔루션

다시 말하지만, 문제를 해결하기 위한 직관적인 접근 방식은 세 개의 루프 변수 (i, j, k) 를 만드는 것입니다 . 그런 다음 합이 0이 되는 세 숫자의 조합을 찾습니다. 아래 코드에서 우리가 초기에 수행한 정렬이 어떻게 파이썬 세트 "결과"가 중복 조합을 인식하도록 허용 했는지 주목 하십시오 .

이 솔루션의 시간 복잡도는 다음과 같습니다.

세 개의 중첩 루프를 사용하기 때문입니다!

공간 복잡성은 다음과 같습니다.

조합을 저장하기 위해 파이썬 세트 "결과"를 사용하기 때문입니다.

최적화 기회: O(n³) ⇾ O(n) 에서 시간 복잡도를 줄일 수 있습니까 ?

3.4 최적화된 솔루션

다시 말하지만 대답은 '예'입니다! 그리고 그것은 "두 포인터" 접근 방식을 사용하는 것입니다. 아이디어는 다음과 같습니다.

정수 배열을 오름차순으로 정렬합니다.
"result" 라는 세 가지 조합을 담을 세트를 만듭니다 .
변수( i) 를 사용하여 배열을 반복하는 동안
값이 i+1 인 왼쪽 포인터와 n-1 인 값이 있는 오른쪽 포인터 , 여기서 n = 배열 크기인 두 포인터를 초기화합니다.
중첩된 루프를 만들고 두 포인터를 사용하여 배열을 트래버스합니다. nums[left] + nums[right] + nums[i]= 0을 찾고 있기 때문에 target = -nums[i] 로 설정합니다 .
nums[left] + nums[right] = target 이면 이를 결과 집합에 추가합니다.
nums[left] + nums[right] < target 이면 이 합계의 값을 늘리려면 왼쪽 포인터를 늘려야 함을 의미합니다.
마지막으로 nums[left] + nums[right] > target 인 경우 오른쪽 포인터를 줄여 합계 값을 줄이고 0 쪽으로 밀어야 함을 의미합니다.
결국 " 결과"를 반환합니다.

시간 복잡도는 다음과 같습니다.

O( n³) 에 비해 약간 더 나은 시간 복잡도입니다 . Sorting O(n.logn) 및 Searching O(n²) (두 개의 중첩 루프)라는 두 가지 주요 작업을 사용했습니다. 그러나 O(n.logn) + O(n²) = O(n²) 이므로 시간 복잡도는 여전히 O (n²) 입니다.

공간 복잡성은 다음과 같습니다.

그러나 여전히 무차별 대입 솔루션과 유사합니다. 그것에서 탈출!

3.5 패턴

정렬: 정렬은 알고리즘 문제, 특히 배열(목록) 문제를 해결할 때 가장 중요한 전처리 단계 중 하나입니다. 문제를 훨씬 더 쉽게 위반할 수 있으므로 어레이 문제를 해결할 때 잠시 동안 어레이를 정렬하는 것을 고려하십시오.
Python "Set" 데이터 구조 사용: Python "set" 데이터 구조를 사용하여 반복되는 값을 극복합니다. 중복 값을 자동으로 제거하는 속성이 있습니다. 여기에서는 중복을 제거하면서 조합을 저장하는 데 사용했습니다.
2점슛: 목록을 더 빠르게 탐색하기 위해 2점슛을 사용했습니다. 목록 값을 정렬한 후 이 접근 방식을 사용하는 것이 얼마나 쉬워지는지 확인하십시오.

4.1 문제 설명

이것은 KSum의 제네릭 버전을 논의하기 전에 KSum 제품군 의 마지막 문제가 될 것입니다 . 아시다시피 이러한 문제를 해결하는 패턴이 분명해지며 여러분도 이를 감지하기 시작했을 것입니다. 그래서,

고유하지 않은 정수 목록과 대상이 주어지면 이 목록에서 해당 대상에 합산되는 4개의 숫자 집합을 찾고자 합니다 . 여기서 해당 집합은 모두 고유 합니다 .
A + B + C + D = 대상

4.2 예

입력: 숫자 = [3,7,2,4,5,4,6,1,8], 대상 = 12
출력: [[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]]

이것은 알고리즘의 입력 및 출력의 예입니다. 알고리즘이 목록 nums = [3,7,2,4,5,4,6,1,8] 및 대상 = 12 를 수신 하는 경우 이 대상이 목록 내에서 발견되면 알고리즘은 다음 인덱스를 반환해야 합니다. 합계가 0 인 세 개의 숫자는 [[1, 2, 3, 6], [1, 2, 4, 5], [1, 3, 4, 4]]입니다 .

4.3 무차별 대입 솔루션

3Sum과 마찬가지로 이 문제에 대한 무차별 대입 솔루션은 4개의 루프 변수 (i, j, k, l) 를 만드는 것입니다 . 그런 다음 해당 목표 값에 합산되는 4개의 숫자 조합을 찾습니다. 이 솔루션을 코딩할 필요가 없습니다! 지금은 식은 죽 먹기가 되었습니다.

4.4 최적화된 솔루션

4Sum의 최적화 버전은 3Sum 최적화 솔루션과 매우 유사합니다. 아래 코드에서 두 포인터 루프 ( 세 번째 루프 )를 유지하면서 루프 (두 번째 루프) 를 하나 더 추가했습니다 . 아래 코드를 보자:

시간 복잡도는 다음과 같습니다.

세 개의 루프를 사용했기 때문입니다.

공간 복잡성은 다음과 같습니다.

결과를 저장해야 하기 때문입니다.

6. 케이썸

드디어 야수를 직접 만나고 있습니다! KSum . 2Sum, 3Sum 및 4Sum 문제는 모든 KSum 문제(예: 5Sum, 6Sum)를 해결하기 위한 패턴을 제공했습니다.

5.1 문제 설명

이전 솔루션에서 KSum 솔루션을 추론할 수 있으려면 먼저 매우 중요한 사항을 이해해야 합니다. 모든 KSum 문제는 다음과 같은 간단한 아이디어로 해결할 수 있습니다.

KSum을 2Sum 문제로 줄인 다음 해결하십시오.

예, KSum을 2Sum으로 줄인 다음 해결해야 합니다! 그러나 먼저 이 솔루션 패턴을 이해하려면 다음과 같은 간단한 방정식을 다시 검토해야 합니다.

2Sum 문제는 다음과 같이 공식화될 수 있습니다.

3Sum은 다음 과 같이 공식화됩니다 .

그리고 4Sum은 다음과 같이 공식화됩니다 .

그런 다음 4Sum을 풀기 위해 이 방정식을 다음과 같이 재정렬할 수 있습니다.

잠깐, 잠깐, 잠깐, Waleed, 내가 길을 잃고 있어. 더 설명해 주시겠습니까? 전적으로! 4Sum을 예로 들어 보겠습니다. 계산할 수 있으려면 하위 목표 (즉, " t₁") 를 계산할 수 있으려면 상위 목표 " t₂" 와 "숫자"가 필요합니다 . 여기서 "숫자"는 방정식의 4ₜₕ 항을 나타냅니다 .

그런 다음 4Sum을 풀기 위해 항상 주어진 최상위 목표(즉, " t₃") 를 사용하여 역방향으로 시작하여 이러한 목표를 계산해야 합니다.

마지막으로 앞서 2Sum 에서 본 2점 접근 방식 을 사용하여 방정식 (a, b) 의 마지막 두 요소를 찾을 수 있습니다 . 좋은 소식은 정확한 개념을 적용하여 모든 KSum 문제를 해결할 수 있다는 것입니다.

5.2 솔루션

위의 알고리즘을 요약하면 다음과 같습니다.

최상위 목표 (예: degree = 3, t = " t₃" ) 부터 시작 :

재귀적으로 상위 목표 (t₂, t₁)를 계산합니다.
degree = 2 일 때 2Sum 함수를 호출하여 마지막 누락된 요소(a, b)를 찾습니다 .

Unsplash의 TERRA 사진

자, 자, 여기 위의 알고리즘이 어떻게 작동하는지에 대한 시각적 설명이 있습니다.

KSum 알고리즘(k=3, target = 6)의 시각적 그림.[GIF by Author]

자, 여기 코드가 있습니다. 더 나은 이해를 위해 코드의 모든 줄을 위의 시각적 그림의 해당 단계와 연결하십시오.

정렬 작업을 무시하면 시간 복잡도는 다음과 같습니다.

여기서 k = 정도 또는 누락된 구성 요소의 수, n = 배열 크기입니다.

공간 복잡성은 다음과 같습니다.

" path" 변수 가 사용하는 메모리를 무시합니다 .

5.3 패턴과 요령

깊이 우선 검색(DFS): 깊이 우선 검색 알고리즘을 사용하여 차수(k) 와 대상 값을 업데이트하여 숫자 목록을 순회합니다.
두 개의 포인터: 마지막 누락된 요소(a, b)를 찾기 위해 2Sum의 최적화된 버전 (두 개의 포인터 포함) 을 사용했습니다 .

이 게시물에서는 KSum 문제 제품군에 대해 논의했습니다 . 이러한 유형의 문제는 다음과 같이 요약할 수 있는 몇 가지 중요한 알고리즘 패턴을 소개했습니다.

문제 패턴:

주어진 집계 값(sum, max, min, … 등)과 일치하기 위해 배열에서 일련의 숫자(하위 배열)를 찾아야 하는 문제 → 두 개의 포인터를 사용해 보십시오. [1] [2]
조합 집합 또는 솔루션 하위 집합을 찾아야 하는 문제 → 깊이 우선 검색 알고리즘(DFS)을 사용해 보십시오. [3] [4]