kth990303의 코딩 블로그

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 이 문제도 좀 유명한 편인데 뒤늦게 풀었다. N은 50만, 시간 제한은 1.5초라 상한 시간복잡도는 O(NlgN)인 문제이다. KOI 2009 지역본선 초등부 4번, 고등부 2번이기도 한 문제이다. 지역본선이라 그런지 난이도는 높지 않은 듯하다. (근데 애초에 초등학생이 이정도 문제 풀 정도면 대단한거 아닌가... 요즘 초등부 문제들이 워낙 괴랄해서 쉬워보이는건가...) 의식의 흐름 및 해설 처..

5월에 카카오 월간 코드 챌린지를 치고 나서, 내 약점 중 하나인 스택을 보완해야겠다고 느끼고 풀어본 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 의식의 흐름 및 해설 우선 올바른 괄호쌍끼리만 제거할 수 있다는 점을 파악한다. 따라서 "문자열 폭발" 과 비슷한 원리를 이용할 수 있으며, 이 괄호쌍들을 넣을지 안넣을지 고려하는 알고리즘을 짜봐야 하는데, 괄호쌍은 적어도 1, 많아..