[04.04/week04]TIL

오늘 한줄 요약

somebody help me

새로 배우게 된 것

• CSAPP Team Study
• DP
• Greedy

CSAPP Team Study(~3.4)

가장 헷갈렸던 데이터 이동 명령어 부분을 확실히 집고 갈 수 있었음.

4. 데이터 이동 명령어

명령어	크기
movb	1 byte
movw	2 bytes
movl	4 bytes
movq	8 bytes

• mov는 단순 복사. 변환 없음
• 두 오퍼랜드 모두 메모리는 불가 (중간에 레지스터 거쳐야 함)
  

예:

movq (%rsi), %rax     ; 메모리 → 레지스터
movq %rax, (%rdi)     ; 레지스터 → 메모리

• movabsq
  • 64비트 상수값(imm) → 레지스터 로 이동시 사용하는 명령어

movz ⇒ 0 으로 확장하는 이동 인스트럭션(move with zero)

movz x0, #0x1234
# 0x0000000000001234

movs ⇒ F로 확장하는 이동 인스트럭션(move with sign)

• movslq는 있는데 movzlq는 없는 이유
  • x86-64에선 32비트 레지스터에 값을 쓰면 자동으로 상위 32비트를 0으로 클리어해주기 때문
  • movslq

    • F로 클리어하려면 필요함

      movslq %eax, %rdx
      # %eax = 0xFFFFFFFE (음수) → %rdx = 0xFFFFFFFFFFFFFFFE

  • movzlq

    movl %eax, %edx    # 하위 32비트 복사됨, 상위 32비트는 자동으로 0으로 클리어됨
    # 32비트 -> 64비트로 옮길경우 알아서 0 채움

그리고 데이터 이동 인스트럭션 자체가 성립하는지를 먼저 확인하고,
접미사와 크기가 맞는지 확인하고, 오퍼런드가 둘다 메모리가 아닌지 확인하는 과정을 통해서
이게 정당한 인스트럭션인지 확인해야한다.

DP

개념	설명
Memoization	필요한 순간에 계산해서 저장 (게으른 계산)
Tabulation	미리 계산해두고 바로 사용 (선 계산, 후 사용)
Top-Down	큰 문제부터 재귀로 내려가며 해결
Bottom-Up	작은 문제부터 반복적으로 해결

뭐 이렇게 정리는 했는데
Smart Recursion 이라는 말에 전적으로 동의한다.

결국 큰 문제를 작게 나누거나, 작은 문제를 합쳐서 큰 문제를 해결하는데
이때 중복 계산을 하지 않고 어디다가 기록해서 가져오는게 DP
이름을 잘못지었다.
차라리 Record 알고리즘이라고 지었으면 좋았을텐데
뭐가 다이나믹한지 하나도 모르겠다.

• vs 재귀

cut_rod(4)
├── cut_rod(3)
│   ├── cut_rod(2)
│   │   ├── cut_rod(1)
│   │   │   └── cut_rod(0)
│   │   └── cut_rod(0)
│   └── cut_rod(1)
│       └── cut_rod(0)
├── cut_rod(2)
│   ├── cut_rod(1)
│   │   └── cut_rod(0)
│   └── cut_rod(0)
├── cut_rod(1)
│   └── cut_rod(0)
└── cut_rod(0)


cut_rod(4)
├── cut_rod(3)
│   ├── cut_rod(2)
│   │   ├── cut_rod(1)
│   │   │   └── cut_rod(0)
│   │   └── [memo[1]]
│   └── [memo[2]]
├── [memo[3]]
├── [memo[2]]
└── [memo[1]]

막대 자르기 문제를 시각화 한건데
DP는 각 N에 대해 한번만 연산하고 기록해둔다.
그리고 또 똑같은 연산을 해야할 때 이를 가져오는 것.

• Memoizaion vs Tabulation

def fibo_top_down(n, memo=None):
    if memo is None:
        memo = [-1] * (n + 1)
    if n <= 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fibo_top_down(n - 1, memo) + fibo_top_down(n - 2, memo)
    return memo[n]


def fibo_bottom_up(n):
    if n == 0:
        return 0
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Top-Down의 메모이제이션은 재귀로 필요한 것만 계산하고,
Bottom-up의 테뷸레이션은 반복문으로 가장 작은 것 부터 다 계산해놓는 점에서 차이가 있다.

Greedy

그리디는 별게 없다.
그냥 주어진 상황에서 가장 좋은 것만 선택하면 된다.

단, 코테환경에서 그리디를 쓴다는 것은
좋은 것만 선택해도 최적해가 된다는 이야기.

따라서 정렬을 하고 이 정렬을 어떻게 해서 현재의 선택만 고려해도 최적의 선택이 될까를 고민해야 한다.

공부하다가 아쉬운 점

CSAPP을 GPT를 동원해서 잘 읽었다고 생각했는데 아니었고
연습문제 중심으로 봐야 이해가 된다는 걸 깨우쳤다...