스택
-
[자료구조] 스택, 큐는 무엇인가? :: 마이구미알고리즘 2019. 9. 7. 22:35
이 글은 자료구조의 "스택, 큐" 를 다룬다. 자료구조에서 가장 먼저 나오는 기본적인 자료구조이다. 각 자료구조에 대한 깊은 설명보다는 현실적인 이해에 도움을 위해 다루려고 노력했다. 알고리즘 문제를 풀기 위해 알아야하는 지식을 위한 설명이 아닌, 현실적으로 활용할 수 있는 이해를 위한 도움에 중점을 둔다. 실제로 요즘은 자료구조를 생각하지않고도 코드를 작성할 수 있다. 예를 들어, 스택과 큐와 같은 개념은 배열로 처리하면 그만이다. 하지만 이 과정에서도 자료구조의 개념을 인지하고 활용하면 분명 코드와 개발에 도움이 된다. 본인은 왜 코딩테스트가 존재하는지도 연관이 있다고 생각한다. 자료구조를 구현하기 위한 코드를 작성해야하는가? 에 대한 글은 다른 글을 참고하길 바란다. 자료구조에서 가장 기본적인 스택..
-
백준 1935번 후위표기식2 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 16. 21:36
이번 글은 백준 알고리즘 문제 1935번 "후위표기식2" 를 다뤄본다.1918번 "후위표기식" 문제는 중위표기식에서 후위표기식으로 변환하는 문제였다. - 관련 링크이번 문제는 후위표기식을 계산하는 문제로써, 1918번 문제를 푼 후, 풀어보면 좋은 문제가 된다. 중위표기식에서 후위표기식 변환 문제도 사실상 방법만 알면 간단했다.후위표기식의 계산 또한, 단순하다. 피연산자는 스택에 push 한다.연산자가 나오면 스택에 있는 수를 2번 pop 한다.pop한 두 수를 연산자에 맞게 계산한 후, 다시 push 한다.모든 계산이 끝나면, 스택의 top이 최종 계산 값이 된다. for (int i = 0; i < len; i++) { char ch = s[i]; switch(ch) { case '+': case '..
-
백준 2841번 외계인의 기타 연주 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 6. 00:38
이번 글은 백준 알고리즘 문제 "외계인의 기타 연주" 를 다뤄본다.문제 접근법은 스택을 활용한다.정답 비율과 제출수를 보면 어려운 문제에 속한다.하지만 문제를 이해하기 어려운 것이지, 쉬운 문제로 해당된다. 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다.보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누..
-
백준 1725번 히스토그램 :: 마이구미알고리즘 풀이/스택, 큐 2017. 7. 2. 20:42
이번 글은 백준 알고리즘 문제 1725번 "히스토그램"을 다뤄본다.6549번 "히스토그램에서 가장 큰 직사각형" 또한 거의 동일한 문제가 된다. 문제의 접근은 스택을 활용한다. 각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오. 처음에는 도저히 생각이 나지 않아, 순수하게 접근했다.시간초과가 발생할 것을 알았지만, 일단 풀어보았다.단순히, 하나의 막대를 기준으로, 왼쪽 오른쪽에 대..
-
백준 2504번 괄호의 값 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 6. 25. 22:22
이번 글은 백준 알고리즘 문제 2504번 "괄호의 값"을 다뤄본다.정올 2008년 초등부, 중등부 문제로써, 스택을 응용한 문제가 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다.‘[]’ 인 괄호열의 값은 3이다.‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘..
-
백준 2493번 탑 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 18. 23:48
이번 글은 백준 알고리즘 2493번 문제 "탑" 을 다뤄본다.스택을 응용한 문제이다.백준 2493번 탑 문제 - https://www.acmicpc.net/problem/2493 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한..
-
백준 3986번 좋은 단어 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 16. 21:00
이번 글은 백준 알고리즘 3986번 "좋은 단어" 를 다뤄본다.이 문제는 스택을 통해 접근하는 문제이다.백준 3986번 좋은 단어 - https://www.acmicpc.net/problem/3986 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 갯수를 세는 것을 도와주자. 문제만 보면, 바로 쉽게 이해하기는 힘들 수 있다.먼저 예를 통해 문제를 이해해보자.ABAB 주어졌을 경우를 보자.1. ABAB => A와 A 위로 아치형 곡선을 그린다.2. ABAB => B와 B 위로 아치형 곡선을 ..