본문 바로가기

Problem Solving

(59)
[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을 쓴다..