배열 순회는 모든 개발자가 숙지해야 하는 데이터 구조 및 알고리즘(DSA)의 기본 개념입니다. 이 포괄적인 가이드에서는 기본 접근 방식부터 시작하여 고급 방법까지 진행하면서 JavaScript에서 배열을 탐색하는 다양한 기술을 살펴보겠습니다. 쉬운 수준부터 고급 수준까지 20가지 예시를 다루며, 학습을 강화하기 위한 LeetCode 스타일의 질문도 포함합니다.
배열 순회는 일부 작업을 수행하기 위해 배열의 각 요소를 방문하는 프로세스입니다. 이는 프로그래밍에서 중요한 기술로, 많은 알고리즘과 데이터 조작의 기초를 형성합니다. JavaScript에서 배열은 데이터를 탐색하고 조작하는 다양한 방법을 제공하는 다목적 데이터 구조입니다.
배열 탐색의 기본 방법부터 시작해 보겠습니다.
클래식 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은 배열의 길이입니다.
특히 종료 조건이 더 복잡한 경우 배열 순회에 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)이지만, 음수를 조기에 발견하면 더 작아질 수 있습니다.
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을 만나면 더 작아질 수 있습니다.
배열을 역순으로 탐색하는 것은 많은 알고리즘에서 일반적인 작업입니다.
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은 배열의 길이입니다.
ES6 및 이후 버전의 JavaScript에는 순회 및 조작을 단순화하는 강력한 배열 방법이 도입되었습니다.
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은 배열의 길이입니다.
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은 배열의 길이입니다.
필터 메소드는 특정 조건을 통과하는 모든 요소로 새 배열을 생성합니다.
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은 배열에서 가장 큰 숫자입니다.
리듀스 메소드는 배열의 각 요소에 리듀서 함수를 적용하여 단일 출력값을 생성합니다.
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은 배열의 길이입니다.
이제 배열 순회를 위한 몇 가지 중간 기술을 살펴보겠습니다.
두 포인터 기법은 배열 관련 문제를 효율적으로 해결하기 위해 자주 사용됩니다.
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.
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.
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.
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.
Let's explore some more advanced techniques for array 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.
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.
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.
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.
Some scenarios require specialized traversal techniques, especially when dealing with multi-dimensional arrays.
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.
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.
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.
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.
When working with array traversals, it's important to consider performance implications:
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.
Space Complexity: Methods like map and filter create new arrays, potentially doubling memory usage. In-place algorithms are more memory-efficient.
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.
Early Termination: for and while loops allow for early termination, which can be more efficient when you're searching for a specific element.
Large Arrays: For very large arrays, consider using for loops for better performance, especially if you need to break the loop early.
Caching Array Length: In performance-critical situations, caching the array length in a variable before the loop can provide a slight speed improvement.
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.
배열 순회 기술에 대한 이해를 더욱 강화하기 위해 연습할 수 있는 15가지 LeetCode 문제가 있습니다.
이러한 문제는 광범위한 배열 순회 기술을 다루며 이 블로그 게시물에서 논의한 개념을 적용하는 데 도움이 됩니다.
배열 순회는 많은 알고리즘과 데이터 조작의 기초를 형성하는 프로그래밍의 기본 기술입니다. 기본 for 루프부터 슬라이딩 윈도우 및 특수 행렬 탐색과 같은 고급 기술에 이르기까지 이러한 방법을 익히면 복잡한 문제를 효율적으로 해결하는 능력이 크게 향상됩니다.
이 20가지 예를 통해 살펴본 것처럼 JavaScript는 배열 순회를 위한 풍부한 도구 세트를 제공하며 각 도구에는 고유한 장점과 사용 사례가 있습니다. 각 기술을 적용하는 시기와 방법을 이해하면 다양한 프로그래밍 문제를 처리할 수 있는 준비를 갖추게 됩니다.
숙련의 열쇠는 연습이라는 점을 기억하세요. 자신의 프로젝트에서 이러한 순회 방법을 구현해 보고, 기본 사항에 익숙해지면 주저하지 말고 고급 기술을 탐색해 보세요. 제공된 LeetCode 문제는 이러한 개념을 다양한 시나리오에 적용할 수 있는 충분한 기회를 제공합니다.
계속 기술을 개발하면서 선택한 순회 방법이 성능에 미치는 영향을 항상 염두에 두세요. 때로는 간단한 for 루프가 가장 효율적인 솔루션일 수도 있지만, 다른 경우에는 슬라이딩 윈도우나 2포인터 방법과 같은 보다 전문적인 기술이 최적일 수 있습니다.
즐거운 코딩 되시기 바랍니다. 배열이 항상 효율적으로 탐색되기를 바랍니다!
위 내용은 JavaScript를 사용한 DSA의 배열 탐색: 기본부터 고급 기술까지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
