스택

1. Stack이란? 후입선출(Last In First Out) 즉 나중에 들어간 데이터가 제일 먼저 나오는 성질을 가지는 자료구조이다. 시간복잡도 : O(1) 2. Stack구현 Push(int value) : value를 스택의 최상단에 삽입 Pop() : 최상단의 원소를 스택에서 제거. 만약 스택이 비었다면 프로그램 종료 Top() : 스택의 최상위 원소를 반환. 만약 스택이 미었다면 프로그램 종료 Size() : 스택의 원소의 갯수를 반환. isEmpty() : 스택이 비어있는지 여부를 반환. #include #include using namespace std; class Stack{ private: int *arr; int top; int capacity; public: Stack(int siz..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. Logic 1. pair를 원소로 가지는 stack 하나를 선언한다. pair는 이다. 2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로 스택을 항상 내림차순으로 정렬해..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 처음 이 문제를 봤을 때는 작은 숫자 순서대로 다 빼주면 되는 줄 알았다. Case 3을 보면 작은 수 부터 다 빼주면 477584이기 때문에 정답이 아니다. 결국 이 문제를 일반화 시켜보게 되면 알고리즘은 "현재 보고 있는 수보다 작은 수가 앞에 있으면 앞에 있는 수를 지워야 한다." 이다. 문제에 나온 TestCase 3을 예시로 들어 설명하자면 10 4 4177252841 지울 수를 걸러내는 로직은 스택에 값이 있고(비어있지 않고) 숫자를 지울 수 있으..