0과 1의 쉼터

목록Stack이란?Python에서 Stack 구현 방법✏️ 연습 문제📚 Stack후입선출(LIFO, Last In, First Out) 구조를 가진 자료구조💡 가장 나중에 삽입된 데이터가 가장 먼저 삭제됩니다! 스택의 주요 연산push(x): 스택의 맨 위에 요소 x를 추가한다.pop(): 스택의 맨 위 요소를 제거하고 반환한다.top() / peek(): 스택의 맨 위 요소를 제거하지 않고 반환한다.size(): 스택에 포함된 요소의 개수를 반환한다.isEmpty(): 스택이 비어 있는지 확인한다.Python에서 Stack 구현 방법Python에서는 내장 자료구조인 list 를 사용해 스택을 구현할 수 있습니다.스택 정의Python의 list를 사용해 stack을 선언합니다.stack = [] # ..

문제https://www.acmicpc.net/problem/1935 풀이스택을 사용해 후위표현식을 구현하면 된다.우선, 수식의 문자에 대응하는 숫자를 매핑해주자. num = {} for i in range(N): num[chr(ord("A") + i)] = int(input())연산 기호를 입력 받기 전 까지 모든 숫자를 스택에 저장해주고,연산 기호를 입력받으면 스택에 저장해둔 두 수를 꺼내 계산을 한 뒤 다시 스택에 저장하면 된다.이 과정을 반복하면 스택에는 후위 표현식에 대한 계산 결과가 남는다. # Solve stack = [] for f in F: if f.isalpha(): stack.append(num[f]) ..

풀이입력받은 문자열 S에 대해 압축을 해제하는 문제다.압축된 문자열은 K(Q)의 형식으로 주어지며 이를 해제할 경우 Q를 K번 반복한다는 의미다.스택과, 재귀 중 스택으로 푸는 방법이 익숙해 스택을 사용해 풀이했다. K(K(Q)K(Q))와 같은 예외를 고려해 문자열의 역순으로 진행했다.정작 제공된 테스트케이스에는 이와 같은 예외가 없었다.우선 ')' 인 경우에는 그냥 stack에 집어넣자.그 다음에는 Q에 해당하는 수들이 들어올 것이다.만약 stack의 마지막 요소가 ')'가 아니라면 Q의 길이를 저장하는 방식이므로 주어진 수( num )를 넣거나 더해주자.탐색을 계속 진행해 '(' 가 나온다면 스택에 넣은 Q의 길이를 뽑아 K와 곱해준 후 다시 스택에 넣어주면 된다.이 과정에서 중복계산과 스택에 남아있..

문제어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.어떤 식을 여러 쌍의 괄호가 감쌀 수 있다...

문제 성애는 이번 학기에 전공을 정말 많이 듣는다. 이로 인해 거의 매일을 과제를 하면서 보내고 있다. 그런데도 과제가 줄어들 기미가 보이지 않는데, 바로 분단위로 과제가 추가되고 있기 때문이다. 다행히 과제 제출 기한은 학기가 끝날 때까지이다. 너무나도 많은 과제를 하다가 미쳐버린 성애는 아래와 같은 규칙으로 과제를 해 나가고 있다. 과제는 가장 최근에 나온 순서대로 한다. 또한 과제를 받으면 바로 시작한다. 과제를 하던 도중 새로운 과제가 나온다면, 하던 과제를 중단하고 새로운 과제를 진행한다. 새로운 과제가 끝났다면, 이전에 하던 과제를 이전에 하던 부분부터 이어서 한다. (성애는 기억력이 좋기 때문에 아무리 긴 시간이 지나도 본인이 하던 부분을 기억할 수 있다.) 성애는 과제를 받자마자 이 과제가..

문제 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이다. 압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오. 입력 첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다. 문자열은 (, ), 0-9사이의 숫자로만 들어온다. 출력 첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다. 풀이 문자열 압축 문제이기 때문에, 문제에서 주어진 압축해제 방식으로 가장 안쪽 압축부터 풀어주면 된다. 때문에 가장 안쪽 압축이 나올 때 까지 stack에 push만 해주며 ..

문제 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다. 빈 문자열은 안정적이다. S가 안정적이라면, {S}도 안정적인 문자열이다. S와 T가 안정적이라면, ST(두 문자열의 연결)도 안정적이다. {}, {}{}, {{}{}}는 안정적인 문자열이지만, }{, {{}{, {}{는 안정적인 문자열이 아니다. 문자열에 행할 수 있는 연산은 여는 괄호를 닫는 괄호로 바꾸거나, 닫는 괄호를 여는 괄호로 바꾸는 것 2가지이다. 입력 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가..

문제 bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다. PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 정확하게는 다음과 같이 정의된다. P는 PPAP 문자열이다. PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다. 예를 들어 PPAP는 PPAP 문자열이다. 또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다. 문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라. 입력 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 ..

문제 상근이의 상상의 친구 외계인은 손가락을 수십억개 가지고 있다. 어느 날 외계인은 기타가 치고 싶었고, 인터넷에서 간단한 멜로디를 검색했다. 이제 이 기타를 치려고 한다. 보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다. 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 예를 들면, 4번 줄의 8번 프렛을 누르고 튕길 수 있다. 만약, 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생한다. 예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있다고 하자. 이때, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고 다른 손..

문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다. ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값..