JavaScript를 사용한 DSA의 배열 탐색: 기본부터 고급 기술까지

배열 순회는 모든 개발자가 숙지해야 하는 데이터 구조 및 알고리즘(DSA)의 기본 개념입니다. 이 포괄적인 가이드에서는 기본 접근 방식부터 시작하여 고급 방법까지 진행하면서 JavaScript에서 배열을 탐색하는 다양한 기술을 살펴보겠습니다. 쉬운 수준부터 고급 수준까지 20가지 예시를 다루며, 학습을 강화하기 위한 LeetCode 스타일의 질문도 포함합니다.

목차

1. 배열 순회 소개
2. 기본 배열 순회
   • 예 1: for 루프 사용
   • 예 2: while 루프 사용
   • 예 3: do-while 루프 사용
   • 예 4: 역순회
3. 최신 JavaScript 배열 방법
   • 예 5: forEach 메소드
   • 예 6: 지도 방법
   • 예 7: 필터 방법
   • 예 8: 축소 방법
4. 중간 순회 기술
   • 예 9: 투 포인터 기술
   • 예시 10: 슬라이딩 윈도우
   • 예 11: Kadane의 알고리즘
   • 예 12: 네덜란드 국기 알고리즘
5. 고급 순회 기술
   • 예 13: 재귀 순회
   • 예 14: 정렬된 배열의 이진 검색
   • 예 15: 두 개의 정렬된 배열 병합
   • 예 16: 빠른 선택 알고리즘
6. 전문 순회
   • 예 17: 2D 배열 탐색
   • 예 18: 나선형 행렬 탐색
   • 예 19: 대각선 순회
   • 예 20: 지그재그 탐색
7. 성능 고려 사항
8. LeetCode 실습 문제
9. 결론

1. 배열 순회 소개

배열 순회는 일부 작업을 수행하기 위해 배열의 각 요소를 방문하는 프로세스입니다. 이는 프로그래밍에서 중요한 기술로, 많은 알고리즘과 데이터 조작의 기초를 형성합니다. JavaScript에서 배열은 데이터를 탐색하고 조작하는 다양한 방법을 제공하는 다목적 데이터 구조입니다.

2. 기본 배열 순회

배열 탐색의 기본 방법부터 시작해 보겠습니다.

예제 1: for 루프 사용

클래식 for 루프는 배열을 순회하는 가장 일반적인 방법 중 하나입니다.

function sumArray(arr) {
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    return sum;
}

const numbers = [1, 2, 3, 4, 5];
console.log(sumArray(numbers)); // Output: 15

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

예제 2: while 루프 사용

특히 종료 조건이 더 복잡한 경우 배열 순회에 while 루프를 사용할 수도 있습니다.

function findFirstNegative(arr) {
    let i = 0;
    while (i < arr.length && arr[i] >= 0) {
        i++;
    }
    return i < arr.length ? arr[i] : "No negative number found";
}

const numbers = [2, 4, 6, -1, 8, 10];
console.log(findFirstNegative(numbers)); // Output: -1

시간 복잡도: 최악의 경우 O(n)이지만, 음수를 조기에 발견하면 더 작아질 수 있습니다.

예제 3: do-while 루프 사용

do-while 루프는 배열 순회에서는 덜 일반적이지만 특정 시나리오에서는 유용할 수 있습니다.

function printReverseUntilZero(arr) {
    let i = arr.length - 1;
    do {
        console.log(arr[i]);
        i--;
    } while (i >= 0 && arr[i] !== 0);
}

const numbers = [1, 3, 0, 5, 7];
printReverseUntilZero(numbers); // Output: 7, 5

시간 복잡도: 최악의 경우 O(n)이지만 초기에 0을 만나면 더 작아질 수 있습니다.

예제 4: 역순회

배열을 역순으로 탐색하는 것은 많은 알고리즘에서 일반적인 작업입니다.

function reverseTraversal(arr) {
    const result = [];
    for (let i = arr.length - 1; i >= 0; i--) {
        result.push(arr[i]);
    }
    return result;
}

const numbers = [1, 2, 3, 4, 5];
console.log(reverseTraversal(numbers)); // Output: [5, 4, 3, 2, 1]

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

3. 최신 JavaScript 배열 방법

ES6 및 이후 버전의 JavaScript에는 순회 및 조작을 단순화하는 강력한 배열 방법이 도입되었습니다.

예시 5: forEach 메서드

forEach 메소드는 배열 요소를 반복하는 깔끔한 방법을 제공합니다.

function logEvenNumbers(arr) {
    arr.forEach(num => {
        if (num % 2 === 0) {
            console.log(num);
        }
    });
}

const numbers = [1, 2, 3, 4, 5, 6];
logEvenNumbers(numbers); // Output: 2, 4, 6

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

예시 6: 지도 방법

map 메소드는 모든 요소에 대해 제공된 함수를 호출한 결과로 새 배열을 생성합니다.

function doubleNumbers(arr) {
    return arr.map(num => num * 2);
}

const numbers = [1, 2, 3, 4, 5];
console.log(doubleNumbers(numbers)); // Output: [2, 4, 6, 8, 10]

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

실시예 7: 필터 방법

필터 메소드는 특정 조건을 통과하는 모든 요소로 새 배열을 생성합니다.

function filterPrimes(arr) {
    function isPrime(num) {
        if (num <= 1) return false;
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num % i === 0) return false;
        }
        return true;
    }

    return arr.filter(isPrime);
}

const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(filterPrimes(numbers)); // Output: [2, 3, 5, 7]

시간 복잡도: O(n * sqrt(m)), 여기서 n은 배열의 길이이고 m은 배열에서 가장 큰 숫자입니다.

실시예 8: 감소 방법

리듀스 메소드는 배열의 각 요소에 리듀서 함수를 적용하여 단일 출력값을 생성합니다.

function findMax(arr) {
    return arr.reduce((max, current) => Math.max(max, current), arr[0]);
}

const numbers = [3, 7, 2, 9, 1, 5];
console.log(findMax(numbers)); // Output: 9

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

4. 중간 순회 기법

이제 배열 순회를 위한 몇 가지 중간 기술을 살펴보겠습니다.

예시 9: 두 포인터 기술

두 포인터 기법은 배열 관련 문제를 효율적으로 해결하기 위해 자주 사용됩니다.

function isPalindrome(arr) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        if (arr[left] !== arr[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

console.log(isPalindrome([1, 2, 3, 2, 1])); // Output: true
console.log(isPalindrome([1, 2, 3, 4, 5])); // Output: false

Time Complexity: O(n/2) which simplifies to O(n), where n is the length of the array.

Example 10: Sliding window

The sliding window technique is useful for solving problems involving subarrays or subsequences.

function maxSubarraySum(arr, k) {
    if (k > arr.length) return null;

    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;
}

const numbers = [1, 4, 2, 10, 23, 3, 1, 0, 20];
console.log(maxSubarraySum(numbers, 4)); // Output: 39

Time Complexity: O(n), where n is the length of the array.

Example 11: Kadane's Algorithm

Kadane's algorithm is used to find the maximum subarray sum in a one-dimensional array.

function maxSubarraySum(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;
}

const numbers = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubarraySum(numbers)); // Output: 6

Time Complexity: O(n), where n is the length of the array.

Example 12: Dutch National Flag Algorithm

This algorithm is used to sort an array containing three distinct elements.

function dutchFlagSort(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--;
        }
    }

    return arr;
}

const numbers = [2, 0, 1, 2, 1, 0];
console.log(dutchFlagSort(numbers)); // Output: [0, 0, 1, 1, 2, 2]

Time Complexity: O(n), where n is the length of the array.

5. Advanced Traversal Techniques

Let's explore some more advanced techniques for array traversal.

Example 13: Recursive traversal

Recursive traversal can be powerful for certain types of problems, especially those involving nested structures.

function sumNestedArray(arr) {
    let sum = 0;
    for (let element of arr) {
        if (Array.isArray(element)) {
            sum += sumNestedArray(element);
        } else {
            sum += element;
        }
    }
    return sum;
}

const nestedNumbers = [1, [2, 3], [[4, 5], 6]];
console.log(sumNestedArray(nestedNumbers)); // Output: 21

Time Complexity: O(n), where n is the total number of elements including nested ones.

Example 14: Binary search on sorted array

Binary search is an efficient algorithm for searching a sorted array.

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1; // Target not found
}

const sortedNumbers = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedNumbers, 7)); // Output: 3
console.log(binarySearch(sortedNumbers, 6)); // Output: -1

Time Complexity: O(log n), where n is the length of the array.

Example 15: Merge two sorted arrays

This technique is often used in merge sort and other algorithms.

function mergeSortedArrays(arr1, arr2) {
    const mergedArray = [];
    let i = 0, j = 0;

    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            mergedArray.push(arr1[i]);
            i++;
        } else {
            mergedArray.push(arr2[j]);
            j++;
        }
    }

    while (i < arr1.length) {
        mergedArray.push(arr1[i]);
        i++;
    }

    while (j < arr2.length) {
        mergedArray.push(arr2[j]);
        j++;
    }

    return mergedArray;
}

const arr1 = [1, 3, 5, 7];
const arr2 = [2, 4, 6, 8];
console.log(mergeSortedArrays(arr1, arr2)); // Output: [1, 2, 3, 4, 5, 6, 7, 8]

Time Complexity: O(n + m), where n and m are the lengths of the input arrays.

Example 16: Quick Select Algorithm

Quick Select is used to find the kth smallest element in an unsorted array.

function quickSelect(arr, k) {
    if (k < 1 || k > arr.length) {
        return null;
    }

    function partition(low, high) {
        const pivot = arr[high];
        let i = low - 1;

        for (let j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                [arr[i], arr[j]] = [arr[j], arr[i]];
            }
        }

        [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
        return i + 1;
    }

    function select(low, high, k) {
        const pivotIndex = partition(low, high);

        if (pivotIndex === k - 1) {
            return arr[pivotIndex];
        } else if (pivotIndex > k - 1) {
            return select(low, pivotIndex - 1, k);
        } else {
            return select(pivotIndex + 1, high, k);
        }
    }

    return select(0, arr.length - 1, k);
}

const numbers = [3, 2, 1, 5, 6, 4];
console.log(quickSelect(numbers, 2)); // Output: 2 (2nd smallest element)

Time Complexity: Average case O(n), worst case O(n^2), where n is the length of the array.

6. Specialized Traversals

Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.

Example 17: Traversing a 2D array

Traversing 2D arrays (matrices) is a common operation in many algorithms.

function traverse2DArray(matrix) {
    const result = [];
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[i].length; j++) {
            result.push(matrix[i][j]);
        }
    }
    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(traverse2DArray(matrix)); // Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 18: Spiral Matrix Traversal

Spiral traversal is a more complex pattern often used in coding interviews and specific algorithms.

function spiralTraversal(matrix) {
    const result = [];
    if (matrix.length === 0) return result;

    let top = 0, bottom = matrix.length - 1;
    let left = 0, right = matrix[0].length - 1;

    while (top <= bottom && left <= right) {
        // Traverse right
        for (let i = left; i <= right; i++) {
            result.push(matrix[top][i]);
        }
        top++;

        // Traverse down
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;

        if (top <= bottom) {
            // Traverse left
            for (let i = right; i >= left; i--) {
                result.push(matrix[bottom][i]);
            }
            bottom--;
        }

        if (left <= right) {
            // Traverse up
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }

    return result;
}

const matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9, 10, 11, 12]
];
console.log(spiralTraversal(matrix));
// Output: [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 19: Diagonal Traversal

Diagonal traversal of a matrix is another interesting pattern.

function diagonalTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];

    for (let d = 0; d < m + n - 1; d++) {
        const temp = [];
        for (let i = 0; i < m; i++) {
            const j = d - i;
            if (j >= 0 && j < n) {
                temp.push(matrix[i][j]);
            }
        }
        if (d % 2 === 0) {
            result.push(...temp.reverse());
        } else {
            result.push(...temp);
        }
    }

    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(diagonalTraversal(matrix));
// Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

Example 20: Zigzag Traversal

Zigzag traversal is a pattern where we traverse the array in a zigzag manner.

function zigzagTraversal(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    const result = [];
    let row = 0, col = 0;
    let goingDown = true;

    for (let i = 0; i < m * n; i++) {
        result.push(matrix[row][col]);

        if (goingDown) {
            if (row === m - 1 || col === 0) {
                goingDown = false;
                if (row === m - 1) {
                    col++;
                } else {
                    row++;
                }
            } else {
                row++;
                col--;
            }
        } else {
            if (col === n - 1 || row === 0) {
                goingDown = true;
                if (col === n - 1) {
                    row++;
                } else {
                    col++;
                }
            } else {
                row--;
                col++;
            }
        }
    }

    return result;
}

const matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
console.log(zigzagTraversal(matrix));
// Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix.

7. Performance Considerations

When working with array traversals, it's important to consider performance implications:

1. Time Complexity: Most basic traversals have O(n) time complexity, where n is the number of elements. However, nested loops or recursive calls can increase this to O(n^2) or higher.

2. Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.

3. Iterator Methods vs. For Loops: Modern methods like forEach, map, and filter are generally slower than traditional for loops but offer cleaner, more readable code.

4. Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.

5. Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.

6. Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.

7. Avoiding Array Resizing: When building an array dynamically, initializing it with a predetermined size (if possible) can improve performance by avoiding multiple array resizing operations.

8. LeetCode 실습 문제

배열 순회 기술에 대한 이해를 더욱 강화하기 위해 연습할 수 있는 15가지 LeetCode 문제가 있습니다.

1. 투썸
2. 주식을 사고 파는 가장 좋은 시기
3. 중복 내용이 포함되어 있습니다
4. Self를 제외한 배열의 곱
5. 최대 하위 배열
6. 0 이동
7. 3썸
8. 물이 가장 많은 용기
9. 배열 회전
10. 회전 정렬 배열에서 최소값 찾기
11. 회전 정렬 배열에서 검색
12. 병합 간격
13. 나선형 매트릭스
14. 행렬 0 설정
15. 가장 긴 연속 시퀀스

이러한 문제는 광범위한 배열 순회 기술을 다루며 이 블로그 게시물에서 논의한 개념을 적용하는 데 도움이 됩니다.

9. 결론

배열 순회는 많은 알고리즘과 데이터 조작의 기초를 형성하는 프로그래밍의 기본 기술입니다. 기본 for 루프부터 슬라이딩 윈도우 및 특수 행렬 탐색과 같은 고급 기술에 이르기까지 이러한 방법을 익히면 복잡한 문제를 효율적으로 해결하는 능력이 크게 향상됩니다.

이 20가지 예를 통해 살펴본 것처럼 JavaScript는 배열 순회를 위한 풍부한 도구 세트를 제공하며 각 도구에는 고유한 장점과 사용 사례가 있습니다. 각 기술을 적용하는 시기와 방법을 이해하면 다양한 프로그래밍 문제를 처리할 수 있는 준비를 갖추게 됩니다.

숙련의 열쇠는 연습이라는 점을 기억하세요. 자신의 프로젝트에서 이러한 순회 방법을 구현해 보고, 기본 사항에 익숙해지면 주저하지 말고 고급 기술을 탐색해 보세요. 제공된 LeetCode 문제는 이러한 개념을 다양한 시나리오에 적용할 수 있는 충분한 기회를 제공합니다.

계속 기술을 개발하면서 선택한 순회 방법이 성능에 미치는 영향을 항상 염두에 두세요. 때로는 간단한 for 루프가 가장 효율적인 솔루션일 수도 있지만, 다른 경우에는 슬라이딩 윈도우나 2포인터 방법과 같은 보다 전문적인 기술이 최적일 수 있습니다.

즐거운 코딩 되시기 바랍니다. 배열이 항상 효율적으로 탐색되기를 바랍니다!

위 내용은 JavaScript를 사용한 DSA의 배열 탐색: 기본부터 고급 기술까지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!