JavaScript를 사용하여 DSA에서 배열 조작 마스터하기: 기초부터 고급까지-JS 튜토리얼-php.cn

Mastering Array Manipulation in DSA using JavaScript: From Basics to Advanced

DSA용 JavaScript의 배열 조작 마스터하기

배열은 컴퓨터 과학의 기본 데이터 구조이며 다양한 알고리즘과 문제 해결 시나리오에서 광범위하게 사용됩니다. 이 포괄적인 가이드는 기본부터 고급 수준까지 주제를 다루면서 JavaScript 배열 조작의 필수 사항을 안내합니다. 순회, 삽입, 삭제, 검색 등을 시간 복잡성과 실제 예와 함께 살펴보겠습니다.

1. 배열 소개

배열은 인접한 메모리 위치에 저장된 요소의 모음입니다. JavaScript에서 배열은 동적이며 다양한 유형의 요소를 보유할 수 있습니다.

기본 배열 작업:

// Creating an array
let arr = [1, 2, 3, 4, 5];

// Accessing elements
console.log(arr[0]); // Output: 1

// Modifying elements
arr[2] = 10;
console.log(arr); // Output: [1, 2, 10, 4, 5]

// Getting array length
console.log(arr.length); // Output: 5

로그인 후 복사

시간 복잡성:

요소 접근: O(1)
요소 수정: O(1)
배열 길이 가져오기: O(1)

2. 배열 순회

순회는 배열의 각 요소를 한 번 방문하는 것을 의미합니다. JavaScript에서 배열을 순회하는 방법에는 여러 가지가 있습니다.

2.1 for 루프 사용하기

let arr = [1, 2, 3, 4, 5];
for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
}

로그인 후 복사

시간 복잡도: O(n), 여기서 n은 배열의 요소 수입니다.

2.2 forEach 사용하기

let arr = [1, 2, 3, 4, 5];
arr.forEach(element => console.log(element));

로그인 후 복사

시간 복잡도: O(n)

2.3 for...of 루프 사용

let arr = [1, 2, 3, 4, 5];
for (let element of arr) {
    console.log(element);
}

로그인 후 복사

시간 복잡도: O(n)

3. 배열에 삽입

배열의 삽입은 시작, 끝, 특정 위치에 삽입할 수 있습니다.

3.1 마지막에 삽입

let arr = [1, 2, 3];
arr.push(4);
console.log(arr); // Output: [1, 2, 3, 4]

로그인 후 복사

시간 복잡도: O(1)(상각)

3.2 시작 부분에 삽입

let arr = [1, 2, 3];
arr.unshift(0);
console.log(arr); // Output: [0, 1, 2, 3]

로그인 후 복사

시간 복잡도: O(n), 모든 기존 요소를 이동해야 하므로

3.3 특정 위치에 삽입

let arr = [1, 2, 4, 5];
arr.splice(2, 0, 3);
console.log(arr); // Output: [1, 2, 3, 4, 5]

로그인 후 복사

시간 복잡도: O(n), 삽입 지점 뒤의 요소를 이동해야 하기 때문에

4. 배열에서 삭제

삽입과 마찬가지로 삭제도 처음, 끝, 특정 위치에서 수행할 수 있습니다.

4.1 최종 삭제

let arr = [1, 2, 3, 4];
arr.pop();
console.log(arr); // Output: [1, 2, 3]

로그인 후 복사

시간 복잡도: O(1)

4.2 처음부터 삭제

let arr = [1, 2, 3, 4];
arr.shift();
console.log(arr); // Output: [2, 3, 4]

로그인 후 복사

시간 복잡도: O(n), 나머지 모든 요소를 이동해야 함

4.3 특정 위치 삭제

let arr = [1, 2, 3, 4, 5];
arr.splice(2, 1);
console.log(arr); // Output: [1, 2, 4, 5]

로그인 후 복사

시간 복잡도: O(n), 삭제 지점 이후의 요소를 이동해야 하기 때문에

5. 배열에서 검색하기

검색은 배열에서 수행되는 일반적인 작업입니다. 몇 가지 검색 기술을 살펴보겠습니다.

5.1 선형 검색

function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(linearSearch(arr, 5)); // Output: 2
console.log(linearSearch(arr, 6)); // Output: -1

로그인 후 복사

시간 복잡도: O(n)

5.2 이진 검색(정렬된 배열의 경우)

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

let arr = [1, 3, 5, 7, 9];
console.log(binarySearch(arr, 5)); // Output: 2
console.log(binarySearch(arr, 6)); // Output: -1

로그인 후 복사

시간 복잡도: O(log n)

6. 고급 배열 조작 기술

이제 배열 조작을 위한 몇 가지 고급 기술을 살펴보겠습니다.

6.1 두 포인터 기법

두 포인터 기법은 배열 문제를 효율적으로 해결하기 위해 자주 사용됩니다. 다음은 배열을 제자리에서 뒤집기 위해 두 개의 포인터를 사용하는 예입니다.

function reverseArray(arr) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++;
        right--;
    }
}

let arr = [1, 2, 3, 4, 5];
reverseArray(arr);
console.log(arr); // Output: [5, 4, 3, 2, 1]

로그인 후 복사

시간 복잡도: O(n)

6.2 슬라이딩 윈도우 기법

슬라이딩 윈도우 기술은 하위 배열 문제를 해결하는 데 유용합니다. 다음은 k 크기의 최대 합계 하위 배열을 찾는 예입니다.

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let windowSum = 0;

    // Calculate sum of first window
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    maxSum = windowSum;

    // Slide the window
    for (let i = k; i < arr.length; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

let arr = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSumSubarray(arr, 4)); // Output: 39

로그인 후 복사

시간 복잡도: O(n)

6.3 Kadane의 알고리즘

Kadane의 알고리즘은 배열에서 최대 하위 배열 합계를 찾는 데 사용됩니다. 동적 프로그래밍의 예입니다.

function kadane(arr) {
    let maxSoFar = arr[0];
    let maxEndingHere = arr[0];

    for (let i = 1; i < arr.length; i++) {
        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    return maxSoFar;
}

let arr = [-2, -3, 4, -1, -2, 1, 5, -3];
console.log(kadane(arr)); // Output: 7

로그인 후 복사

시간 복잡도: O(n)

6.4 네덜란드 국기 알고리즘

이 알고리즘은 0, 1, 2만 포함된 배열을 정렬하는 데 사용됩니다.

function dutchNationalFlag(arr) {
    let low = 0, mid = 0, high = arr.length - 1;

    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
}

let arr = [2, 0, 1, 2, 1, 0];
dutchNationalFlag(arr);
console.log(arr); // Output: [0, 0, 1, 1, 2, 2]

로그인 후 복사

시간 복잡도: O(n)