오늘 배운 것들

1. 동적계획법(다이나믹 프로그래밍, DP)

복잡한 문제를 단순한 작은 문제로 나누어 해결하는 알고리즘 설계 기법
이 때 작은 문제들을 중복 계산하는 것을 피하는 것이 핵심이다.
'기억하며 풀기'

1-1. 사용 조건

1. Optimal Substructure(최적 부분 구조)
   작은 문제의 최적 해로부터 큰 문제의 최적 해를 결정할 수 있어야 한다.
2. Overlapping Subproblems(중복 부분 문제)
   작은 문제가 큰 문제와 같은 구조를 가져야 한다.

예시: 피보나치 수열($f(n)=f(n-2)+f(n-1)$),
하노이 탑($f(n)=f(n-1)+f(1)+f(n-1)$)

1-2. 접근 방법

1. 하향식 접근(Top-down approach, 메모이제이션)
   문제를 분할하면서 해결하는 것.
   부분 문제의 해답을 저장해두고 필요할 때 저장된 값을 재사용한다.
   주로 재귀적으로 구현한다.
2. 상향식 접근(Bottom-up approach, 태뷸레이션)
   부분 문제부터 시작하여 차례대로 큰 문제로 나아가는 것.
   반복문을 사용하여 구현한다.

1-2-1. 하향식 접근 예시

cache = {0: 0, 1: 1}
def fibo(n: int) -> int:
    if n not in cache:
        cache[n] = fibo(n-1)+fibo(n-2)
    return cache[n]

큰 문제 fibo(n)부터 작은 문제 fibo(n-1), fibo(n-2)로 분할하며 해결해간다.
fibo(n-1)을 계산할 때는 fibo(n-2), fibo(n-3)을 계산하기 때문에 중복 계산이 발생한다.
그러므로 fibo(n-2)를 해결하면 cache에 저장하여 중복 계산을 피한다.

1-2-2. 상향식 접근 예시

def fibo2(n: int) -> int:
    table = [0, 1]
    for i in range(n):
        table[i%2] = sum(table)
    return table[(i+1)%2]

가장 작은 부분문제인 fibo(1)부터 계산을 시작한다.
차례대로 n까지 계산하여 문제를 해결한다.
이미 계산한 문제를 사용하여 다음 큰 문제를 사용하므로 중복 계산이 발생하지 않는다.

1-3. 분할 정복과의 차이

작은 문제로 나누어 해결한다는 점에서 분할 정복과 같은 개념이 아닌가 생각이 들었다.

분할 정복에서는 하위문제들이 서로 독립적이다.
예를 들어 병합 정렬같은 경우 부분문제를 독립적으로 해결한 후 결합하여 전체 문제를 해결한다.
동적 계획법에서는 하위문제들이 반복적으로 나오기도 하고 포함관계를 가지기도 한다. 따라서 메모이제이션 등을 이용하여 중복계산을 피한다.

2. 클린코드

좋은 글을 발견하여 읽어보았다.
정리하기에는 시간이 부족해 보편적인 이름 짓기 부분만 가져와봤다.
보편적인 이름 사용하기

• 함수:
  create~(), add~(), push~(), insert~()
  parse~(), make~(), build~(), split~()
  query~(), mutation~(), fetch~(), update~(), delete~()
  save~(), put~(), send~(), dispatch~(), receive~()
  validate~(), calc~(), serialize~()
  init~(), configure~(), start~(), stop~()
  generate~(), transform~(), log~()

• 변수나 속성:
  count~, sum~, num~
  is~, has~
  ~ing, ~ed
  min~, max~, total
  ~name, ~title, ~desc, ~data
  item, temp
  ~at, ~date, ~index
  selected~, current~
  ~s (복수형)
  ~type, ~code, ~ID, ~text
  params, error

여기에 비슷한 이름들의 정확한 뉘앙스를 파악하고 사용하는 것도 중요하다.