![[코딩 테스트 합격자 되기]큐 접근하는게 효율적인 경우](https://cdn.inflearn.com/public/files/blogs/924aa5e6-5529-47f4-9018-cb2b0e9f5785/씨삐삐.png)
[코딩 테스트 합격자 되기]큐 접근하는게 효율적인 경우
큐를 사용하여 문제를 해결하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 큐를 사용하여 해결될 가능성이 높습니다.
선입선출 특성 (First In, First Out, FIFO)
큐는 선입선출 방식으로 동작합니다. 즉, 먼저 삽입된 요소가 먼저 제거됩니다. 따라서, 선입선출 특성을 이용해야 하는 문제에서 큐가 효과적입니다.
순차적 처리 (Sequential Processing)
큐는 순차적으로 데이터를 처리하는 데 유용합니다. 데이터를 순서대로 처리해야 하는 문제에서 큐를 사용하는 것이 적합합니다.
큐로 접근하는 게 효율적인 경우
큐의 대표적인 예시는 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘입니다.
BFS를 사용하여 그래프의 모든 노드를 탐색하는 과정은 아래와 같습니다. 예를 들어, 다음과 같은 그래프가 있을 때 시작 노드부터 모든 노드를 탐색합니다.
이를 코드로 구현하면 아래와 같습니다.
python코드 복사from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
위의 코드에서 큐는 현재 탐색 중인 노드를 저장하고, 각 노드의 이웃을 큐에 추가하여 순차적으로 탐색합니다. 이 방법은 선입선출 특성을 이용하여 각 노드를 너비 우선으로 탐색하므로 효율적입니다.
큐로 접근하는 게 효율적이지 않은 경우
반대로, 큐가 비효율적인 경우도 있습니다. 대표적인 예로는 배열의 특정 요소에 접근하여 값을 수정하는 문제가 있습니다.
배열의 특정 요소에 접근하여 값을 수정하는 과정은 아래와 같습니다.
주어진 배열의 특정 인덱스에 값을 삽입하거나 수정합니다.
이를 코드로 구현하면 아래와 같습니다.
def modify_array(arr, index, value):
if 0 <= index < len(arr):
arr[index] = value
return arr
이 코드에서, 큐를 사용하여 각 요소를 저장하고 꺼내어 값을 수정할 수도 있습니다. 그러나 이는 불필요한 메모리 사용과 연산을 증가시킵니다. 단순히 배열 인덱스를 사용하여 접근하는 것이 더 효율적입니다.
def modify_array_with_queue(arr, index, value):
queue = deque(arr)
for i in range(len(queue)):
if i == index:
queue[i] = value
return list(queue)
이와 같이, 배열의 특정 요소에 접근하여 값을 수정하는 문제는 큐를 사용하지 않는 것이 더 효율적입니다. 큐의 선입선출 특성이 불필요하게 사용되기 때문입니다.
따라서, 큐를 사용해야 하는 문제는 주로 선입선출 특성을 활용해야 하는 문제나 순차적으로 데이터를 처리해야 하는 문제입니다.
댓글을 작성해보세요.