프로그래머스 인공지능 데브코스 3기 1주차 Day2(1)

1. 큐를 배열과 연결 리스트로 구현 했을 때, 각 경우의 시간 복잡도 비교

연산	배열	연결 리스트
size()	O(1)	O(1)
isEmpty()	O(1)	O(1)
enqueue()	O(1)	O(1)
dequeue()	O(n)	O(1)
peek()	O(1)	O(1)

size() 가 O(1)인 이유는 추상적 자료구조상에서 'nodeCount'라는 변수를 가지고 있기 때문에 상수시간이다.

같은 이유로 isEmpty()도 상수시간이다.

 

배열로 구현한 큐에서 enqueue을 한다는 것은 끝에 삽입이 되는 것이고, 연결 리스트로 구현한 큐에서 enqueue는 tail의 next에 삽입이 되는 상황이다. 때문에 두 개의 구현 방식 모두 enqueue가 될 때에는 O(1) 즉, 상수 시간에 이뤄진다. 

 

배열로 구현한 큐에서 dequeue을 한다는 것은 맨 앞에서 삭제가 되는 것인데, 이때 나머지 원소들이 전부 앞으로 이동해야하기 때문에 O(n)시간이 걸리게 된다. 반면에 연결 리스트로 구현한 큐에서는 head가 가리키고 있는 node만 끊어주면 되는 것이기 때문에 O(1) 즉, 상수 시간에 이뤄진다. 

 

강의에서 학습한 연결 리스트는 크게 3종류라고 볼 수 있다.

 

1. basic : 가장 기본 적인 리스트

2. modified : head에 dummy node를 위치하고 insertAfter(), popAfter()를 추가하여 약간 수정된 리스트

3. doubly : 양방향 연결 리스트

 

각 종류는 삽입, 삭제되는 위치 그리고 prev 노드를 알고 있는지의 여부에 따라서 연산 시간이 조금씩 달라진다. 

다만, 큐의 연산을 보면 삽입은 tail에서만, 삭제는 head에서만 이뤄진다. 

따라서 학습한 리스트 종류(basic, modified, doubly)에 상관없이 삽입 삭제 모두 O(1) 즉, 상수 시간에 연산이 수행된다.

 

2. 환형 큐(Circular Queue) 구현 시 front, rear 프로퍼티의 초기값을 '-1'로 설정하면 좋은 점?

개인적으로 답을 내려보자면, 

연산중에서 enqueue, dequeue, peek을 구현하는 코드에는 1을 더하면서 새로운 위치와 원하는 데이터를 찾는다.

큐가 비어있는 상태에서 enqueue를 하거나, 최초로 dequeue 또는 peek을 하게되면 front, rear의 초기값 -1에 1을 더하여 0이 된다. 

그렇기 때문에 일관성 있는 코드로 정확한 위치와 데이터에 접근 할 수 있게 된다.  

 

3. 우선순위 큐(Priority Queues)의 기준은 무엇일까?

어떻게 보면 이러한 의문을 갖는 것이 이상 할 수 있다... 나는 왜 이런 생각을 한지 모르겠다

 

일반적으로 쓰이는큐는 선입선출(FIFO)이다. 즉, 특정한 기준 없이 삽입된 순서에 의존하여 값이 나온다.

우선순위 큐는 값의 크기에 따라서 기준을 두고 우선순위를 매기긴다. 즉, 정렬이 된다는 뜻이다. 

 

따라서 우선순위 큐는 두 가지 형태를 가지고 있을 수 있다.

1. Max-Priority : 가장 우선순위에 있는 원소가 가장 큰 값

2. Min-Priority :  가장 우선순위에 있는 원소가 가장 작은 값

 

이처럼 우선순위 큐는 최댓값과 최솟값을 찾을 때 효율적이다.