[week02/03.24]TIL

하루 한줄 요약

공부의 방향성, 쉽지 않지만 하나씩 안개를 걷어가는 느낌

오늘 공부한 것

• Queue 모듈 vs Deque 모듈
• 투포인터 vs 이분탐색
• 원형 힙

새로 배우게 된것

Queue 모듈 vs Deque 모듈

https://www.acmicpc.net/problem/18258

이 문제를 두가지 모듈을 활용하여 풀었다.
결론부터 말하자면 Queue 모듈은 동기화 기능때문에 내부적으로 최적화를 진행,
따라서 deque 모듈 대비 속도가 느리다.
따라서 Queue모듈로 풀면 시간 초과가 발생

# 큐의 6가지 명령 처리
# First In first out

from collections import deque
import sys
input = sys.stdin.readline
q = deque([])

def push(q, X):
  q.append(X)

def pop(q):
  if len(q) == 0:
    print(-1)
  else:
    print(q.popleft())

def size(q):
  print(len(q))

def empty(q):
  if len(q) == 0:
    print(1)
  else:
    print(0)

def front(q):
  if len(q) == 0:
    print(-1)
  else:
    print(q[0])

def back(q):
  if len(q) == 0:
    print(-1)
  else:
    print(q[-1])


N = int(input())
for i in range(N):
  command = input().split()

  if command[0] == 'push':
    push(q, int(command[1]))
  elif command[0] == 'pop':
    pop(q)
  elif command[0] == 'size':
    size(q)
  elif command[0] =='empty':
    empty(q)
  elif command[0] == 'front':
    front(q)
  elif command[0] == 'back':
    back(q)

# 큐의 6가지 명령 처리
# First In first out

import queue
import sys
input = sys.stdin.readline
q = queue.Queue()

def push(q, X):
  q.put(X)

def pop(q):
  if q.qsize() == 0:
    print(-1)
  else:
    print(q.get())

def size(q):
  print(q.qsize())

def empty (q):
  if q.qsize() == 0:
    print(1)
  else:
    print(0)

def front(q):
  if q.qsize() == 0:
    print(-1)
  else:
    print(q.queue[0])

def back(q):
  if q.qsize() == 0:
    print(-1)
  else:
    print(q.queue[-1])

N = int(input())
for i in range(N):
  command = input().split()

  if command[0] == 'push':
    push(q, int(command[1]))
  elif command[0] == 'pop':
    pop(q)
  elif command[0] == 'size':
    size(q)
  elif command[0] =='empty':
    empty(q)
  elif command[0] == 'front':
    front(q)
  elif command[0] == 'back':
    back(q)

투포인터 vs 이분탐색

https://www.acmicpc.net/problem/2470

• 투 포인터
  말 그대로, 리스트 양쪽 끝에서 2개의 포인터를 이동해가며 원하는 결과값을 얻는 방식

• 이분탐색
  나이맞추기 할때 up Down 하듯, 절반씩 범위를 좁혀가며 원하는 결과값을 얻는 방식

• 이분탐색 풀이

import sys
input = sys.stdin.readline

# 1. 입력받기
N = int(input())
num_list = list(map(int, input().split()))
num_list.sort()
# 단 0에 가깝다 = 절댓값이 작다

start = 0
end = len(num_list) - 1

def search(start, end, arr):
  first = arr[start]
  second = arr[end]
  min_sum = float('inf')
  if sum == 0:
    return first, second

  while start < end:
    if sum < 0:
      start = start + 1
      new_sum = arr[start] + arr[end]

      if abs(new_sum) < abs(sum):
        sum = new_sum
        first = arr[start]
        second = arr[end]
    else:
      end = end - 1
      new_sum = arr[start] + arr[end]
      if abs(new_sum) < abs(sum):
        sum = new_sum
        first = arr[start]
        second = arr[end]
  return first, second

print(*search(start, end, num_list))

• 투 포인터

import sys
input = sys.stdin.readline

# 1. 입력받기
N = int(input())
num_list = list(map(int, input().split()))
num_list.sort()

start = 0
end = len(num_list) - 1

def search(start, end, arr):
    first, second = arr[start], arr[end]
    min_sum = float('inf')

    while start < end: 
        current_sum = arr[start] + arr[end]

        if abs(current_sum) < abs(min_sum):  
            min_sum = current_sum
            first = arr[start]
            second = arr[end]

        if current_sum == 0:
            break
        elif current_sum < 0:  
            start += 1
        else:  
            end -= 1
            
    return first, second

print(*search(start, end, num_list))

bisect_left(), bisect_right()

num_list = [-99, -2, -1, 4, 98, 98]
idx = bisect.bisect_left(num_list, 98) # 4
idx = bisect.bisect_right(num_list, 98) # 6

이분탐색시, 한 요소를 고정하고 나머지 한 요소가 있는 인덱스를 찾을때 사용한 모듈

Circular Queue

Dequeue 시 front가 위치한 인덱스의 아이템을 빼는 것은 이해가 가는데
이걸 코드화 시키는 것이 아직 어렵다.

공부하면서 아쉬운 점

나는 모듈로 딸깍해서 풀었는데, 하나하나 함수로 구현하신 분들을 보면
내일부턴 최대한 직접 구현하는 방향으로 풀어야할 것 같다.
물론 가장 최적의 방법을 적용하는 것은 맞지만,
지금 단계에선 직접 구현해서 푸는 것이 얻는 것이 더 많을 듯 싶다.