https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 단순함 속에서도 배울 건 존재하기 마련이다. 문제 자체는 굉장히 단순하지만, 어째서인지 deque가 아닌 리스트로 접근하면 시간 초과가 발생한다. 풀이 자체에 큰 어려움을 느끼지는 않았지만 소개할 두 번째 풀이가 조금 감명 깊었다. 알고리즘에 수학이 필연적인 이유를 어렴풋이 느끼게 되었달까... # PYTHON CODE (1) - 리스트 매서드 실패 1 2 3 4 5 6 7 8 9 n = int(..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 알고리즘 공부는 프로그래머스의 '어서 와 알고리즘은 처음이지?' 강좌와 'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책 두 가지로 기초를 다졌는데, 큐에 대해 소개된 내용은 스택과 크게 다르지 않다. 더욱이 collections의 deque모듈을 이용하면 스택과 큐 두 가지 동시에 사용할 수 있기 때문에 그 경계가 또한 모호해진다. 'DOIT 자료구조와 함께 배우는 알고리즘 입문' 책에 소개된 큐의 개념 중에 링 버퍼라는 알고리즘이 있는데, 우선 그것부터 소개해보려 한다. 1158번..
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 풀어본 스택 문항 중에 가장 어려웠다. 고려해야할 조건도 너무 많았고, 약간의 구글링의 결과 분할정복이나 트리 쪽 문제라는 얘기도 있어서 추가적인 학습 후 돌아와야하나 고민하던 문제다. 계속 수정에 수정을 거듭하다보니 처음 의도했던 코드가 마구잡이로 더러워져서... 첫 접근 방법과 가장 스택다운 풀이를 소개하는 걸로 마무리 지으려한다. 첫 ..
