진짜 백만 년에 알고리즘 문제풀이에 대해서 글을 쓴다.
그동안 잘 안 썼는데, 문제 푸는 것보다 글 쓰는 게 더 어렵다고 느껴졌기 때문이다.
그렇지만 이번에 쓰는 이유는 내가 잘 안 쓰는 자료구조이기도 하고,
학교 다닐땐 알고리즘 코딩 테스트에서 못 풀었었는데 지금은 푼 기념으로 정리하고자 글을 적는다.
이번에 쓸 자료구조는 queue의 변형인 circular-queue 다.
우선 queue 란,
stack 자료구조와 다르게 first-in first-out (FIFO)의 입출 로직을 갖는 자료구조를 얘기한다.
여기에 빈 배열이 있다고 치자.
[ ]
차례로 1,2,3 의 숫자를 집어넣는다 치면 (enqueue라고 한다.)
[1,2,3]으로 들어가고, 꺼낼 땐 (dequeue라고 한다.)
1 ← [2, 3]
2 ← [3]
3 ← [ ]
의 순서로 꺼내지는 배열 자료구조를 말한다.
하지만 오늘 볼건 이 배열을 원형으로 두른다. (일명 circular-queue)
왜? 원형으로 만드냐? 원형으로 만들면 무어가 좋더냐?
선형 큐의 문제점(배열로 큐를 선언할 시 큐의 삭제와 생성이 계속 일어났을 때, 마지막 배열에 도달 후 실제로는 데이터 공간이 남아있지만 오버플로우가 발생)을 보완한 것이 환형 큐이다. front가 큐의 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식이다.
자 그럼 기존 큐랑 다르게 무얼 고려해야 하느냐?
기존 큐엔 앞과 뒤가 고정되어있기 때문에 난 뒤!로 넣고, 앞!으로 빼면 된다
원형 큐의 경우
추가(뒤에 추가)하다가 배열 끝에 다다르면
맨 앞에 자리가 남았는지! 확인하고 넣을 수 있다는 점
때문에 front와 rear의 포인터를 두고 코드 내 고려해 짜야한다는 점이다.
(즉, rear의 index < front의 index 인 상황도 생긴다는 얘기… 이것만 해도 2학년의 나는 머리 아팠다.)
아래 그림의 마지막 enQueue 부분을 보자.
문제를 통해 살펴보자.
첫번째 문제
Design Circular Queue - LeetCode
Design Circular Queue - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
처음 문제를 봤을 때만 해도 원형 큐에 대해 무지했기 때문에 구글링을 통해 개념을 살펴봤다.
살펴본 블로그 → https://lktprogrammer.tistory.com/59
해당 블로그에선 원형 큐의 포화상태를 확인하기 위해 배열을 하나 크게 만들고 한 칸은 비워둔 채로 구현했다.
그래서 나 역시 원래 그렇게 구현하는 건가? 하면서 문제에 맞게 구현했다.
class MyCircularQueue:
def __init__(self, k: int):
self.qu = [-1] * (k+1)
self.front = 0
self.rear = 0
self.capacity = (k+1)원형 큐를 선언하는 부분이다.
인자로는 k 값이 들어오는데 이는 원형 큐의 전체 배열 크기이다. (=capacity)
위 블로그에 따라 배열을 입력으로 들어오는 k보다 +1칸 늘려준다.
입력되기 전 front, rear 포인터는 0으로 초기화해준다.
def isEmpty(self) -> bool:
if self.front == self.rear:
return True
else:
return False
def isFull(self) -> bool:
if (self.rear+1) % self.capacity == self.front:
return True
else:
return False원형 큐가 비어 있는지 확인하는 함수로는 isEmpty 가 있고,
front값과 rear 값이 같다면 현재 큐 배열에는 값이 들어있지 않기 때문이고, 그럼 True를 반환한다.
원형 큐가 포화상태인지 확인하는 함수로는 isFull이 있고,
rear+1 % capacity 값이 front 포인터와 같다면 포화상태로 판단, True를 반환한다.
배열의 크기를 1이라고 생각해보자 (k=1 → capacity = k+1 = 2)
생성자에 정의한 대로는 [-1, -1]이고 front와 rear는 각 0 인 상태다.
이때 1이라는 값을 큐 에 삽입시 rear값은 1 증가
[1,-1]이고 front = 0, rear = 1이다.
이때 isFull 함수를 실행 시
rear+1 % capacity ⇒ (1+1) % 2 → 0
front = 0 이므로 현재 큐 배열은 꽉 차 있는 상태라고 판단할 수 있다.
def enQueue(self, value: int) -> bool:
if (self.rear+1) % self.capacity != self.front:
self.qu[(self.rear+1) % self.capacity] = value
self.rear = (self.rear+1) % self.capacity
return True
else:
return Falseenqueue의 경우
위에서 살펴본 대로 꽉 차있는지 확인 후 아니라면
한 칸씩 넣어준다. 이때 rear+1 이 아니라 rear+1 % capacity로 rear의 포인터를 조정하는데
이 역시 원형 큐의 특성 때문이다. (배열의 마지막까지 채웠다면 맨 앞에 넣기 위해!)
def deQueue(self) -> bool:
if self.front != self.rear:
self.qu[(self.front+1)%self.capacity] = -1
self.front = (self.front+1)%self.capacity
return True
else:
return Falsedequeue의 경우
front와 rear가 같지 않은지 확인 후 (비어 있는지 확인)
비어있지 않다면 rear와 마찬가지로 해당 자리를 비워준다.
(역시 front+1 % capacity 로 포인터를 조정해준다.)
전체 코드는 아래와 같다.
class MyCircularQueue:
def __init__(self, k: int):
self.qu = [-1] * (k+1)
self.front = 0
self.rear = 0
self.capacity = (k+1)
def enQueue(self, value: int) -> bool:
if (self.rear+1) % self.capacity != self.front:
self.qu[(self.rear+1) % self.capacity] = value
self.rear = (self.rear+1) % self.capacity
return True
else:
return False
def deQueue(self) -> bool:
if self.front != self.rear:
self.qu[(self.front+1)%self.capacity] = -1
self.front = (self.front+1)%self.capacity
return True
else:
return False
def Front(self) -> int:
return self.qu[(self.front+1)%self.capacity]
def Rear(self) -> int:
return self.qu[self.rear]
def isEmpty(self) -> bool:
if self.front == self.rear:
return True
else:
return False
def isFull(self) -> bool:
if (self.rear+1) % self.capacity == self.front:
return True
else:
return Falseleetcode의 경우, 문제를 맞히면 관련 문제를 추천해주는데
추천받은 문제로 조금 더 심화 문제가 있어 가지고 왔다.
두 번째 문제
Design Circular Deque - LeetCode
Design Circular Deque - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
queue를 원형으로 만들면 circular-queue
queue를 양쪽에서 뺄 수 있게 만들면? double-ended queue (줄여서 deque)
근데 그 deque를 원형으로 만들면 바로 오늘의 문제 되시겠다.
- queue는 뒤!로 넣고, 앞!으로 뺀다.
- circular- queue는 뒤!로 넣고, 앞!으로 뺀다. 하지만 빙글빙글 돌기에 앞과 뒤를 내가 정의하고 알고 있어야 한다.
- circular- deque는 뒤로도 넣고, 앞으로도 넣고, 역시 빙글빙글 돌기에 앞과 뒤를 내가 정의하고 있어야 한다.
문제 보고 머리가 아팠었다.
게다가 위 문제처럼 한 칸 더 만들고, 그거의 앞과 뒤를 체크하고 하려니 먼가 직관적이지 않았다.
꼭 front, rear 포인트로 isFull, isEmpty를 체크해야 할까?
이때 지난번 본 java의 arrayList가 떠오르면서 count 개념을 도입했다.
데이터 추가 시 count + 1 , 데이터 제거 시 count - 1 이면
isEmpty는 count == 0 인지만 체크
isFull 은 count == capacity 인지만 체크하면 훨씬 직관적이고 편해진다.
class MyCircularDeque:
def __init__(self, k: int):
self.count = 0
self.capacity = k
self.dequ = [-1]*k
self.front = 0
self.rear = 0
위 문제와 다르게 이번엔 한 칸 더 설정하지 않는다.
대신 count 변수를 두고 데이터 입출력 시 +/- 작업을 해준다.
def isEmpty(self) -> bool:
if self.count == 0:
return True
else:
return False
def isFull(self) -> bool:
if self.count == self.capacity:
return True
else:
return False위와 다르게 front, rear의 포인터를 확인하는 게 아닌 단순히 count 값을 통해 확인하고 있다.
(확실히 직관적이고 짧아졌다.)
circular-queue와 동일하게 환형 큐로써, 뒤!로 넣고 앞!으로 나오는 로직은 동일하다.
def insertLast(self, value: int) -> bool:
if self.isFull() == False:
self.dequ[self.rear % self.capacity] = value
self.rear = (self.rear+1) % self.capacity
self.count += 1
return True
else:
return False
def deleteFront(self) -> bool:
if self.isEmpty() == False:
self.dequ[self.front] = -1
self.front = (self.front+1)%self.capacity
self.count -= 1
return True
else:
return False위 원형 큐와 다른 점은 rear+1을 데이터를 넣은 다음에 수행한다는 점이다.
그리고 넣은 다음엔 count + 1을, 뺀 다음엔 count - 1을 수행해준다.
그리고 대망의 deque 만의 앞으로 넣기
앞으로 넣을 땐 문제가
- 현재 queue에 들어있는 모든 값을 하나씩 뒤로 옮겨주어야 한다는 점
- 까먹지 말고 rear의 포인터를 +1 해줘야 한다는 점
이 존재한다.
def insertFront(self, value: int) -> bool:
if self.isFull() == False:
prev = self.dequ[self.front]
for i in range(self.front+1, self.front+self.count+1):
next_index = (i%self.capacity)
temp = self.dequ[next_index]
self.dequ[next_index] = prev
prev = temp
self.dequ[self.front] = value
self.rear = (self.rear+1)%self.capacity
self.count += 1
return True
else:
return False중간에 front 뒤부터 count 만큼 이동하면서 한 칸씩 뒤로 복사해주는 loop를 볼 수 있다.
이 때문에 맨 앞에서 넣는 작업 시 배열의 모든 값을 이동시키느라 가장 오래 걸리는 작업 O(N) 이 된다.
이와는 다르게 뒤로 뺄 때는 상대적으로 쉽다. rear-1을 해주면 된다.
def deleteLast(self) -> bool:
if self.isEmpty() == False:
self.rear = (self.rear-1)%self.capacity
self.dequ[self.rear] = -1
self.count -= 1
return True
else:
return False아래는 전체 코드이다.
class MyCircularDeque:
def __init__(self, k: int):
self.count = 0
self.capacity = k
self.dequ = [-1]*k
self.front = 0
self.rear = 0
def insertFront(self, value: int) -> bool:
if self.isFull() == False:
prev = self.dequ[self.front]
for i in range(self.front+1, self.front+self.count+1):
next_index = (i%self.capacity)
temp = self.dequ[next_index]
self.dequ[next_index] = prev
prev = temp
self.dequ[self.front] = value
self.rear = (self.rear+1)%self.capacity
self.count += 1
return True
else:
return False
def insertLast(self, value: int) -> bool:
if self.isFull() == False:
self.dequ[self.rear % self.capacity] = value
self.rear = (self.rear+1) % self.capacity
self.count += 1
return True
else:
return False
def deleteFront(self) -> bool:
if self.isEmpty() == False:
self.dequ[self.front] = -1
self.front = (self.front+1)%self.capacity
self.count -= 1
return True
else:
return False
def deleteLast(self) -> bool:
if self.isEmpty() == False:
self.rear = (self.rear-1)%self.capacity
self.dequ[self.rear] = -1
self.count -= 1
return True
else:
return False
def getFront(self) -> int:
return self.dequ[self.front]
def getRear(self) -> int:
return self.dequ[(self.rear-1)%self.capacity]
def isEmpty(self) -> bool:
if self.count == 0:
return True
else:
return False
def isFull(self) -> bool:
if self.count == self.capacity:
return True
else:
return False오늘은 학교 다닐 때 못 풀었던 circular queue를 살펴보았다. 끝!
'algorithm > leetcode' 카테고리의 다른 글
| Reservoir Sampling? 날 괴롭히지마 [leetcode] (0) | 2023.03.13 |
|---|---|
| binarySearch를 정렬된 리스트에 insert를 위해서만 사용한 나 조금 무례할지도 [leetcode] (0) | 2023.02.22 |
| Trie 자료구조와 문제풀이 [leetcode] (0) | 2022.06.21 |
| tree 문제 2개 (dfs & bfs) [leetcode] (0) | 2022.05.16 |
| tree 문제 2개 [leetcode] (0) | 2022.04.17 |
댓글