Notion에서 작성한 글이라, 여기 에서 더 깔끔하게 보실 수 있습니다! 😮😊

---

[Beginner] 같은 숫자는 싫어

[같은 숫자는 싫어]

2기 3일차에 풀었던 문제로, Queue 문제이다.

당시에는 Queue가 FIFO다~ 정도만 알았지, 문제의 흐름에서 자연스럽게 Queue가 보이지도 않았고, Queue를 사용한 이유를 설명하라면 아마 버벅거렸을 것이다.

하지만 이제 여러 가지 방법들이 보인다! 😮😊

Solution 1. Queue $O(n)$

def solution(arr):
    queue = []
    for n in arr:
        if queue[-1:] != [n]:
            queue.append(n)
    
    return queue

• 여기에서, queue[-1] == n이 아닌 queue[-1:]로 슬라이싱을 사용한 이유는, 반복문에 처음 진입할 땐 queue가 비어 있는 상태이기 때문에 [-1]로 접근할 경우 IndexError가 발생하기 때문이다. 슬라이싱을 사용하면 유효한 인덱스에 대해서만 슬라이싱하기 때문에 IndexError가 발생하지 않는다.
  • 이 때 주의해야 할 점은, 슬라이싱은 리스트를 반환하기 때문에 비교 대상도 리스트로 묶어주어야 한다.
• 다른 방법으로는, 배열 arr의 크기가 자연수이므로 항상 queue에는 arr[0]이 push됨이 보장되기 때문에 미리 queue에 첫 번째 원소를 넣어놓고 시작을 할 수도 있다.

Solution 2. Set / temp $O(n)$

def solution(arr):
    a_set = set()
    answer = []
    
    for n in arr:
        if n not in a_set:
            a_set = set(n)
            answer.append(n)
    
    return answer

• 앞에서 이미 answer에 추가되었지만, 뒤에서 한 번 더 들어오는 경우를 처리하기 위해 새로운 n이 들어올 때마다 set을 초기화시켜준다. 집합을 이용하여 $O(1)$만에 연속적으로 나타난 숫자인지 아닌지 판별할 수 있다.
• 여기서, 굳이 set을 써야할까라는 생각을 해볼 수 있다. 어차피 위 코드에서 set은 항상(맨 처음 초기화할 때를 제외하고) 하나의 원소만을 갖는다. 이는 정수형 변수로도 $O(1)$만에 비교가 가능하기 때문에, 굳이 set을 쓸 이유도 없다.

  def solution(arr):
      temp = -1
      answer = []
      
      for n in arr:
          if n != temp:
              temp = n
              answer.append(n)
      
      return answer

Solution 3. itertools.groupby $O(n)$

from itertools import groupby
def solution(arr):
	return [key for key, group in groupby(arr)]

• 2기때 메모해놨던 내용이다.

---

[Middler] 하노이의 탑

[하노이의 탑]

BOJ 11729. 하노이 탑 이동 순서 과 동일한 재귀 문제이다.

점화식 도출 과정과 DP를 이용한 최적화까지 설명하고 싶은데 어제 시험도 보고 백준도 풀다보니 밤을 새서… 내일 이어서 작성하겠다 😢

Solution 1. Recursion $O(2^n)$

def f(n, s, d):
    if n == 1: return [[s, d]]
    return f(n-1, s, 6-(s+d)) + [[s, d]] + f(n-1, 6-(s+d), d)

def solution(n):
    return f(n, 1, 3)

Solution 2. Memoization + Recursion $O(2^n)$

memo = {}
def f(n, s, d):
    if n == 1: return [[s, d]]
    if (n, s) in memo: return memo[(n, s)]
    memo[(n, s)] = f(n-1, s, 6-(s+d)) + [[s, d]] + f(n-1, 6-(s+d), d)
    return memo[(n, s)]

def solution(n):
    return f(n, 1, 3)

• 시간복잡도가 확실히 엄청나게 커팅되는데 정확히 계산을 못하겠다,,, 내일은 요걸 좀 알아봐야겠다!

---

[Challenger] 과제 진행하기

[과제 진행하기]

• 문제 설명대로 차근차근 구현해나가면 되는 문제이다. Solution은,,, 너무너무 졸려서,,, 😢

---