알고리즘 해결 전략?

by

솔직히 머리가 좋으면

흐름도를 그리지 않아도 머릿속에 데이터를 가지고 그림을 그리는 아이들이 있다.

그게 다야?

문제 해결은 전략입니다. 전략을 살펴보자.

'추천 관련글,

알고리즘 퍼즐은 불행하게도 지원 과정에서 후보자를 걸러내는 일반적인 방법입니다. 그러나 구직에 대해 스트레스를 받지 않을 때는 코더를 위한 크로스워드 퍼즐과 같이 실제로 매우 재미있습니다.

이를 해결하면 Yet Another Crud App을 시작할 때 직면하지 않는 고유한 문제가 발생하고 아직 익숙하지 않은 개념에 노출됩니다. 알고리즘 챌린지를 연습하면 보다 폭넓은 문제 해결 능력을 향상시킬 뿐만 아니라 보다 일반적으로 유용한 문제 해결 프로세스를 강화할 수 있습니다.

다른 유형의 퍼즐과 마찬가지로 문제에 대한 초기 발판을 제공하고 문제를 더 작고 접근하기 쉬운 덩어리로 분해하는 방법을 제공하는 전략이 있습니다. 실제 퍼즐을 사용하면 조각을 유사한 색상이나 기능의 일관된 그룹으로 분류하고, 일치하는 항목을 찾고, 바깥쪽으로 성장할 수 있습니다. 지뢰 찾기를 사용하면 임의의 클릭으로 시작한 다음 노출된 가장자리 주위를 이동하여 명백한 지뢰를 표시하고 명백한 명확한 영역을 노출할 수 있습니다.

유사한 종류의 알고리즘에 접근하기 위한 전략이 있지만 인터뷰 준비로 LeetCode를 연마할 때뿐만 아니라 일반적인 습관으로 받아들이는 더 광범위한 문제 해결 전략으로 시작하는 것이 좋습니다.

전략적으로 먼저 생각하십시오

뛰어들기보다는 단계적으로 문제에 접근하십시오.

생각하다:

  1. 문제 분석
  2. 문제를 다시 말하십시오
  3. 입력 및 출력의 예를 작성하십시오.
  4. 문제를 구성 요소로 분해
  5. 의사 코드로 솔루션 개요
  6. 의사 코드를 사용하여 예제 데이터를 단계별로 실행합니다.

실행하다

  1. 코딩
  2. 예제와 비교하여 솔루션 테스트
  3. 리팩토링

(이 접근 방식에 익숙하다면 알고리즘 패턴으로 건너뛰십시오.)

문제 분석

문제를 처음 보았을 때 번쩍이는 통찰력이 있었을 것입니다. 이것은 일반적으로 이전 경험과 연결되는 마음입니다. 그 통찰력을 유지하십시오! 그러나 여전히 문제를 살펴보는 데 시간을 할애해야 합니다. 특히 통찰력이 실제 질문과 다른 방식에 대해서는 더욱 그렇습니다.

잘 작성된 퍼즐에는 한두 문장에 포함된 문제에 답하는 데 필요한 구성 요소가 있습니다. 그러나 문제를 읽었다고 해서 문제를 이해한 것은 아닙니다. 그리고 문제를 이해하지 못한다면 목적 없이 비틀거리거나 문제라고 생각했던 것을 해결하게 될 것입니다.

도전의 형태를 결정하는 키워드를 찾으십시오.

입력을 식별합니다.
원하는 출력을 식별합니다.
중요한 키워드와 구문을 식별합니다.

예를 들어, 리트코드 #26

주어진 (정렬된) (배열) 숫자, (중복 항목 제거) (제자리에서) 각 요소가 한 번만 나타나도록 하고 (새 길이를 반환).

다른 어레이에 추가 공간을 할당하지 마십시오. 입력 배열을 수정하여 이를 수행해야 합니다. 인플레이스 (O(1) 추가 메모리).

입력:

  • 배열. 그래서 우리는 아마도 어떤 종류의 반복을 할 것이라는 것을 압니다.
  • 숫자의 배열. 그것은 구체적으로 언급되기보다는 암시적이며 동일한 조건문 세트를 사용할 수 있는 만큼 실제로 중요하지 않습니다.

반품:

  • 변경된 배열의 길이
  • 부작용: 수정된 배열

중요한 단어 및 문구:

  • 정렬됨: 반복되는 요소가 서로 옆에 배치됩니다.
  • 제거…중복
  • in-place: 배열 자체를 파괴적으로 수정해야 합니다. 이 제약 조건은 우리가 사용할 수 있는 배열 방법을 나타냅니다.
  • O(1) 추가 메모리: O(1) 공간 복잡성으로 제한되어 변수를 정의할 수 있지만 배열의 복사본을 만들 수는 없습니다.

문제를 다시 말하십시오

이제 우리 자신에게 의미가 있도록 이것을 우리 자신의 말로 바꾸십시오. 면접 상황에 있다면 면접관에게 다시 말하여 자신의 마음 속에 설정하고 올바르게 듣고 이해했는지 확인하십시오.

다시 언급:

참조로 전달된 정렬된 숫자 배열이 주어지면 각 값이 한 번만 나타나도록 중복을 제거하여 제자리에서 원래 배열을 파괴적으로 수정합니다. 수정된 배열의 길이를 반환합니다.

예제 입력 및 예상 출력 작성

우리가 하는 일은 입력을 출력에 매핑하는 것뿐입니다. 문제는 A에서 B로 이동하는 방법을 파악하는 것이지만 먼저 A와 B가 무엇인지 설정해야 합니다. 이다. 테스트 사례가 주어지더라도 직접 작성하십시오. 무언가를 보는 것은 직접 해보는 것만큼 많은 이해를 만들어내지 못합니다.

이것은 또한 문제에 대한 이해를 탐색하고 순진한 솔루션을 방해할 수 있는 단점을 찾을 수 있는 좋은 시간입니다. 여기에는 빈 입력, 동일한 값의 중복으로 채워진 배열, 대규모 데이터 세트 등과 같은 엣지 케이스가 포함됩니다. 문제의 제약 조건을 벗어나는 것에 대해 걱정할 필요가 없습니다.

최소한 3가지 예를 작성하십시오.

() -> (), return 0
(1) -> (1), return 1
(1, 1, 2, 3, 4, 4, 4, 5) -> (1, 2, 3, 4, 5), return 5
(1, 1, 1, 1, 1) -> (1), return 1

입력이 주어지면 결과에 매핑할 충분한 정보가 있습니까? 그렇지 않은 경우 한 걸음 뒤로 물러나서 계속하기 전에 문제를 계속 조사하십시오. 인터뷰 중이라면 언제든지 설명을 요청하십시오.

결과에 도달하기 위해 가치에 관계없이 적용할 수 있는 간단하고 일관된 프로세스를 찾으십시오. 복잡한 일련의 단계와 예외가 발생하면 너무 멀리 갔고 더 간단한 솔루션을 통과했을 수 있습니다.

문제를 작은 부분으로 나누기

가능한 가장 간단한 예부터 시작하여 문제를 필수 퍼즐 그리고 그것을 기반으로 합니다. 이 경우, 그것은 3개의 요소, 즉 2개가 복제된 배열입니다. (1, 1, 2). 문제를 이렇게 작은 사례로 축소하면 더 접근하기 쉬워지고 취해야 할 첫 번째 단계가 명확해집니다. 거기에서 당신의 임무는 그 간단한 사례를 해결하는 절차를 개발하는 것입니다. 그리고 문제 세트의 다른 모든 경우에 적용됩니다.

따라서 몇 가지 작업을 수행해야 한다는 것을 알고 있습니다.

  • 배열을 통해 반복
  • 배열에서 우리가 있는 위치를 추적합니다.
  • 인접한 값이 같은지 확인
  • 중복 값이 ​​처음 발생한 후 파괴적으로 제거
  • 최종 배열 길이를 가져와서 반환

이것은 비교적 간단한 예제 문제이지만, 잡았다 그것에 숨어: 많은 반복 방법은 배열에서 요소를 제거하는 것과 잘 작동하지 않습니다. ~하는 동안 인덱스 값이 변경되기 때문에 배열을 반복하고 있습니다. 포인터가 증가했기 때문에 중복 항목을 건너뛸 수 있습니다.

이 문제는 반복을 명시적으로 제어할 수 있는 접근 방식을 사용하고 싶다는 것을 나타냅니다.

보다 복잡한 문제에서는 이러한 구성 요소 중 일부 또는 전부를 도우미 기능으로 간주하여 명확하고 간결한 솔루션을 작성하고 각 하위 부분의 유효성을 개별적으로 테스트할 수 있습니다.

솔루션 의사 코드

우리가 문제를 명확하게 파악하고 핵심 작업을 식별하고 우리 자신의 가정과 문제의 결함을 발견했으면 우리의 접근 방식이 무엇인지에 대한 사람이 읽을 수 있는 설명을 작성합니다. 이 작업을 완료하면 작업 코드로 깔끔하게 변환할 수 있기를 바랍니다.

의사 코드를 작성하는 방법은 귀하에게 달려 있습니다. 표기법의 철자가 완벽하고 문법적으로 정확할 필요는 없습니다. 의미를 전달하기 위한 코드와 단어의 몸짓 조합일 수 있습니다. 의사 코드는 구현 세부 사항에 대해 잘 모르는 경우 다시 참조할 수 있는 의미 있는 로드맵을 제공하므로 나중에 유용할 수 있도록 충분히 기록해야 합니다.

인터뷰 중이라면 면접관에게 의도를 전달할 수 있는 좋은 기회입니다. 그리고 시간이 부족하다면 적어도 문제 해결 방식을 보여주는 무언가가 보드에 있을 것입니다.

추천:

  • 함수 서명으로 시작: removeDuplicates :: (배열) -> 숫자
  • 화이트보드를 사용하는 경우 실제 코드를 작성할 공간을 충분히 남겨두세요.
  • IDE를 사용하는 경우 나중에 다시 참조할 수 있도록 주석을 작성하고 코드와 별도로 보관하십시오.
  • 일련의 단계로 작성하고 글머리 기호 사용

중복을 찾고 있으므로 비교를 수행해야 합니다. 배열에서 현재 위치보다 앞을 보거나 뒤를 볼 수 있습니다.

// removeDuplicates :: (Array) -> number
// if array is empty or has 1 element, return array length and exit
// iterate through array
//     compare each element to the next element
//
//     repeat until false:
//        if the next element is the same as the current element
//        remove the next element
//
//     move on to the next element in the array
//     stop once the second to last element has been reached
// return array length

배열의 크기가 0 또는 1인 경우 종료하는 것으로 시작합니다. 부분적으로는 이러한 경우가 문제의 조건을 충족하기 때문입니다. 가능한 중복이 없으며 부분적으로는 첫 번째 값을 비교하려고 시도하면 코드가 손상되기 때문입니다. 존재하지 않는 초로.

또한 반복 종료 조건을 설정하고 예측을 사용할 것이므로 중지해야 합니다. ~ 전에 우리는 마지막 요소에 도달합니다.

때까지 포인터 위치를 이동하지 않기 때문에 ~ 후에 우리는 모든 중복을 처리했으므로 이동 인덱스 문제가 없어야 합니다.

샘플 데이터 단계별 실행

잠시 시간을 내어 의사 코드를 통해 샘플 데이터 중 일부를 정신적으로 실행하십시오.

() -> (), return 0
(1) -> (1), return 1
(1, 1, 2, 3, 4, 4, 4, 5) -> (1, 2, 3, 4, 5), return 5
(1, 1, 1, 1, 1) -> (1), return 1

빠진 것이 있습니까?

마지막 예에 문제가 있을 수 있습니다. (1, 1, 1, 1, 1). 중복 항목을 모두 제거한 다음, 중복 항목이 있는지 확인하지 않고 배열의 다음 요소로 이동하면 어떻게 됩니까?

종료 조건이 배열 길이의 변경 사항을 포착하는지 확인해야 합니다.

코드 잇

고무가 길을 만나는 시간. 이것은 당신이 당신을 괴롭히기 위해 돌아온 줄도 몰랐던 모든 가정을 가지고 있는 곳입니다. 계획을 잘 세울수록 더 적어질 것입니다.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    return arr.length
}

개인적으로 나는 내 반환 값을 먼저 넣는 것을 좋아합니다. 그렇게 하면 내 목표가 무엇인지 명확해지고 비어 있거나 단일 요소 배열의 첫 번째 경우도 캡처했습니다.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; arr++) {}

    return arr.length
}

예, 우리는 표준 for-loop로 갈 것입니다. 더 적절하거나 깔끔한 구문이 있는 경우 사용하지 않는 것이 좋지만 이 특정 문제의 경우 반복을 제어할 수 있는 기능이 필요합니다.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; i++) {
        while (arr(i + 1) && arr(i) === arr(i + 1)) arr.splice(i + 1, 1)
    }

    return arr.length
}

다음을 제외하고는 기본적으로 작동합니다.

removeDuplicates((0,0,1,1,1,2,2,3,3,4))    //> 6, should be 5

배열 값이 0. 자바스크립트 감사합니다! 따라서 정말 빠르게 재작업하고 앞을 보는 대신 뒤를 살펴보겠습니다. 이렇게 하면 실제로 코드도 약간 정리됩니다.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; i++) {
        while (arr(i) === arr(i - 1)) arr.splice(i, 1)
    }

    return arr.length
}

그리고 그것은 통과합니다. 이것은 메모리 효율적인 솔루션이며 배열 참조 외에 1개의 변수만 정의했습니다. 그리고 그것은 우리가 개선할 수 있는 평균 속도입니다.

그러나 대부분은 프로세스의 간단한 예였습니다.

  1. 분석하다
  2. 다시 말하다
  3. 예시 작성
  4. 작은 문제로 분해
  5. 의사 코드의 개요
  6. 예제를 사용하여 의사 코드 단계별 실행
  7. 암호
  8. 시험
  9. 리팩토링

알고리즘 패턴

알려진 상당히 표준화된 접근 방식이 있는 특정 데이터 구조 및 알고리즘을 제외하고 알고리즘 문제는 유사한 솔루션 접근 방식을 제안하는 범주로 분류되는 경향이 있습니다. 이러한 접근 방식을 배우면 문제에 대한 발판을 마련할 수 있습니다.

다중 포인터

컬렉션(일반적으로 배열)을 반복하는 방법을 처음 배울 때 인덱스가 가장 낮은 값에서 가장 높은 값으로 가는 단일 포인터를 사용하여 수행합니다. 이것은 일부 작업에서 작동하며 고려 및 코딩이 간단합니다. 그러나 여러 요소를 비교하는 것과 관련된 문제, 특히 컬렉션에서 해당 위치가 중요한 요소의 경우 단일 포인터로 해당 값을 찾으려면 각 값에 대해 적어도 한 번은 배열을 반복해야 합니다. O(n2) 작업.

대신 여러 포인트를 사용하면 계산을 O(n) 연산으로 줄일 수 있습니다.

두 가지 일반적인 전략이 있습니다: 투 포인터 및 슬라이딩 윈도우

투 포인터

양쪽 끝에서 시작하여 작업하는 것이 어떻습니까? 또는 값 또는 값 쌍에서 시작하여 바깥쪽으로 확장합니다. 이것은 컬렉션에서 가장 큰 시퀀스를 찾기 위한 훌륭한 접근 방식입니다.

두 지점을 처리하고 있기 때문에 서로 교차하지 않도록 규칙을 정의해야 합니다.

// Time complexity O(n)
// Space complexity O(1)
function sumZero(arr) {
  let left = 0;
  let right = array.length - 1;
  while (left < right) {
    let sum = arr(left) + arr(right);
    if (sum === 0) return (arr(left), arr(right));
    else if (sum > 0) right--;
    else left++;
  }
}

슬라이딩 윈도우

외부 경계에 두 점을 배치하는 대신 두 포인터를 병렬로 순차적으로 이동하는 배열을 통해 행진할 수 있습니다. 창의 너비는 문제 세트에 따라 늘어나거나 줄어들 수 있지만 컬렉션 전체에서 계속 진행되어 원하는 결과에 가장 적합한 시퀀스의 스냅샷을 캡처합니다.

function maxSubarraySum(array, n) {
  if (array.length < n) n = array.length;
  let sum = 0;

  for (let i = 0; i < n; i++) {
    sum = sum + array(i);
  }

  let maxSum = sum;

  // shift window across array
  for (let i = n; i < array.length; i++) {
    sum = sum + array(i) - array(i - n);
    if (sum > maxSum) maxSum = sum;
  }
  return maxSum;
}

분할 정복

Divide and Conquer에는 종종 재귀적 접근 방식이 포함됩니다. 동일한 규칙을 적용하여 컬렉션을 가장 작은 구성 요소로 나누고 답을 식별할 때까지 컬렉션을 나눕니다.

Binary Search와 Merge Sort는 솔루션으로 이어지는 재귀 세분화의 훌륭한 예입니다.

O(1) 조회: 객체/사전/해시

해시 키: 코딩 언어에 따라 개체, 사전 또는 해시라고 하는 값 저장소는 빈도를 계산할 때 정보를 저장하고 중복 또는 답변 보완을 확인하는 데 매우 유용한 도구입니다. 그곳에

값을 저장할 수도 있고 대신 찾고 있는 값을 저장할 수도 있습니다. 예를 들어 배열에서 제로섬 쌍을 찾을 때 값 자체가 아닌 보수를 저장할 수 있습니다.

자원:

알고리즘 문제 해결의 기초(영상)
프로그래머를 위한 알고리즘 문제 해결
인터뷰 질문의 상위 10개 알고리즘
알고리즘 및 데이터 구조 기술 향상