본문 바로가기

분류 전체보기

(78)
[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. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어..
[자료구조] 스택 개인적으로 스택이란 자료구조를 굉장히 좋아하는 편이다. 사실 우리가 일상 생활에서 스택과 유사한 것을 보기는 쉽지 않긴 하지만 정보과학 문제를 풀 때는 스택을 사용하면 정말 예쁘게 풀리는 경우가 꽤 있기 때문이다. 그리고 웬만해서 그런 문제들은 좀 재미있기도 하고.. 스택(Stack)은 기본적으로 후입선출(LIFO, Last In First Out) 구조이다. 다른 말로 자료구조에 제일 먼저 넣은 값이 나올 때는 가장 마지막에 나오는 것이다. 정확히 Queue하고는 반대의 개념을 가지고 있다. 원소를 넣거나 뺄 때는 $O(1)$ 만큼의 시간복잡도를 가져야 하기 때문에 원래는 연결리스트를 사용하는 것이 정석이라고 알고 있기는 한데, 보통은 배열이나 vector로 구현하거나 아니면 그냥 맘편히 STL을 쓴다..
블로그를 처음 시작해보면서 사실상 진지하게 목표를 가지고 운영해 보려는 블로그는 이 블로그가 처음인 것 같다.다른 알고리즘으로 문제 푸는 것을 기록해두는 블로그도 꽤나 많은데, 그 블로그들 처럼 중간에 포기하지 않고 적어도 100문제 정도는 채워보는 것이 1차적인 목표다. 또 동아리에서 할 여러 알고리즘과 자료구조도 간단한 것부터 정리해 두려고 한다. 이렇게 정리해 두면 대학을 가던 어디를 가던 간에 도움이 될 것이라고 생각한다. 티스토리 초대장 주신 유쾌한삼이 님께 감사드립니다.