✍️오늘 공부한 내용

• 어제에 이어서 자료구조(큐) 관련 문제들을 풀었다.
  • 문제 (풀이는 추후정리해 올릴 예정)
    • 큐
      • [2164] 큐2
      • [11866] 요세푸스 문제
    • 분할 정복
      • [2630] 색종이 만들기

📋새로 배우게 된 내용

• 큐 순환하는 방법으로 deque의 rotate()에 대해 배우게 되었다. 인자가 없으면 default로 1씩 양의 방향으로 순회하며, 음수 인자가 주어지면 음의 방향으로 순회한다.

from collections import deque
dq.rotate(-(K-1)) #K-1만큼 거꾸로 리스트를 순환한다.

🤯어려웠던 점

1. 2146번 큐 문제에서 시간초과가 또 일어났다. 저번에 처음 시간초과가 있었을 때는 왜 발생한 건지 잘 몰랐는데, 이번에는 바로 눈치챘다! 해결책은 아래 해결방법에서👇
2. 2630번 분할 정복 문제를 풀고 있는 중이다. 아직 문제 해결중인데, 오류 부분은 찾은 거 같다. 분할할 때 해당 범위를 기준으로 재귀가 돌아야하는데 처음 분할 했던 곳에서 다시 돌고 있다. 이 부분 코드 수정을 해봐야겠다.

😸어려움을 해결한 방법

1. 찾아보니까 deque 컬렉션을 import해서 rotate()를 쓰면 된다.

• list로 큐를 구현하면 일반 array이기 때문에 pop()을 하게 되면 n만큼 리스트를 앞당겨줘야해서 O(n)이 되어버린다.
• 따라서 큐를 deque로 import해서 구현하기

🤔아쉬웠던 점

• deque를 import해 오는 건 큐 구조를 직접 구현하자는 취지에서 좀 벗어난 느낌이다.살짝 치팅 아닌가

😝느낀점

• 분할 정복 문제에 다시 재귀가 나왔다! 재귀를 단순히 자기를 호출하는 함수라고 개념을 잡았었는데, 함수를 구성할 때 몇가지를 나누어서 생각해보니 좀 더 풀기 쉬워진 것 같다.
  1. basecase 조건 설정에 대한 고민
  2. basecase로 점점 가까워지게 설계하기
  3. 2를 하기 위해 규칙성 발견하기
  4. 2를 위한 인자가 어떤게 있어야할 지 고민하지 (변하고 다음 case에 넘겨줘야할 값이 뭔지)

👊다짐

• deque를 사용해보지 않고 구현방법을 고민해보자.

🚀오늘의 한줄평

• 재귀도 나름 분할하면 정복 가능할 듯!