DFS & BFS탐색 (Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로 DFS, BFS가 있다. 이를 이해하기 위해 몇 개의 자료구조를 먼저 알아봐야 한다.자료구조 기초스택 (Stack)선입후출(FILO) or 후입선출(LIFO) : 나중에 들어온 것이 먼저 나감Python의 list : 삽입(append), 삭제(pop)예시 : (박스 쌓기) 아래에서 위로 쌓고 아래의 박스를 치우기 위해 위의 박스를 먼저 내려야 함큐 (Queue)선입선출(FIFO) : 먼저 들어온 것이 먼저 나감python의 deque : 삽입(append), 삭제(popleft)예시 : (대기 줄) 입..
문제24511번: queuestack문제 이해queuestack : 1, 2, ..., N번의 자료구조(큐 or 스택)가 나열되어 있으며 각 자료구조에는 한 개의 원소가 들어 있음queuestack의 작동x0 입력x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x1x1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x2...xn-1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 xnxn 반환입력받은 M개의 정수(C)를 queuestack에 차례로 삽입했을 때의 반환값(xn)을 출력출력 예시자료구조가 어떤 형태인지 글로는 한 번에 와닿지는 않는다. 첫 번째 출력 예시로 확인해 보자.N = 4A = [0, 1, 1, 0]B ..
문제20278번: 스택 2문제 이해문제에 주어진 방식의 스택을 구현 (총 5개)풀이Deque 라이브러리 학습을 위해 List가 아닌 collections의 deque 라이브러리 사용각 입력에 따른 결과를 나타낼 수 있도록 코딩코드sys.stdin.readline 함수는 일반적으로 input 함수보다 빠르기 때문에 2-3줄은 코딩 테스트에서 거의 필수로 적고 시작하는 코드이다. deq.append(end[2:-1]) 부분은 첫 부분의 명령어와 공백을 제외한 정수 부분을 인덱싱 한다.from collections import dequeimport sysinput = sys.stdin.readlinedeq = deque()N = int(input())for i in range(N): cmd = input..
데크(Deque)란?큐(queue)는 선입선출(FIFO) 방식으로 작동하며, 스택(Stack)은 후입선출(LIFO) 방식으로 작동한다. 큐와 스택이 합쳐져 양방향에서 Push와 Pop을 할 수 있는 자료구조가 데크(Deque)이다. 앞, 뒤 방향에서 요소(element)를 추가하거나 제거할 수 있다. 큐와 스택은 반대쪽에 존재하는 요소를 Pop 하려면 O(n)의 시간이 필요하지만, 데크를 사용하면 어느 방향이든 O(1)의 시간으로 연산을 수행할 수 있다.파이썬 라이브러리 deque파이썬에서는 데크를 라이브러리로 사용할 수 있다. 아래의 공식문서에서 자세한 설명과 예시를 확인해 볼 수 있다. 여기에는 알고리즘 문제를 해결할 때 필요한 연산을 정리하려고 한다. collections — Container da..
