Arrays

in Notes / Codingtest / Datastructures

Queue, Stack,

Queue

  • 줄 서는 행위와 비슷하다
시간 복잡도  
검색, 수정O(n)#접근, 검색, 수정 모두 그 항목이 나올 때 까지 pop 해야 한다
삽입, 삭제O(1)FIFO, LILO
공간 복잡도  
모든 작업O(1)#새로운 공간 불필요
  • FIFO : First in, First Out
  • Enqueue : 데이터 넣기

  • Dequeue : 데이터 빼기

  • 구현 & 파이썬 제공 라이브러리
코드
  class myQueue():
    def __init__(self) -> None:
        self.q = []
        
    def enqueue(self, a):
        self.q.append(a)
    
    def dequeue(self):
        self.delData = self.q[0]
        del self.q[0]
        return self.delData
    
    def size(self):
        return len(self.q)

    def print(self):
        for i in self.q:
            print(i, end=" ")
        print()
1) Queue()
  import queue  #put(a), get(), qsize()

  q = queue.Queue() 
  q.put("TEST")  #enqueue "TEST"
  q.put(1)       #enqueue 1

  q.qsize()       #size = 2
    
  q.get()        #dequeue and returns "TEST" (First in First Out)
2) LifoQueue() 
  import queue
  q = queue.LifoQueue() #STACK의 기능을 한다

  q.put("TEST")
  q.put(1)

  q.qsize() # = 2
  q.get()   # deletes and returns 1
3) PriorityQueue()
  • 우선순위 큐 (데이터 입력 순서대로 get하는 것이 아닌, 초기에 설정된 우선순위로 get한다)
  import queue  
  q = q.PriorityQueue()

  q.put((10, "TEST"))   #put ( 우선순위, 데이터 )
  q.put((5, "CODING"))  
  q.put((7, 1))

  q.get()               # (5, "CODING")이 먼저 나온다

Two Pointer Algorithm

  • reduces time complexity (한번만 탐색)
  • sorted: \(O(n)\), unsorted: \(O(nlogn)\)
     --- --- --- --- --- --- --- --- --- 
| 1 | 5 | 2 | 8 | 6 | 3 | 4 | 9 | 0 |
 --- --- --- --- --- --- --- --- --- 
 ↑                                ↑
 startPtr                       endPtr
  • variants:
    1. Opposite Directional: 반대편에서 시작해 만날때까지 or 조건만족할때까지 좁혀짐
    2. Equi-Directional: 동시 시작, slow-runner & fast-runner
  • 연습문제: