[04.06/week04]TIL

오늘 한줄 요약

맨땅에 헤딩.

새로 배우게 된 것

• CSAPP 3.8 (배열의 할당과 접근)
• LCS
• KnapSack

CSAPP 3.8

✅ 3.8 배열의 할당과 접근 요약

1. 배열의 기본 원리

• C에서 T A[N]은 L*N 바이트의 연속된 공간 할당 (L = 자료형 T의 크기)
• A[i]의 주소는 Xa + L * i로 계산됨
• x86-64에서는 movl (%rdx, %rcx, 4), %eax 방식으로 E[i] 접근

2. 포인터 연산

• p + i는 Xp + L * i와 같음
• Expr[i]는 *(Expr + i)와 동일

3. 다중 배열 (2차원 배열)

• int A[5][3]은 행 우선 순서로 메모리 배치
• 원소 접근 주소: &A[i][j] = x_A + 4 * (3 * i + j)

4. 고정 크기 배열의 최적화

• A[i][j] 접근 시 매번 i * N + j 계산 필요
• 포인터로 접근 시 연속 메모리 접근 가능해 더 빠름

int *Aptr = &A[i][0];
int *Bptr = &B[0][k];
while (Bptr != Bend) {
    result += (*Aptr) * (*Bptr);
    Aptr++;
    Bptr += N;
}

• 수식: &D[i][j] = x_D + L * (C * i + j)

5. 가변 크기 배열

• int A[n][n]처럼 N이 런타임에 결정되는 배열
• 주소 계산: A + 4 * (n * i + j)
• 고정 배열: shift 사용 가능
• 가변 배열: 반드시 곱셈 명령어 imulq 필요

KnapSack Problem

N개의 물건과 M만큼의 무게를 버틸 수 있는 배낭이 존재,
각 물건마다 가치가 다를때 최대 가치의 합을 찾는 문제

본질은 물건을 배낭에 넣느냐 마느냐

이를 알고리즘 적으로 해석하면,
최대 M까지 담을 수 있는 배낭, K의 가치를 지는 물건 Nkg 을 가방에 넣는다면?
넣었다면 K의 가치와 (M - N) 까지 담을 수 있는 배낭이 됨.
만약 이를 넣지 않았다면 그대로 M Kg까지 담을 수 있는 배낭.

만약 6Kg 짜리 배낭이 있다면,
이때 $4의 가치를 갖는 3kg 물건을 넣는다면, 이제 3Kg 짜리 배낭을 채우면 된다.

즉 6Kg 배낭 최대 가치 = $4 + 3Kg 배낭 최대가치로
DP의 특징을 찍을 수 있다.

점화식을 뽑아보면,

물건 K 무게 > 베낭 무게 W:
	dp[K][W] = dp[K - 1][W]
물건 K 무게 <= 배낭 W 무게
	dp[K][W] = max(dp[K -1][W], K가치 + dp[K - 1][W- K의 무게]

이걸 코드로 만들면

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

items = []
for _ in range(N):
    W, V = map(int, input().split())
    items.append((W, V))

dp = [[0] * (K + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    weight, value = items[i - 1]  # 현재 물건의 무게와 가치
    for j in range(1, K + 1):  # 현재 배낭 무게
        if j < weight:
            dp[i][j] = dp[i - 1][j]  # 물건 못 넣음
        else:
            dp[i][j] = max(
                dp[i - 1][j],  # 안 넣은 경우
                dp[i - 1][j - weight] + value  # 넣은 경우
            )

print(dp[N][K])  # 최대 가치 출력

LCS(Longest Common SubString/Subsequence)

✅ 최장 공통 부분 문자열 (Substring)

개념

• LCS[i][j]는 str1[0~i-1]과 str2[0~j-1]의 연속된 공통 문자열의 길이
• str1[i-1] == str2[j-1]일 때만 갱신됨

점화식

if str1[i-1] == str2[j-1]:
    LCS[i][j] = LCS[i-1][j-1] + 1
else:
    LCS[i][j] = 0  # 연속되지 않으면 0으로 초기화

결과

• LCS[i][j] 중 최댓값이 가장 긴 공통 문자열의 길이
• 해당 시점의 i 저장 → str1[end_idx - max_len : end_idx]로 실제 문자열 추출 가능

---

✅ 최장 공통 부분 수열 (Subsequence)

개념

• 연속되지 않아도 순서만 지키면 됨
• LCS[i][j]는 str1[0~i-1], str2[0~j-1]의 최장 부분 수열의 길이

점화식

if str1[i-1] == str2[j-1]:
    LCS[i][j] = LCS[i-1][j-1] + 1
else:
    LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])

결과

• LCS[len(str1)][len(str2)]이 최장 부분 수열의 길이
• 실제 문자열을 구하려면 → DP 테이블을 역추적

역추적 방법

1. DP 테이블의 끝에서 시작
2. 현재 값이 LCS[i-1][j] 또는 LCS[i][j-1]와 같으면 해당 방향으로 이동
3. 그렇지 않으면 문자가 같다는 뜻 → 결과에 해당 문자 추가하고 대각선으로 이동 (i-1, j-1)
4. 결과는 역순(reverse) 처리

항목	Substring	Subsequence
연속성	O (연속 필수)	X (연속 아님)
불일치 시	0으로 초기화	max 값 유지
용도	특정 패턴 찾기	전체 흐름 속 일치 추적

공부하다가 아쉬운 점

이 문제가 DP로 해결가능한 문제인지 판단하는 것 부터가 어렵다.
많은 문제를 접해야 얻을 수있는 거라 최대한 많이 양치기 하기로...