스택

[C++] 백준 2504번 괄호의 값

2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택 자료구조 문제. 구현력을 필요로 하는 노가다 문제이다. 문제 분석 스택 하나에 입력들을 넣어놨다가, 괄호가 닫히는 경우를 처리해주면 된다. 나같은 경우에는 다음과 같이 처리했다. 현재 입력이 '(' 또는 '['인 경우 -> 그냥 스택에 넣어준다. 현재 입력이 ')' 또는 ']'인 경우 -> 만일 스택의 위에 있는 게 숫자들일 경우, 다 더해준 후 *2 / *3을 해준다. 스택의 위에 있는 게 '(' / '[' 일 경우 '(' / '['를 빼내고 2를 넣어..

[C++] 백준 17298번 오큰수

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 자료 구조 - 스택 문제. 알고리즘 분류를 알고 풀어서 쉽게 접근할 수 있었다. 알고리즘 분류를 모르고 풀면 풀 수 있었을지 모르겠다. 문제풀이 다음과 같은 생각을 하고 풀었다. 큐를 두 개 만든다. 하나는 입력을 받아놓는 큐, 하나는 큐에서 꺼낸 수를 저장해놓는 큐. 입력을 받아놓는 큐에서 하나씩 꺼내보며 꺼낸 수를 저장해놓는 큐의 맨 위와 비교한다. 만일 큐가 비어있다면 오큰수가 없다는 뜻이다. 큐가 비어있지 않을 때에는 현재 수와 저장해놓은 큐의 맨 위의 수를 비교한다..

[C++] 백준 2493번 탑

스택을 이용해서 푸는 문제. 우선순위 큐로도 풀 수 있는 문제다. 자료구조의 기본적인 문제라고 한다. 평이 좋았던 문제였다. 문제풀이 탑들은 왼쪽 방향으로 레이저 신호를 보낸다. 만일, 자신의 왼쪽에 자신의 높이보다 큰 탑이 있을 경우에, 그 탑이 자기 자신의 레이저 신호를 받는 탑이 된다. 레이저 신호는 하나의 탑만 수신 가능하다. 즉, 스택, 우선순위 큐를 이용해서 탑의 높이를 기록해두는데, 지금 내가 탐색하는 탑의 높이보다 높은 탑의 높이가 나올 때까지 pop한다. 어차피 지금 탐색하는 탑보다 낮은 높이의 탑은 필요가 없기 때문이다. 그리고 stack에 넣을 때, 해당하는 높이가 몇번째 탑인지도 기록해 주어야 한다. 예제 6 9 5 7 4를 예로 들어보자. 1. stack : empty input ..

[C++] 백준 1874번 스택 수열

자료구조를 이용해서 푸는 문제. 스택 ADT에 대한 이해가 잘 돼있다면 쉽게 머리속에 그려낼 수 있다. 접근 방법 우선 예시로 주어진 테스트 케이스 1번 [4, 3, 6, 8, 7, 5, 2, 1]을 이용해서 살펴보자. 입력은 오름차순으로 이루어지므로 1, 2, 3, ...의 순서로 입력된다. 입력을 받을때마다 다음의 상황을 고려한다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 같다면 스택에 push한 후 pop한다. 이 때 수열에 넣어야하는 수와 스택에 있는 수가 같다면 계속해서 pop해준다. 현재 내가 입력하려는 수 i가 수열에 넣어야 하는 수와 다르다면 스택에 push만 한다. 예시상황으로 한번 살펴보겠다. 1 : 스택에 push하면 스택이 { 1 }의 상황이고 수열 [4, 3, 6, ..

[C++] 백준 10773번 제로

0을 부르면 최근에 적은 값을 지우고 아니라면 값을 넣는 문제. 최근에 있는 값을 빼야한다. -> 스택 문제 스택 자료구조를 쓰면 쉽게 풀 수 있다. 쉽게 맞출 수 있는 문제라 생각한다. GitHub - kimyunseok/study-record: my study-record my study-record. Contribute to kimyunseok/study-record development by creating an account on GitHub. github.com 코드는 위에서 확인이 가능하다.

[자료구조]2. 스택

STACK ADT, 스택 추상자료형 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다. 삽입과 삭제가 후입선출 구조로 이루어진다. 스택의 주요 기능은 다음과 같다. push(object) : element를 삽입한다. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다). 스택의 추가적인 기능은 다음과 같다. top() : 마지막으로 push된 element를 보여준다. size() : 저장된 elements의 수를 알려준다. empty() : 스택이 비어있는지 확인한다. 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다. Stack을 사용한 프로그램 예시에는 다음이 있다. 웹 브라우저 방문 기록 텍스트 편집기 되돌리기..