몽상실현개발주의

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

[BOJ] 1261 / 알고스팟 / Python 파이썬 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 누적 합이 가장 적은 구간을 찾는 문제이다. 처음에는 deque 를 이용한 bfs 로 구하였는데 시간초과가 발생 하였다. 어느 경우에서든 "누적 합" 이 적은 경우로 진행하여야 하기 때문에, 우선순위 queue 로 해결하여야 효율적으로 해결 할 수 있었다. 이를 위하여 deque 에서 appendleft 로 누적합이..

[BOJ] 9019 / DSLR / Python 파이썬 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 전형적인 Queue 를 사용한 BFS 문제라고 생각하였다가 시간초과로 꽤나 고생을 하였다. 풀고나니 파이썬으로는 해결이 불가능 하다고 결론을 내었지만 그래도 배울것이 많은 문제였다. List 로 visted 를 만드는 것보다, set 이 더 빠르다. List 에서 in 을 사용하는 탐색은 O(n) -> list 의 index..

[BOJ] 10866 / 덱 / Python 파이썬 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque 자료구조의 동작을 구현하는 문제이다. import sys N = int(sys.stdin.readline()) dq = [] for _ in range(N): order = sys.stdin.readline().split() if order[0] == 'push_front': dq = [int(order[1])] ..