덱 검색 결과

해당 글 2건
백준 11003 최소값 찾기 : 큐와 덱를 응용해 봅시다.

요새 코테 철이 되었습니다. 저도 간간히 구현력을 잃어버리지 않기 위해서 조금씩 복기만 하고 있습니다. 백준 11003번 문제는 최솟값을 구하는 문제입니다. 특정 구간 [e-k, e]에서의 최솟값을요. 단, 0보다 작은 위치의 구간은 무시하고 구해야 합니다. 별로 어렵지 않아 보이는데, 문제는 n이 500만입니다. 입력 받느라 시간이 많이 가는 건 흐음. O(n)으로 줄일 수 있습니다. 다들 아시는 기법을 소개하도록 하겠습니다. 관찰을 해야 할 것은 2가지 상황입니다. 어떠한 데이터가 추가되는 상황하고, 제거되는 상황. i번째에 있는 데이터가 제거되면, 더 이상 추가되지 않는다는 것을 관찰하는 것 또한 포인트입니다. 현재, 이런 식으로 데이터가 들어갔다고 해 보겠습니다. 그리고 저는 7번째 위치에 있는 ..
자료알고/알고리즘 2020. 9. 11. 02:37
자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료알고/자료구조 2019. 8. 22. 01:05