https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 단순해 보이는데, 생각할수록 뭔가 복잡해보였다. 역시 예시를 따라가며 구조를 파악하는 건 중요한듯 싶다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 import sys n, k = map(int, sys.stdin.readline().split()) s1 = list(sys.stdin.readline().rstrip()) stk1 = [] cnt = 0 for i in range(n): while cnt
https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net 지난번에 풀이한 히스토그램 문항이랑 같다. 근데 지난번 풀이때 놓친 부분이 있어서 간단히 소개하려한다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 n = int(input()) s1 = [int(input()) for _ in range(n)] s2 = [0] answer = 0 s1.insert(0, 0) s1.append(0..
https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제는 굉장히 어렵게 써있지만, 기본 스택 문항. 지금 휴가중이라 슬쩍슬쩍 공부중인데, 복귀해서는 큐부터 시작해서 다른 알고리즘 문항들에 손대기 시작할 것 같다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys n = int(sys.stdin.readline()) answer = 0 for _ in range(n): s ..
https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 앞서 풀어본 후위 표기식의 발전된 버전이다. 후위 표기식을 해결하지 못한 채 마주쳤으면 조금은 까다로웠을 수도 있는데, 결론적으로 꽤나 쉬운 문항이었다. 가장 어려웠던 부분이 첫 부분 알파벳에 숫자를 대입하는 부분일 정도. 아스키코드로 알파벳 값들을 계산하는 풀이들이 주를 이루던데, 아스키코드를 공부해본 적이 없어 그냥 뚝심으로 밀고 갔다. 간단하게 알파벳 리스트를 불러오는 string..
https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 목적지까지 걸어가는 길은 굉장히 다양하다. 이 문제의 경우 도처에 힌트들과 도구들을 직접 작성해놓고, 빙글빙글 돌아가다가 실패를 잔뜩 맛봤다. 사무실 pc에 첫 시도의 노력이 묻어있는데 호환의 문제로 개인 노트북으로 따로 글을 쓰는 중이라 완성된 코드만 올릴 수 있을 것 같다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 imp..
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 하는 수준에는 온 것 같은데, 두 가지가 아직 깔끔하지 않다. 첫 번째는 시간 복잡도이다. 대략적으로 시간 복잡도를 계산하는 방법은 알고 있다만, 문제를 풀 때 이를 적용시키는 부분에 대해서는 아직 잘 이해가 안 간다. 문제를 풀 때도 이를 고려하지 않다 보니, 뭔가 힌트가 될 여지 하나를 놓치며 접근하는 것 같아 굉..
