简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)
집 > 웹 프론트엔드 > JS 튜토리얼 > 본문

JavaScript를 사용하여 DSA에서 배열 조작 마스터하기: 기초부터 고급까지

王林
풀어 주다： 2024-09-06 18:30:35
원래의
994명이 탐색했습니다.

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

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

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

목차

  1. 배열 소개
  2. 어레이 순회
  3. 배열에 삽입
  4. 배열에서 삭제
  5. 배열에서 검색
  6. 고급 배열 조작 기술
  7. 연습 문제
  8. LeetCode 문제 링크

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)

7. 연습문제

다음은 쉬운 수준부터 고급 수준까지 다양한 연습 문제 50개입니다. 이들 중 일부는 LeetCode에서 가져온 반면 다른 일부는 일반적인 배열 조작 시나리오입니다.

  1. 배열의 모든 요소 합
  2. 배열에서 최대 요소 찾기
  3. 그 자리에서 배열 뒤집기
  4. 정렬된 배열에서 중복 항목 제거
  5. k 단계씩 배열 회전
  6. 배열에서 두 번째로 큰 요소 찾기
  7. 두 개의 정렬된 배열 병합
  8. 1부터 n까지의 배열에서 빠진 숫자를 찾아보세요
  9. 모든 0을 배열의 끝으로 이동
  10. 두 배열의 교차점 찾기
  11. 두 배열의 합집합 찾기
  12. 어레이가 다른 어레이의 하위 집합인지 확인
  13. 배열에서 평형 지수 찾기
  14. 양수와 음수를 배열로 재배열
  15. 배열에서 주요 요소 찾기
  16. 배열에서 피크 요소 찾기
  17. 원형 배열 구현
  18. 배열에서 누락된 가장 작은 양수 찾기
  19. 빗물 고임 문제
  20. 배열을 사용하여 스택 구현
  21. 배열을 사용하여 대기열 구현
  22. 가장 긴 증가 부분 수열 찾기
  23. 회전 정렬 배열에서 이진 검색 구현
  24. 크기 k인 하위 배열의 최대 합 찾기
  25. Kadane 알고리즘 구현
  26. 기차역에 필요한 최소 승강장 수를 찾아보세요
  27. 0과 1의 개수가 같은 가장 긴 하위 배열을 찾습니다
  28. 네덜란드 국기 알고리즘 구현
  29. 합이 주어진 값보다 큰 가장 작은 하위 배열을 찾습니다
  30. Boyer-Moore 과반수 투표 알고리즘 구현
  31. 최대 제품 하위 배열 찾기
  32. 점프 게임 알고리즘 구현
  33. 배열의 모든 요소에 대해 다음으로 큰 요소 찾기
  34. 슬라이딩 윈도우 최대 알고리즘 구현
  35. 반복되는 문자가 없는 가장 긴 부분 문자열 찾기
  36. 병합 간격 알고리즘 구현
  37. 배열의 끝에 도달하기 위한 최소 점프 횟수 찾기
  38. 이익 극대화 알고리즘을 구현하기 위해 주식 매수 매도
  39. 가장 긴 회문 부분 문자열 찾기
  40. 최장 공통 부분 수열 알고리즘 구현
  41. 가장 짧고 정렬되지 않은 연속 하위 배열 찾기
  42. 물이 가장 많은 용기 알고리즘 구현
  43. 배열에서 가장 긴 연속 시퀀스 찾기
  44. 세 숫자의 최대 곱 알고리즘 구현
  45. 배열에서 K번째로 큰 요소 찾기
  46. 배열에서 중복 항목 모두 찾기 알고리즘 구현
  47. 최소 크기 하위 배열 합계 찾기
  48. Array Except Self 알고리즘의 곱 구현
  49. 정렬된 배열에서 최대 간격 찾기
  50. 두 개의 정렬된 배열의 중앙값 알고리즘 구현

8. LeetCode 문제 링크

다음은 배열 조작 기술을 테스트할 수 있는 20가지 LeetCode 문제입니다.

  1. 투섬
  2. 주식을 사고 파는 가장 좋은 시기
  3. 중복 내용이 포함되어 있습니다
  4. Self를 제외한 배열의 곱
  5. 최대 하위 배열
  6. 병합 간격
  7. 3썸
  8. 물이 가장 많은 용기
  9. 배열 회전
  10. 회전 정렬 배열에서 검색
  11. 회전 정렬 배열에서 최소값 찾기
  12. 다음 순열
  13. 하위 배열의 합은 K와 같습니다
  14. 나선형 매트릭스
  15. 점프 게임
  16. 가장 긴 연속 시퀀스
  17. 배열에서 모든 중복 찾기
  18. 배열에서 K번째로 큰 요소
  19. 빗물 가두기
  20. 두 개의 정렬된 배열의 중앙값

이러한 문제를 해결하고 기본 개념을 이해함으로써 데이터 구조 및 알고리즘을 위한 JavaScript의 배열 조작 기술을 크게 향상시킬 수 있습니다.

이러한 기술을 익히는 열쇠는 일관된 연습과 솔루션의 시간 및 공간 복잡성을 이해하는 것임을 기억하세요.

즐거운 코딩하세요!

위 내용은 JavaScript를 사용하여 DSA에서 배열 조작 마스터하기: 기초부터 고급까지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천：dev.to
이전 기사：uick이 웹 사이트 속도를 높이고 성능을 향상시키는 데 성공했습니다. 다음 기사：\"수명주기 후크\" 없이 생활하기
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
최신 이슈
function_exists()는 사용자 정의 함수를 결정할 수 없습니다. 기능 테스트() {                                                                                ...
에서 2024-04-29 11:01:01
0
2
1318
Chrome 모바일 버전을 표시하는 방법 안녕하세요 선생님, Chrome을 모바일 버전으로 어떻게 변경하나요?
에서 2024-04-23 00:22:19
0
9
1421
자식 창이 부모 창을 작동하지만 출력이 응답하지 않습니다. 처음 두 문장은 실행 가능하지만 마지막 문장은 구현할 수 없습니다.
에서 2024-04-19 15:37:47
0
1
1244
상위 창에 출력이 없습니다. document.onclick = function(){ window.opener.document.write('나는 자식 창의 출력입니다.');
에서 2024-04-18 23:52:34
0
1
1148
CSS 마인드맵 코스웨어는 어디에 있나요? 코스웨어
에서 2024-04-16 10:10:18
0
0
1227
관련 주제
더>
인기 추천
인기 튜토리얼
더>
관련 튜토리얼
인기 추천
최신 강좌
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트：공공복지 온라인 PHP 교육，PHP 학습자의 빠른 성장을 도와주세요！