본문 바로가기

스택

(5)
[BOJ] 2439 탑 문제: https://www.acmicpc.net/problem/2493 2009년 초등부 지역본선 4번, 고등부 지역본선 2번 문제이다. 그만큼 난이도도 매우 쉬운 스택 문제기는 한데 처음 보면 스택 문제가 아니라고 생각할 수도 있을 거라 생각한다. 풀이는 다음과 같다. 이 문제를 푸는 가장 적절한 알고리즘은, 왼쪽부터 탑의 높이를 차례대로 보면서 스택의 맨 위와 비교해서, 스택의 수가 더 클 때까지 pop하고 그 때 숫자를 출력하는 것이다. 굉장히 단순하기 짝이 없지만 제대로 동작하는 알고리즘이다. 대략적으로라도 증명을 해보자. 1. 이 알고리즘을 썼을 때 원래 부딪혀야 하는 곳보다 왼쪽에서 부딪히는 경우는 없다.원래 부딪혀야 하는 것보다 왼쪽에서 부딪혔다고 가정해 보자. 스택에서 pop을 할 때 원..
[BOJ] 1918 후위표기식 문제: https://www.acmicpc.net/problem/1918 후위표기식은 스택의 대표주자라 할 만큼 중요한 내용이다.알고리즘은 간단하다. 1. 열린 괄호 -> push2. 닫힌 괄호 -> 열린 괄호가 나올때까지 pop3. 피연산자 -> 그대로 출력4. 연산자 -> 자기보다 우선순위가 낮거나, 열린 괄호가 나오거나, 스택이 빌 때까지 pop 후 push 코드는 이를 그대로 구현했다.4번에 열린 괄호가 나오는 것을 별도로 처리해주지 않은데 주의. 난이도는 1.5/5 정도? 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using ..
[BOJ] 1874 스택 수열 문제: https://www.acmicpc.net/problem/1874 굉장히 간단해 보이는 문제와 굉장히 간단한 해법이다.그저 숫자를 스택에 차례대로 넣으면서 지금 빼야 하는 숫자가 top이면 pop해주면 된다.만약에 모든 알고리즘이 끝났는데도 stack이 비지 않았다면 NO. 코드를 좀 더 깔끔하게 짤 수 있을 것 같다. 고민 좀 해 봐야징아마 난이도는 1/5 정도 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include using namespace std; stack S;vector oper; int main(){ int i=1,j=1,n,a..
[BOJ] 3986 좋은 단어 문제: https://www.acmicpc.net/problem/3986 사실 괄호 문자열 처리하는 문제와 다를 것이 전혀 없습니다. 굳이 스택을 써야 하는지도 모르겠는 문제... 지만 어쨌던 간에 스택 태그가 달려있어서 풀어봤습니다. 코드에서 '_'를 먼저 추가해서 오버플로우를 방지한 영향으로 만족 조건이 S.empty()가 아닌 S.size()==1이 된 것에 주의합시다. 난이도는 1/5. 기초 중의 기초. 12345678910111213141516171819202122232425262728293031323334#include #include #include using namespace std; int solve(){ char str[100005]; stack S; S.push('_'); scanf(..
[BOJ] 2841 외계인의 기타 연주 문제: https://www.acmicpc.net/problem/2841 설명: 항상 가장 높은 플랫만이 연주된다는 점에서 실마리를 찾아볼 수 있다. 어떤 줄 A에 만약 B의 음을 연주해 달라는 쿼리가 들어왔다고 하자. 1. 현재 그 줄에 누르고 있는 손가락이 없는 경우 이 경우에는 당연히 주어진 음에 해당하는 손가락을 누르고 음을 연주하면 된다. 이때 손가락을 한번 누른다. 2. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음과 같은 경우 손가락을 따로 움직일 필요 없이 그냥 음을 연주하면 된다. 3. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음보다 낮은 경우 주어진 음에 해당하는 플랫을 누르고, 그 다음 음을 연주하면 된다 4. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어..