[1주차] 알고리즘: Dynamic Programming, 배열

Q1. Dynamic Programming이란? 장점은?

• 메모리를 적절히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법
• 이미 계산된 결과는 별도의 메모리에 저장해서 다시 계산하지 않도록 함
• 일반적으로 2가지 방식으로 구성됨
  • Top Down (하향식)
    • Memoization : 한 번 계산한 결과 메모리 공간에 메모 (== caching)
  • Bottom Up (상향식)
• 특정 문제가 다음의 조건 만족할 때 사용 가능
  • 최적 부분 구조 (Optimal Substructure)
    • 큰 문제를 작은 문제로 나눌 수 있음
    • 작은 문제의 답을 모아서 큰 문제 해결할 수 있음
  • 중복되는 부분 문제 (Overlapping Subproblem)
    • 동일한 작은 문제를 반복적으로 해결해야 함

장점

• 하나의 문제를 단 한번만 풀기 때문에 효율적

ex) 피보나치 수열

점화식 : D[i] = D[i-1] + D[i-2]

→ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

재귀 함수로 푸는 경우

# 시간 복잡도 : O(2^N)
**def fibo(x):
  if x == 1 or x == 2:
    return 1
  return fibo(x - 1) + fibo(x - 2) 

print(fibo(4))**

다이나믹 프로그래밍

# top down
# 10부터 재귀함수 
d = [0] * 11     # list for memoization

def fibo(x):
  if x == 1 or x == 2:
      return 1
  
  # 이미 계산한 적 있는 문제면 그대로 반환
  if d[x] != 0:
      return d[x]

  # 아직 계산하지 않은 문제면 피보나치 결과 반환 
  d[x] = fibo(x - 1) + fibo(x - 2)
  return d[x]

print(fibo(10))

# bottom up 
# 1부터 차례대로
d = [0] * 11

d[1] = 1
d[2] = 1
n  = 10

# 피보나치 함수의 반복문으로 구현 
for i in range(3, n+1):
  d[i] = d[i-1] + d[i-2] 

print(d[n])

참고자료 : https://blog.naver.com/ndb796/221233570962

Q2. 배열 nums에 [0, n]범위의 n개의 양의 정수가 담겨있습니다. [0, n]범위 수 중에서 배열에 빠져있는 수 하나를 반환하는 가장 효율적인 알고리즘을 작성하세요.

✅ 공간복잡도 및 시간복잡도

• 공간복잡도: 알고리즘 수행에 필요한 메모리 양을 평가
  • 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수
  • 가변 공간 (알고리즘 실행과 관련있는 공간): 실행 중 동적으로 필요한 공간
  • S(P) = c + Sp(n)
    • c : 고정 공간
    • 𝑆(𝑝), 𝑆𝑝(𝑛) : 가변 공간
• 시간복잡도: 알고리즘의 성능을 평가
  • 최상의 경우(Best Case) : 오메가 표기법 (Big-Ω Notation)
  • 평균의 경우(Average Case) : 세타 표기법 (Big-θ Notation)
  • 최악의 경우(Worst Case) : 빅오 표기법 (Big-O Notation)
  💙 정렬 및 자료구조 시간복잡도

1. Hashset 사용하기

   from collections import defaultdict
   
   n = 10
   arr = [1, 6, 4, 3, 5, 2, 8, 9]
   lst = defaultdict(int)
   
   for i in arr:
   	lst[i] = 1
   
   for i in range(n):
   	if lst[i] == 0:
   		print(i)​

    
   1. 시간복잡도: O(n)
      • Hashset 삽입/탐색/삭제 단계: 시간복잡도 O(1)
      • $\because$ Hash를 사용하면 Hash function을 한 번만 수행하면 되므로
      • Hash function 시간복잡도: O(n)
      • → Hash 함수를 잘못 설정했거나, 버킷이 충분하지 않을 경우
   2. 공간복잡도: O(n)
2. from collections import defaultdict n = 10 arr = [1, 6, 4, 3, 5, 2, 8, 9] lst = defaultdict(int) for i in arr: lst[i] = 1 for i in range(n): if lst[i] == 0: print(i)
3. 배열 내 원소의 합 이용하기
   • (누락된 수) = (n까지의 합) - (배열 내 원소의 합)
   • 0~n까지 양의 정수의 합:
    
   1. 시간복잡도: O(n)
   2. 공간복잡도: O(1)

n = 9
arr = [0, 1, 6, 4, 3, 5, 2, 8, 9]
tmp = (n * (n+1)) // 2
sumTmp = 0

for i in arr:  # 반복문 호출: n + 1
	sumTmp += i  # 덧셈: n

print(tmp - sumTmp)

Q3. 배열의 숫자를 활용해서 만들 수 있는 가장 큰 숫자를 반환하세요.

가장 큰 숫자를 반환해야 하지만, 정렬 기준이 기존과는 다르므로, 이미 구현되어있는 정렬 메서드로는 불가능함

data = list(map(int,input().split(',')))
ans = data[0]
data.pop(0)

def maxNumber(a, b):
    a = str(a)
    b = str(b)
    if int(a+b) < int(b+a):
        return int(b+a)
    else:
        return int(a+b)

for i in data:
    ans = maxNumber(ans, i)

print(ans)

파이썬 정렬

• 파이썬에는 리스트객체의 메서드 sort()가 존재 (리스트에서만 사용 가능)내림차순으로 정렬하고 싶다면 .list(reverse=True)
• → 기본적으로 오름차순으로 정렬한다. (기본값 reverse=False)
• 종류
  • sort(): 해당 리스트 자체를 정렬
  • sorted(): 해당 리스트는 변하지 않고, 새롭게 정렬된 리스트를 반환
• 반환결과
  • 숫자리스트: 음수→양수까지 숫자 크기대로 정렬
  
  • 대소문자: 대문자→소문자 순서

• 파이썬의 정렬은 팀 피터스(Tim Peters)가 만든 알고리즘이며, 병합정렬 + 삽입정렬을 적당히 섞어 만들었다고 함
• 시간복잡도 O(NlogN)
• key를 이용해 새로운 기준으로 정렬 가능

  class Solution:
      def largestNumber(self, nums):
          class Predicate(str):
              def __lt__(self, other):
                  return self + other < other + self
  
          res = ''.join(sorted(map(str, nums), key=Predicate, reverse=True))
          return '0' if res[0] == '0' else res​

• key에 함수를 넣으면 그의 반환값에 맞게 정렬된다.