스택

백준 2493번 탑 문제 풀이입니다. 2493번: 탑 (acmicpc.net) 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2009 정올 초등부, 고등부 문제입니다. 직전에 포스팅했던 '옥상 정원 꾸미기'와 유사점이 많은 문제입니다. 문제 요약 및 분석 오른쪽에서 왼쪽으로 레이저를 발사하는데 탑의 기둥부분(벽면)에 맞으면 수신이 되는 방식입니다. 높이가 다른 각 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지가 문제입니다. 이때 N = 5 x 10^5 으로 O(n)이나 O(NlogN) 안에는 들어와야..

백준 6198번 옥상 정원 꾸미기 문제 풀이입니다. 6198번: 옥상 정원 꾸미기 (acmicpc.net) 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 2006 USACO Silver 문제입니다. 개인적으로 문제 푸는데 이걸 스택으로 푼다는 걸 떠올리는데 오래걸렸던 것 같습니다. 문제 요약 및 분석 왼쪽에서 오른쪽으로 각 빌딩에 대해서 크거나 같지 않은 빌딩의 개수를 구하는 문제가 되겠습니다. 일단 입력을 보았을 때 N = 8 x 10^4 입니다. N^2으로 풀면 시간 초과가 날 것 같고 N이나 N..

백준 1406번 에디터 문제 풀이입니다. 1406번: 에디터 (acmicpc.net) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제요약 키보드로 에디터에 텍스트를 입력하듯 명령을 했을 때 최종 글자를 출력하는 문제입니다. 단, 입력 할 수 있는 경우는 '커서 좌로 1칸이동', '커서 우로 1칸이동', '백스페이스', '알파벳 입력' 4가지 입니다. 문제 접근 아래의 그림까지만 떠올리면 쉽게 풀 수 있습니다. 커서를 움직인다는 접근보다, 커서는 가만히 가운데 있고 좌우로 글자가 스택에 쌓이는 그림을 떠올릴..

백준 10799번 쇠막대기 문제 C++ 풀이입니다. 10799번: 쇠막대기 (acmicpc.net) 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 2015 초, 중등부 정올 지역본선 문제입니다. 문제 요약 레이저로 잘린 쇠막대기의 개수를 구하는 문제인데, 입력값이 괄호로 이뤄져 있습니다. 1. 모든 레이저는 "( )" 로만 표현됩니다. 2. 나머지 괄호는 막대기의 양 끝을 표현하게 됩니다. 이때 문제에 중요한 조건이 있습니다. '쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다' 항상 안쪽에 위치하는 괄호가 더 짧은..