몽상실현개발주의

[종만북] Queue, Stack, Deque / 큐와 스택, 데크 큐와 스택, 데크 Queue 큐 한쪽 끝에서 자료를 넣고 반대 쪽 끝에서 자료를 꺼낼 수 있다. 가장 먼저 들어간 자료를 가장 먼저 꺼내게 된다. FIFO (First In First Out) 선입선출 Stack 스택 한쪽 끝에서만 자료를 넣고 뺄 수 있다. 가장 늦게 들어간 자료를 가장 먼저 꺼내게 된다. LIFO (Last In First Out) 후입 선출 전산학 전반에 걸쳐 널리 사용된다. 함수 호출이 끝나고 이전 함수로 돌아갈 때, 이 함수 바로 이전의 함수로 돌아가야 하는데 컴퓨터는 내부적으로 스택(Stack)을 사용하여 함수들의 문백(context)를 관리한다. Deque 데크 양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료 구..

[알고리즘 기초] 05_Stack 2 / Python 1. 계산기 문자열로 된 계산식이 주어질 때, 스택이 이용하여 이 계산식의 값을 계산할 수 있다. 문자열 수식 계산의 일반적 방법 step1. 중위 표기법의 수식을 후위 표기법으로 변경한다. (스택 이용) step2. 후위 표기법의 수식을 스택을 이용하여 계산한다. 1.1 중위표기식의 후위표기식 변환 방법. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현한다. 각 연산자를 그에 대응하는 오른쪽괄호의 뒤로 이동시킨다. 괄호를 제거한다. 1. ( ( A * B ) - ( C / D )) 2. ( ( A B ) * ( C D ) / ) - 3. AB * CD / - 1.2 중위표기식의 후위표기식 변환 방..

[알고리즘 기초] 04_Stack 1 / Python 1. Stack(스택) 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 이다. 스택에 저장된 자료는 선형 구조를 갖는다. 선형구조 : 자료 간의 관계가 1대 1의 관계를 갖는다. 비선형구조 : 자료 간의 관계가 1대 N의 관계를 갖는다. (ex. 트리 구조) 트리구조: 트리구조는 가지치기형으로 생긴 구조이다. 부모자식 관계로 형성. 스택에 자료를 삽입하거나 스택에서 자료를 꺼낼 수 있다. 마지막에 삽입한 자료를 가장 먼저 꺼낸다. LIFO(후입선출) 이라고 부른다. ex) 1, 2, 3 순으로 삽입 -> 3, 2, 1 순으로 꺼낼 수 있음 2. 스택의 구현 - 스택을 프로그램에서 구현하기 위해 필요한 자료구조와 연산 자료구조: 자료를 선형으로 저..

[BOJ] 10799 / 쇠막대기 / Python 파이썬 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 풀이 [BOJ] 9012 / 괄호 문제의 응용이다. 쇠막대기를 표현한 괄호를 각각 여는 괄호"(" : +1 닫는괄호 ")" : -1 겹치지는 쇠막대기 갯수를 카운팅 해주었다. "()" 를 찾아 레이저 절단 위치를 찾아 잘라진 조각을 더해주고, 조각이 끝나는 부분에서 잘려진 쇠막대 조각이 하나 더 생기는 것을 추가로 더해주었다. pipe = input(..

[BOJ] 9012 / 괄호 / Python 파이썬 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 풀이 괄호는 여는 괄호인 "(" 와 닫는 괄호인 ")" 의 개수와 괄호의 구성이 맞는 VPS 를 찾는 문제이다. "(" 가 나오면 +1 을 ")" 가 나오면 -1 을 해주는 방법으로 여는 괄호와 닫는 괄호의 수를 맞추어주고, 모든 괄호가 끝나는 경우에 합이 0이 되는 경우에만 "YES" 를 출력하면 된다. N = i..

[BOJ] 10828 / 스택 / Python 파이썬 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Stack 을 구현하는 문제이다. Python 의 List 를 활용하면 된다. import sys N = int(sys.stdin.readline()) stack = [] for _ in range(N): order = sys.stdin.readline().split() if order[0] == 'push': stack..