배열(Arrary)이란?

배열이란?

프로그래밍에서 배열(array)은 동일한 유형의 여러 데이터(요소)를 하나의 변수 이름으로 저장할 수 있는 데이터 구조이다.

배열은 데이터를 연속적인 메모리 공간에 저장하며, 각 요소는 0부터 시작하는 고유한 번호인 '인덱스(Index)'를 통해 접근할 수 있다.

이를 통해 여러 데이터를 효율적으로 구성하고 관리할 수 있다.

원래 배열의 주요 특징은 아래와 같다.

1. 동일한 데이터 타입
   배열에 저장되는 모든 요소는 같은 종류의 데이터여야 한다. (모두 정수, 모두 문자열) (*언어 별로 다름)
2. 연속적인 메모리 할당
   배열의 요소들은 메모리 공간에 띄엄띄엄이 아닌 연속적으로 저장되어 효율적인 접근이 가능하다. (*언어 별로 다름)
   저수준 언어의 원시 배열은 값이 연속으로 놓이지만, 고수준 언어의 배열/리스트는 보통 참조가 연속이며 내부 표현이 달라질 수 있다.
3. 인덱스
   각 배열 요소는 인덱스라고 불리는 숫자로 위치를 지정하여 접근 가능하며, 인덱스는 0부터 시작한다. (*언어 별로 다름)
4. 고정 크기
   대부분의 프로그래밍 언어에서 배열은 생성 시 크기가 고정되어, 한 번 정해진 개수의 요소만 저장할 수 있다. (*언어 별로 다름)

현대 언어의 동적 배열과 배열 내 혼합 타입 허용

대부분의 현대 프로그래밍 언어는 동적 배열(데이터가 추가되거나 삭제될 때 자동으로 크기를 확장)을 제공한다.

(Java: ArrayList, Python: list, JavaScript: Array, 등)

그리고 파이썬, 자바스크립트, 루비 등은 언어의 타입 시스템이 동적 타입(Dynamic Typing)을 사용하고 있어서 배열 안에 여러 타입의 요소를 넣어도 된다.

C, Java, Go 등의 언어는 컴파일 시 타입을 검사하는 반면, 파이썬이나 자바스크립트는 런타임 시 타입을 검사한다.

(그렇다고 안된다는건 아닌데 자세한 건 이 글에서 다루진 않겠다..)

 

JS에서 배열과 문자열, 주요 메서드

프로그래밍에서 문자열(string)이란 여러 개의 문자가 순서대로 나열된 집합으로 대부분의 프로그래밍 언어에서 큰따옴표("")로 문자열을 둘러싸서 표현한다.

그리고 자바스크립트에서 배열이란 mdn에서는 정확히 이렇게 설명하고 있다.

"배열이란 일반적으로 리스트 같은 객체(list-like objects)이다. 배열은 보통 리스트에 저장된 다수의 값들을 포함하고 있는 하나의 객체이다." 자바스크립트는 객체(Obejct) 중심 언어이며, 자바스크립트의 배열은 진짜 리스트 구조를 메모리상에서 구현한 것이 아니라 리스트처럼 동작하도록 만들어진 객체인 것이다.

정리하자면 리스트(list)는 순서가 있는 데이터의 모음을 의미하는 자료구조이고, 자바스크립트에서 배열(Array)은 그 개념을 구현한 객체 기반 도구인 것이다.

const arr = ["apple", "banana", "cherry"];

console.log(arr[0]); // "apple"
console.log(arr["0"]); // "apple" 

// 배열 내부는 아래와 같이 표현된다.

{
  "0": "apple",
  "1": "banana",
  "2": "cherry",
  length: 3
}

문자열 관련 주요 메서드

const string = "ARRAY STUDY"
string[0] : 인덱스 접근 (문자열은 불변이므로, 인덱스로 접근은 가능하다)
string.length : 길이 조회
string.slice(start, end) : 부분 추출
string.split(sep, limit?) : 구분자로 나눠 배열 생성
string.concat(...) : 이어 붙이기
string.trim() : 공백 제거
string.toLowerCase() / string.toUpperCase
string.replace('ARRAY', 'Array') : 치환
string.includes() : 포함 여부
string.indexOf() : 검색 시작 위치
string.startsWith, string.endsWith : 접두/ 접미
[...string] : 스프레드

배열의 선언

// 1. 리터럴: []
// 2. 생성자: new Array(...) (또는 Array(...) — new 생략 가능)
// 3. from: Array.from(iterableOrArrayLike, mapFn?)
// 4. of: Array.of(...items)

1. 배열 리터럴: []
const a1 = [];                  // 빈 배열
const a2 = [1, 2, 3];           // 숫자 배열
const a3 = ['a', {x: 1}, []];   // 혼합 가능
console.log(a1, a2, a3);

2. 생성자: new Array(...)  (길이만 정해두고 채우는)
const b1 = new Array(3);     // 길이가 3인 *구멍 배열* [ <3 empty items> ]
const b2 = Array(3);         // new 생략 가능, 동일 동작
const b3 = new Array(1, 2);  // [1, 2]
const b4 = new Array('3');   // ['3']  ← 숫자가 아니면 그냥 그 값 하나

console.log(b1.length);      // 3
console.log(b1);             // [ <3 empty items> ]
console.log(b3);             // [1, 2]

Array(3).map((_, i) => i);  // [ <3 empty items> ]  ← map이 실행조차 안 됨
new Array(3).forEach(() => console.log('x')); // 아무것도 안 찍힘

// 반면, undefined로 채우면 동작함
Array(3).fill(undefined).map((_, i) => i); // [0, 1, 2]

3. Array.from(source, mapFn?)
// (1) 이터러블/유사배열 변환
const c1 = Array.from('hello');              // ['h','e','l','l','o']
const c2 = Array.from(new Set([1, 2, 2, 3])); // [1, 2, 3]
const c3 = Array.from({ length: 3 });        // [undefined, undefined, undefined]

// (2) 길이 + mapFn 초기화 (구멍 없이!)
const c4 = Array.from({ length: 5 }, (_, i) => i * 10); // [0, 10, 20, 30, 40]
console.log(c1, c2, c3, c4);

const sets = Array.from({ length: 3 }, () => new Set<number>());
sets[0].add(1);
console.log(sets[1].has(1)); // false (각 칸이 *다른* Set 인스턴스)

const bad = new Array(3).fill(new Set<number>()); // ❌ 모두 같은 Set 참조
bad[0].add(1);
console.log(bad[1].has(1)); // true (같은 객체를 가리킴)

배열 관련 주요 메서드

const arr = [1, 2];
arr.push(3); : 배열 끝에 요소 추가 // [1, 2, 3], 원본 변경
arr.pop(); : 배열 끝 요소 제거 // [1], 원본 변경
arr.unshift(1); : 배열 앞에 요소 추가 // [1, 1, 2], 원본 변경
arr.shift(); : 배열 앞 요소 제거, 원본 변경
[1, 2, 3].includes(2); : 값 존재 여부 확인, 원본 변경 X
['a','b','c','a'].indexOf('a'); : 첫 번째 인덱스 반환 (없으면 -1)

// arr.find : 조건을 만족하는 첫 요소 반환 (원본 변경 x)
const users = [{id:1}, {id:2}, {id:3}];
users.find(u => u.id === 2); 

// arr.some() : 하나라도 조건 만족 여부
[1, 2, 3].some(x => x > 2); // true
[1, 2, 3].some(x => x > 5); // false

// arr.every() : 조건 전부 만족 여부
[1, 2, 3].every(x => x < 5); // true
[1, 2, 3].every(x => x < 3); // false

// arr.map(로직) : 변환 후 새 배열 반환 , 원본 변경 x
[1, 2, 3].map(x => x * 2);  // [2, 4, 6]

// arr.filter(로직) : 조건 통과 요소만 남김, 원본 변경 X
[1, 2, 3, 4].filter(x => x % 2 === 0); // [2, 4]

// arr.reduce((acc, cur) => 로직, 초깃값) : 누적값 계산, 원본 변경 X
const arr = [1, 2, 3, 4];
arr.reduce((acc, cur) => acc + cur, 0);  // 10

// arr.slice(start, end) : 일부 복사, 원본 변경 X
const arr = [10, 20, 30, 40, 50];
arr.slice(1, 3);  // [20, 30]

// arr.sort() : 정렬
[5, 2, 9].sort();          // [2, 5, 9]
['b', 'a', 'c'].sort();    // ['a','b','c']

// 숫자 정확 정렬
[10, 2, 5].sort((a, b) => a - b); // [2,5,10]

//arr.join(sep) : 배열 -> 문자열
['a','b','c'].join('-'); // 'a-b-c'

// 스프레드 연산자: 얕은 복사, 원본 불변
const arr = [1, 2];
const copy = [...arr];           // [1, 2]
const merged = [...arr, 3, 4];   // [1, 2, 3, 4]

JS로 알아보는 주요 배열 관련 알고리즘

Sliding Window

"배열이나 문자열에서 일정한 범위를 유지하며 데이터를 탐색하는 기법"

배열이나 리스트와 같은 연속적인 데이터에서 고정된 크기의 '윈도우'를 이동시키면서 특정 구간의 값(합, 최대값, 평균 등)을 효율적으로 계산하는 기법이다.

윈도우가 한 칸씩 이동할 때마다 이미 계산했던 값을 재사용하여 중복 계산을 피하고, 전체적인 연산 시간을 크게 단축하는 것이 핵심이다.

아래 설명할 투포인터와는 구간의 길이가 항상 고정되어 있다는 차이점이 있다.

부분 문자열, 부분 배열의 길이나 합, 고유 문자 개수 등 "연속된 범위"에서 조건을 만족시키는 최적 구간을 찾는 문제에 자주 쓰인다.

윈도우를 확장/축소하면서 효율적으로 상태를 관리할 줄 알아야 한다.

 

대표적인 문제

1. Longest Substring Without Repeating Characters (LeetCode - 3)

문자열 S가 주어졌을때 중복을 제외한 가장 긴 문자열 길이 반환하기
Input: s = "abcabcbb"
Output: 3

// 아이디어: 문자 → 마지막 인덱스를 저장하는 맵. 
// 오른쪽을 늘리며, 중복을 만나면 왼쪽 포인터를 해당 문자 직후로 점프.

function lengthOfLongestSubstring(input) {
  const lastSeenIndex = new Map(); // character -> most recent index
  let leftIndex = 0;
  let bestLength = 0;

  for (let rightIndex = 0; rightIndex < input.length; rightIndex++) {
    const currentChar = input[rightIndex];

    // 현재 문자 중복이면, 해당 문자의 직후로 왼쪽 포인터 점프
    if (lastSeenIndex.has(currentChar) && lastSeenIndex.get(currentChar) >= leftIndex) {
      leftIndex = lastSeenIndex.get(currentChar) + 1;
    }

    lastSeenIndex.set(currentChar, rightIndex);
    const currentLength = rightIndex - leftIndex + 1;
    if (currentLength > bestLength) bestLength = currentLength;
  }

  return bestLength;
}

슬라이딩 윈도우는 이전 계산을 재활용하며 연속된 데이터를 효율적으로 분석하는 데에 좋다.

아래는 슬라이딩 윈도우의 가장 대표적인 응용 예시인 "이동 평균(Moving Average)"이다.

 

도시 A의 일일 평균 기온 데이터

일자	1	2	3	4	5	6	7
기온	12	13	15	14	16	15	18

위의 데이터를 기반으로 최근 3일 이동 평균을 구해 부드러운 추세선을 얻고 싶다고 하자.

 

• 3일 차 평균: (12 + 13 + 15) / 3 = 13.33
• 4일 차 평균: (13 + 15 + 14) / 3 = 14.00
• 5일 차 평균: (15 + 14 + 16) / 3 = 15.00
• 6일 차 평균: (14 + 16 + 15) / 3 = 15.00
• 7일 차 평균: (16 + 15 + 18) / 3 = 16.33

윈도우 크기가 3인 창을 유지하며, 하루씩 오른쪽으로 밀면서 나간 값만 빼고 새값만 더해 평균을 갱신하면 매번 구간 합을 처음부터 세지 않고 나간값, 들어온 값으로 갱신만 하면되서 성능이 더 좋다.

function movingAverageFixedWindow(temps: number[], days: number): number[] {
  if (days <= 0) throw new Error('days must be positive');
  if (temps.length < days) return [];

  const result: number[] = [];
  let windowSum = 0;

  // 초기 윈도우 합 (0 ~ days-1)
  for (let i = 0; i < days; i++) {
    windowSum += temps[i];
  }
  result.push(windowSum / days);

  // 윈도우를 오른쪽으로 한 칸씩 이동
  for (let right = days; right < temps.length; right++) {
    const left = right - days;           // 윈도우에서 빠질 인덱스
    windowSum = windowSum - temps[left] + temps[right];
    result.push(windowSum / days);
  }

  return result;
}

// 사용 예시
const temps = [12, 13, 15, 14, 16, 15, 18];
console.log(movingAverageFixedWindow(temps, 3));
// → [13.333333333333334, 14, 15, 15, 16.333333333333332]

 

Two Pointers 

정렬된 배열이나 문자열와 같은 선형 구조에서 두 개의 포인터를 이용하여 문제를 효율적으로 해결하는 탐색 기법이다.

두 개의 인덱스를 전략적으로 움직여 한 번의 선형 순회로 답을 찾는 것이 핵심이다.

일반적으로 보통 양 끝에서 시작해서 서로 좁혀가거나, 같은 방향으로 움직이며 진행하게 된다.

정렬된 배열에서 특정 조건을 만족하는 쌍을 찾는다거나, 정렬된 배열에서 합이 특정값이 되는 원소의 조합을 찾는다던지,

Palindrome 검사(문자열이 거꾸로 읽어도 같은지 확인)할때 쓴다던지 등등에서 활용도가 높다.
위의 슬라이딩 윈도우와의 차이는 슬라이딩 윈도우의 경우 고정된 크기의 윈도으를 이동시켜 구간의 길이가 고정되어 있지만, 투 포인터의 경우 구간의 길이가 유동적으로 변한다.

 

1. 정렬된 배열에서 목표 합을 만드는 두 수 찾기

function findTwoNumbersWithTargetSumSorted(
  sortedNumbers: number[],
  targetSum: number
): [number, number] | null {
  let left = 0;
  let right = sortedNumbers.length - 1;
  
  while (left < right) {
    const currentSum = sortedNumbers[left] + sortedNumbers[right]
    
    if (currentSum === targetSum){
    	return [sortedNumbers[left], sortedNumbers[right]];
    }
    
    if (currentSum > targetSum){
    	right -= 1;
    } else {
    	left += 1;
  }
  return null
}

// 예시
console.log(findTwoNumbersWithTargetSumSorted([1, 2, 3, 4, 6, 8, 11], 10)); // [2, 8]

 

2. 정렬된 배열에서 중복 제거 (reetcode 26)

function removeDuplicates(nums: number[]): number {
    if (nums.length === 0) return 0;

    let i = 0;
    for (let j = 1; j < nums.length; j++){
        if(nums[i] !== nums[j]){
            i++;
            nums[i] = nums[j]
        }
    }
    return i + 1
};

 

3. Palindrome (왼쪽에서 읽어도, 오른쪽에서 읽어도 같은 문자열)

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

 

투포인터의 핵심은 조건 확립(어떤 상황에서 두 포인터를 움직일지)과 두개의 포인터의 상태 관리라고 생각한다.

 

Binary Search

정렬된 배열에서 중간값을 기준으로 왼쪽/오른쪽 절반씩 버리며 찾는 알고리즘으로 매 단계마다 범위를 절반씩 줄이기 때문에 속도가 아주 빠르다.

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) {
      return mid; // 찾았다!
    } else if (nums[mid] < target) {
      left = mid + 1; // 오른쪽 절반으로 이동
    } else {
      right = mid - 1; // 왼쪽 절반으로 이동
    }
  }

  return -1; // 없을 때
}

// 예시
console.log(binarySearch([1, 3, 5, 7, 9, 11], 9)); // 4

 

DP (동적 프로그래밍)

Dynamic Programming, DP는 복잡한 문제를 여러 개의 작은 문제로 나누어 해결하는 알고리즘 설계 기법이다.

최적 부분 구조와 중복되는 부분 문제의 두 가지 조건을 만족할 때 유용하다. 한 번 해결한 작은 문제의 결과는 메모리에 저장해 두었다가, 같은 문제가 필요할 때 재사용하여 비효율적인 중복 계산을 줄이고 전체적인 수행 시간 효율성을 크게 향상시키는 방법이다.

최적 부분 구조 : 큰 문제의 해답이 그 문제의 작은 부분 문제들의 해답으로부터 만들어지는 구조

중복되는 부분 문제 : 동일한 작은 문제가 반복적으로 등장하는 경우를 말한다. DP는 이 중복되는 문제에 대해 한 번만 계산하여 결과를 저장하고 재활용 한다.