[알고리즘] 자료구조 - 배열, 스택, 큐

배열

배열은 가장 기본적인 자료구조로 인덱스(Index)를 통해 데이터에 접근할 수 있음.

선언 방법

// 가장 기본적인 방법
const arr = []

// 특정 크기로 초기화 
const arr = new Array(5).fill(0);

여기에서 헷갈릴 수 있는 함정
fill([])은 빈 배열을 3개 만드는게 아닌, 하나를 만들어서 3칸 모두 같은 곳을 참조함

투 포인터(Two Pointer)

배열에서 가장 많이 나오는 패턴으로 두개의 포인터(L, R)를 사용해서 탐색 범위를 줄이는 기법

반대 방향
양 끝에서 안쪽으로 좁혀오기
L -> <- R

배열 문제

프로그래머스 LV2 42885번 구명보트
사람들의 몸무게 배열 people과 보트 최대 무게 limit가 주어질 때,
보트는 최대 2명까지 탈 수 있어. 최소 몇 번의 보트가 필요한지 구하시오

function sol(people, limit) {
  people.sort((a, b) => a - b); 
  let L = 0;
  let R = people.length - 1;
  let boats = 0;
  
  while(L <= R) {
	if(people[L] + people[R] <= limit) {
      L = L + 1;
    }
    R -= 1;
    boats++;
  }
  return boats;
}

Stack(스택)

스택은 LIFO - 마지막에 넣은게 가장 먼저 나오는 구조

JS에서는 배열 + push/pop으로 구현이 가능함

const stack = []
// push - 맨 위에 추가 
stack.push(1);	// [1]
stack.push(2);	// [1, 2]
stack.push(3); 	// [1, 2, 3]

// pop - 맨 위에 꺼내기 
stack.pop(); // 3반환, stack = [1, 2]

stack[stack.length - 1];

stack.length === 0

핵심 패턴
스택에 값 대신 인덱스를 저장하면, 나중에 인덱스끼리 뺴서 시간이나 거리를 계산할 수 있다.

스택 문제

프로그래머스 LV2 42584번 주식가격
초 단위로 기록된 주식가격 배열 prices가 주어질 때,
각 초의 가격이 몇 초 동안 떨어지지 않았는지 구하시오

function sol(prices) {
	const answer = new Array(prices.length).fill(0);
  	const stack = [];
  
  	for(let i = 0; i < prices.length; i++){
     	while(stack.length > 0 && prices[stack[stack.length] - 1] > prices[i]){
			const j = stack.pop();
          	answer[j] = i - j
        }
    while (stack.length > 0) {
    	const j = stack.pop();
    	answer[j] = prices.length - 1 - j;
	}
  	return answer;
}

큐(Queue)

큐는 FIFO - 먼저 들어온게 먼저 나가는 구조

JS 구현

// 방법 1 — 배열로 간단하게 (데이터 작을 때)
const queue = [];
queue.push(1);	// enqueue -> [1]
queue.push(2);	// enqueue -> [1, 2]
queue.shift();	// dequeue → 1 반환, queue = [2]

// 방법 2 — 인덱스 포인터 (데이터 클 때, O(1))
const queue2 = [1,2,3]
let front = 0;
queue2[front++];

큐 문제

프로그래머스 LV1 12906번 같은 숫자는 싫어
배열 arr에서 연속으로 나오는 같은 숫자는 제거하시오

function solution(arr)
{
    const stack = []
    
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] !== stack[stack.length - 1])
            stack.push(arr[i])        
    }
    return stack;
}

전체 요약

1. 배열

• 인덱스로 접근
• 정렬 후 투 포인터 사용
• 2차원 배열 초기화 주의

2. 스택

• LIFO
• DFS 사용

3. 큐

• FIFO
• BFS 사용