https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀어본 스택 문항 중에 가장 어려웠다. 고려해야할 조건도 너무 많았고, 약간의 구글링의 결과 분할정복이나 트리 쪽 문제라는 얘기도 있어서 추가적인 학습 후 돌아와야하나 고민하던 문제다. 계속 수정에 수정을 거듭하다보니 처음 의도했던 코드가 마구잡이로 더러워져서... 첫 접근 방법과 가장 스택다운 풀이를 소개하는 걸로 마무리 지으려한다. 첫 ..
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 친숙한 문제다. 예전에 프로그래머스 유료 강의('어서 와 자료구조 및 알고리즘은 처음이지?')를 수강하다가 스택의 연습 문항으로 나왔던 문제다. 당시에는 수업에서 해결 방향과 구조를 어느 정도 제시해주었기에 무감각하게 넘어간 기억이 있는데, 이렇게 만나니깐 등골이 서늘해지더라. 복습의 중요성을 한 번 다시 느꼈달까... 변명을 하자면 문제 해석에서 미스가 있었다. 예를 들어 a+b+c 의..
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 슬슬 스택 자체는 감이 온다. 답을 제출하기 전 돌려보는 예시들도 대게 정답을 return 하는 수준에는 온 것 같은데, 두 가지가 아직 깔끔하지 않다. 첫 번째는 시간 복잡도이다. 대략적으로 시간 복잡도를 계산하는 방법은 알고 있다만, 문제를 풀 때 이를 적용시키는 부분에 대해서는 아직 잘 이해가 안 간다. 문제를 풀 때도 이를 고려하지 않다 보니, 뭔가 힌트가 될 여지 하나를 놓치며 접근하는 것 같아 굉..
https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 커서 문제는 전에도 한번 풀어서 쉽게 풀었다. 한 번 풀어본 거랑 안 풀어본 건 정말 천지차이다. 백준 문제 풀면서 중에 가장 빨리 푼거 같아 나름 뿌듯하구먼. # PYTHON CODE (1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys from collections import deque n = int(sys.s..
https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 재밌는 문제! 근데 시간 초과가 자꾸 떠서 결국은 구글링. # PYTHON CODE (1) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import sys from collections import deque n = int(sys.stdin.readline()) s = list(map(int, sys.stdin.readline(..
https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 백준 저지에 업로드된 스택 문항들을 7개 정도 해결했는데, 이 문항이 가장 어려웠던 것 같다. 인간이 참 대단한게 겨우 괄호를 가지고 이런 문제들을 생각한다는 것도 참 놀랍다. 모든 문제가 그렇듯 이 문제 또한 은근히 심플한 풀이를 갖는다. 조건문이 남용되는 순간 뭔가 잘못되었음을 본능적으로 직감하게 되는데, 이 문제가 대표적으로 그랬다. 사고의 부족은 조건문의 남용으로 이어진다. 큰 틀을 짜고..
https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 분명 어디선가 봤는데, 어딘지 기억이 나질 않는다. 아마 그때는 해결을 못했던거 같은데... 나 혹시 성장한걸까? 모든 문제가 그렇듯 문제 자체는 참 단순하지만, 어떻게 접근하느냐에 따라 그 복잡도가 가히 천차만별이다. 이번 문제도 거의 4가지 풀이를 구사했는데, 한번 들어가보자. 첫 풀이는 문제 분류가 스택이다보니, 당연히 스택으로 접근했다. 근데 리스트로 구현하는 스택은 원소를 중간에 삽입하는건..
이진 탐색 알고리즘 문항들이 뒤로 갈수록 문제에 포함된 알고리즘으 종류가 많아지고 복잡해지기에 다른 알고리즘에 대한 숙련도가 부족하다면 결국 제자리걸음일 것 같아 스택으로 넘어왔다. 단순히 리스트 메서드를 이용한 스택 문항들은 쉽게 풀리지만 이중 연결 리스트를 이용한 스택은 기억이 잘 나질 않아 연결 리스트에 대한 복습도 할 겸 책을 들춰가며 클래스로도 구현을 해봤다. 이 포스팅은 두 문항 풀이를 올리고 다음 포스팅에 연결리스트 +a 해서 올려야겠다. # PYTHON CODE - 10773 1 2 3 4 5 6 7 8 9 10 11 12 13 import sys k = int(sys.stdin.readline()) stk1 = [] for _ in range(k): n = int(sys.stdin.r..
