(5/18) Leetcode - 알고리즘 면접 준비

Introduction

알고리즘 면접 준비를 하게 되면서 풀게 된 문제를 정리한다.

우선은 쉬운 문제들 부터 시작하는데 문제를 푸는 것만이 중요한게 아니라 논리적으로 납득할 만한 설명과 시간복잡도, 공간복잡도를 설명하는 것이 중요하다는 점을 배우게 됐다.

70. Climbing Stairs

Link: https://leetcode.com/problems/climbing-stairs/

class Solution:
    memo = {}

    def climbStairs(self, n: int) -> int:
        if n < 0:
            return 0
        elif n == 0:
            return 1
        elif n not in self.memo:
            self.memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.memo[n]

Feedback

• 설명이 부족했음
• f(k) → k 스텝까지 갈 수 있는 방법의 수
  • k 스텝까지 갈 수 있는 2가지 방법이 있다.
    1. k-1 칸까지 간 다음에 한 칸 점프
    2. k-2 칸까지 간 다음에 두 칸 점프
  • 이제 f(1)을 구하기만 하면 거기서부터 재귀적으로 f(k-1) 또는 f(k-2)까지 구할 수 있게 된다.

Description

• memoization을 사용하지 않는다면
  • 시간복잡도는 O(2^n)
    • 함수 두 개를 n번씩 반복해서 들어가기 때문에
  • 공간복잡도는 O(n)
    • 함수 콜스택 만큼 쌓인다.
• memoization을 사용하면
  • 시간복잡도는 O(n)
    • 이미 연산한 결과에 대해서는 연산하지 않기 때문에 O(n)
  • 공간복잡도는 O(n)
    • 함수 콜스택과 메모의 공간만큼 쌓이므로 O(2n) -> O(n)

338. Counting Bits

Link: https://leetcode.com/problems/counting-bits/

class Solution:
    memo = {}

    def helper(self, k: int) -> int:
        if k == 0:
            return 0
        elif k not in self.memo:
            self.memo[k] = self.helper(k >> 1) + (k & 1)
        return self.memo[k]

    def countBits(self, n: int) -> List[int]:
        answer = []
        for k in range(n+1):
            answer.append(self.helper(k))
        return answer

Description

• 시간복잡도는 O(n)
  • O(1)까지 내려가서 연산해 가져오는데, 결과 값이 이미 있는 경우 memo에서 가져오기 때문에 불필요한 중복과정은 제거되므로 O(n)
• 공간복잡도는 O(n)
  • 함수 콜스택과 메모의 공간만큼 쌓이므로 O(2n) -> O(n)