본문 바로가기

스택

 (10)
[Python] 30855번 Fraction https://www.acmicpc.net/problem/30855 24/11/22  ICPC문제 중 흔치 않은 파이썬 친화적인 문제다. 문제 접근 방식:  파이썬에서는 fractions 모듈이 존재한다. 이 모듈은 유리수를 정확하게 저장해준다. 분모와 분자는 자동적으로 약분을 해서 저장된다. 문제는 굉장히 간단하다. $(a, b, c)$의 형태로 주어질 때, $a + b/c$의 값을 기약 분수로 출력하는 것이 목적이다. $a, b, c$는 숫자 혹은 또 다른 $(a, b, c)$형태의 괄호 문자열이 될 수 있다. 스택을 통해 해결할 수 있다. 예외를 처리하는 부분이 많은데, 그냥 raise문을 통해 Error를 띄우도록 하면 처리가 간편해진다. 예를 들어, 열린 괄호가 있는데 닫히지 않는다라던지, 맨 ..
[Python] 2733번 Brainf*ck https://www.acmicpc.net/problem/2733 24/11/18  입력 커맨드를 제외한 brainfuck 인터프리터를 구현하는 문제이다. 문제의 핵심 부분은 괄호 쌍을 찾아서 넘어가는 부분이다. 문제 접근 방식:  구현의 용이성을 위해, 먼저 파싱부분과 인터프리터 부분을 나눴다.  기본적으로 파싱부분은 하나의 테스트 케이스를 입력받아서 프로그램에 해당하는 하나의 문자열을 내뱉는 함수로 구현했다. 하나의 테스트 케이스는 'end'만 적혀 있는 문자열로 구분된다. 따라서 'end'라는 문자열이 입력되기 전 까지 계속해서 입력을 받는다. 파이썬은 줄바꿈을 기준으로 문자열을 입력받기 때문에, while True를 사용하여 'end'를 입력 받을 때까지 계속 입력받도록 했다. 이후, 주석의 처리..
[Python] 31235번 올라올라 https://www.acmicpc.net/problem/31235 31235번: 올라올라 길이가 $N$인 수열 $A$가 주어질 때, $N$ 이하의 양의 정수 $k$에 대하여 길이가 $N-k+1$인 수열 $B$를 다음과 같이 정의하자. $$B_{i}=\max_{i \le j \le i+k-1}A_j$$ 수열 $B$가 감소하지 않도록 하는 $k$의 최솟값 www.acmicpc.net 24/03/19 두 가지 방법으로 풀 수 있는 좋은 문제다. 그리디 + 스택으로도 풀 수 있고, 슬라이딩 윈도우+이분 탐색으로도 풀 수 있다. 개인적으로 전자가 더 쉽게 떠올릴 수 있다고 생각하지만 구현하는 데에 조금 실수가 생길 수 있고, 후자는 조금 더 어렵지만 구현하는 것이 그다지 어렵지 않아서, 어느 쪽으로 푸나 난이도..
[Python] 25918번 북극곰은 괄호를 찢어 https://www.acmicpc.net/problem/25918 25918번: 북극곰은 괄호를 찢어 극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$와 $X$를 보면 $()$와 $)($로 찢어버린다는 것이다. 협이는 이러한 북극곰의 특성을 이용하여 길이 $N www.acmicpc.net 22/11/07 에디토리얼에서는 그리디 문제라고 나와있었으나, 조금 스택을 곁들인 애드 혹 스러운 문제로, 쉬운 방법으로 구현할 수 있는 문제이다. 문제 접근 방식: 카운터 변수를 하나 선언을 해주고 괄호 문자열에서 (가 나오면 그 변수에 1을 더하고 )가 나오면 1을 뺐다. 북극곰은 항상 () 또는 )(처럼 열린 괄호와 닫힌 괄호를 쌍으로 생성하기 때문에, 북극곰이 생성..
[Python] 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 22/10/09 스택을 이용해서 푸는 문제로, 괄호 문자열 문제를 풀었다면 응용해서 풀 수 있는 문제이다.(유사한 유형임) 문제 접근 방식: 괄호 문자열이 옳은지 그른지 판단하는 문제와 동일하지만, 차이점은 괄호 문자열은 시작과 끝이 정해져 있지만 이 문제 같은 경우는 시작과 끝이 괄호 문자열처럼 명확하지 않다는 것이다. 나는 괄호 문자열의 풀이에서 힌트를 얻어, 스택에 문자들을 계속 쌓다가 현재 문자가 스..
[Python] 21144번 Missing Number https://www.acmicpc.net/problem/21144 21144번: Missing Number You are teaching kindergarten! You wrote down the numbers from $1$ to $n$, in order, on a whiteboard. When you weren’t paying attention, one of your students erased one of the numbers. Can you tell which number your mischievous student erased? www.acmicpc.net 22/09/25 어렵게 생각하면 어려운 문제이고, 쉽게 생각하면 쉽게 풀 수 있는 좋은 문제인 것 같다. 문제 접근 방식: 나는 이 문제를..
[Python] 15904번 UCPC는 무엇의 약자일까? https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 22/09/14 이 문제 또한 문자열 문제이지만 스택으로 접근했다. 정확히 말하면 정수 카운팅에 가깝지만, 어쨌든 그것 또한 스택을 추상적으로 모델링한 것이므로 스택을 이용한 것에 가깝다고 볼 수 있다. 문제 접근 방식: 문제는 일부 문자열을 지워서 UCPC를 만들 수 있는가를 묻는 문제이다. 나는 문자열을 하나씩 반복하여 돌다가 맨 처음에 U를 만나면 stack을 +1 해..
[Python] 17413번 단어 뒤집기 2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 22/09/14 조금 귀찮았던 문자열 문제로, 스택을 이용하여 문제를 접근했다. 문제 접근 방식: 문제 자체는 간단하다. 공백을 기준으로 단어가 정해지는데, 원래 문자열이 주어지면 단어만 전부 뒤집어서 출력해주는 문제이다. 나는 뒤집는다는 점에 주목하여 문자 하나하나를 스택에 담다가 공백을 만나면 그 스택을 뒤집어서 전부 출력하는 것으로 접근했다. 하지만 여기에서 ..

티스토리툴바