알고리즘 자료구조 스택

스택

스택은 후입선출 원칙을 따르는 선형 자료구조이다. (회전초밥 접시, 브라우저 콜스택 등)

선형 자료구조란? 데이터가 일렬로 나열된 형태로 저장되는 자료구조를 말한다.

또한 추상 자료형이다. 즉, 데이터 구조의 논리적인 특성을 정의하지만 직접적인 구현은 추상화 하는 것이다. 구현 시 스택의 논리적인 특성인 LIFO을 따라야 한다. (Last In First Out - 나중에 들어간 데이터가 먼저 나온다)

이미지 출처 : programiz.com

스택을 그림과 같이 쌓아올리는 방식으로 추상화하는데, 저렇게 생겼다고 추상화만 하는 거지 실제로는 배열을 활용하는 거다. [1, 2, 3] 그냥 이런 배열임

스택은 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩 테스트에 효과적이므로 반드시 알아 두어야 한다. 후입 선출은 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통하기 때문이다.

제약 사항

• 데이터는 스택의 끝에서만 삽입 가능하다 -> push() 사용 / O(1)
• 데이터는 스택의 끝에서만 삭제 가능하다 -> pop() 사용 / O(1)
• 스택의 마지막 요소만 읽을 수 있다 -> at(-1) 사용 / O(1)

const stack = new Stack();

stack.push(10);
stack.push(20);

console.log(stack); // [10, 20]
console.log(stack.at(-1)); // 20

stack.pop();
console.log(stack); // [10]

주의

스택은 배열을 사용해 구현되지만, 스택의 본질적인 추상화 개념을 유지하려면 위 제약 사항을 지켜야 한다. 예를 들어, stack = [10, 20]과 같은 배열 형태로 값이 있을 때, stack[0]을 통해 첫 번째 요소 10에 접근할 경우 마지막 요소만 접근할 수 있다는 추상화 규칙을 위반하게 된다. 따라서 스택 사용 시에는 push, pop, stack[stack.length - 1]와 같은 방식으로만 요소에 접근하여 스택의 추상화 개념을 유지하는 것이 좋다.

스택 문제 풀기

막대기 (백준 17608)

이 문제는 막대기의 높이를 오른쪽에서 보면서 보이는 막대기의 개수를 구하는 문제이다. 핵심은 오른쪽에서부터 시작하여 가장 높은 막대기를 기준으로 더 높은 막대기를 찾는 방식이다.

해결 방법

1. 오른쪽부터 탐색: 오른쪽 끝에서부터 차례대로 막대기를 확인한다.
2. 최대 높이를 추적: 현재까지 본 막대기 중 가장 높은 값을 추적한다. 이 값을 기준으로 더 높은 막대기가 나오면 그 막대기는 보이는 것으로 간주된다.
3. 높이 비교: 막대기의 높이가 현재까지 추적한 최대 높이보다 크면 그 막대기는 보이는 것으로 판단하고, 그 높이를 새로운 최대 높이로 업데이트한다.
4. 보이는 막대기 개수 세기: 보이는 막대기의 수를 카운트한다.

코드

// 입력을 처리하여 첫 줄을 제외하고 막대기의 높이 배열을 얻음
const [_, ...arr] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .trim()
  .split("\n");
const input = arr.map(Number); // 각 줄의 높이를 숫자 배열로 변환

// 스택을 사용하여 오른쪽 끝부터 보이는 막대기들의 높이를 저장
const stack = [input.at(-1)]; // 가장 오른쪽 막대기를 스택에 추가 (첫 번째 보이는 막대기)

for (let i = input.length - 2; i >= 0; i--) {
  // 오른쪽에서 왼쪽으로 탐색
  // 현재 스택의 가장 높은 값(보이는 막대기의 최대 높이)보다 큰 경우만 스택에 추가
  if (stack.length && stack.at(-1) < input[i]) {
    stack.push(input[i]); // 보이는 막대기이므로 스택에 추가
  }
}

// 스택에 쌓인 막대기의 개수가 보이는 막대기의 총 개수
console.log(stack.length);

참고

• 코딩문-스택 (Stack) JS 알고리즘 마스터 클래스
• 알고리즘 코딩테스트 책 (이지스퍼블리싱)