큐 검색 결과

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

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

Queue를 직접 구현해야 할 때에는 어떻게 해야 할까요? 사실, 선형 큐를 먼저 고려합니다. 큐는 먼저 넣은 친구가 먼저 빠지는 특성을 지닙니다. 예를 들자면, 은행 창구를 생각해 보세요. 먼저 번호표를 뽑은 손님이 먼저 처리됩니다. 그런가요? 그렇기 때문에, 포인터가 front하고 rear, 이렇게 2개가 있는데요. front는 제일 앞에 있는 것을, rear는 제일 뒤에, 넣을 위치를 가리킵니다. 선형 큐를 구현할 때, 저는 is_full 처리를 하지 않아요. 그렇기 때문에 초기 크기를, 큐에 들어가는 원소의 갯수 + 10로 잡습니다. 예를 들어서, 가로 r개, 세로 c개의 맵이라면 BFS를 돌릴 때, rc만큼 들어가기 때문에 크기를 rc + 10 정도로 잡습니다. 처음에 front와 rear의 값..
자료알고/자료구조 2019. 8. 16. 23:57