[알고리즘 고득점 kit] 스택 / 큐 (개념, 문제풀이)

스택

스택의 개념

• 스택
  • 쌓아 올린다는 것을 의미
  • 스택 자료구조는 책을 쌓는 것처럼 쌓아 올린 형태의 자료구조

스택의 특징

• 스택은 같은 구조의 크기와 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
• top에 있는 가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.
• 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다.
• 삽입하는 연산은 push, 삭제하는 연산은 pop
• 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징이 있다.
  • 비어있는 스택에서 원소를 추출하려고 하는 것 → stack underflow
  • 스택이 넘치는 경우 → stack overflow
• ⇒ 후입선출 구조

스택의 활용 예시

• 스택의 특징인 후입선출을 활용하여 여러 분야에서 활용 가능하다.
• 웹 브라우저 방문 기록
  • 가장 나중에 열린 페이지부터 다시 보여준다.
• 역순 문자열 만들기
  • 가장 나중에 입력된 문자부터 출력한다.
• 실행 취소
  • 가장 나중에 실행된 것부터 실행을 취소한다.
• 후위 표기법 계싼
• 수식의 괄호 검사

큐

큐의 개념

• 말 그대로 줄
• 선입선출 방식의 자료구조

큐의 특징

• 정해진 한 곳을 통해서 삽입, 삭제가 이루어지는 스택과 달리 큐는 한쪽 끝에서 삽입 작업, 다른 끝에서 삭제 작업이 이루어진다.
• 삭제 연산만 수행되는 곳을 프론트, 삽입연산만 이루어지는 곳을 리어로 정한다.
• 큐의 리어에서 이루어지는 삽입 연산을 인큐
• 큐의 프론트에서 이루어지는 삭제 연산을 디큐라고 한다.
• 즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔던 첫번째 원소
• 리어 원소는 가장 늦게 큐에 들어온 마지막 원소

활용 예시

• 큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
• 우선순위가 같은 작업 예약
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색 구현
• 캐시 구현

문제 풀이

같은 숫자는 싫어

 

자바스크립트

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

 

파이썬

def solution(arr):
    answer = []
    for e in arr:
        if answer and answer[-1] == e:
            continue
        answer.append(e)
    return answer

 

 

=> 로직은 같다. 현재 가리키고 있는 요소와 요소 -1의 인덱스를 가진 요소를 비교해서 다른 경우에만 answer에 push한다.

 

기능 개발

 

자바스크립트

function solution(progresses, speeds) {
    const answer = [];
    let days = progresses.map((progress, i) => Math.ceil((100 - progress) / speeds[i]));
    
    let maxDay = days[0];
    let count = 1;
    
    for (let i = 1; i < days.length; i++) {
        if (days[i] > maxDay) {
            answer.push(count);
            maxDay = days[i];
            count = 1;
        } else {
            count++;
        }
    }
    
    answer.push(count);
    return answer;
}

 

 

 

올바른 괄호

 

자바스크립트

function solution(s){
    let paren = 0;
    for (let i = 0; i < s.length; i++) {
        s[i] === "(" ? paren++ : paren--;
        if (paren < 0) {
            return false;
        }
    }
    return s.at(-1) == ")" && paren == 0;
}

 

프로세스

추후 수정

다리를 지나는 트럭

추후 수정

주식가격

 

추후 수정