[CS기초] 4주차 개념 정리

CSAPP

[CSAPP 3장 완전정복] 시리즈 참고 (링크: 3.1절 핵심 정리)

https://just-live.tistory.com/entry/CSAPP-3%EC%9E%A5-%EC%99%84%EC%A0%84-%EC%A0%95%EB%B3%B5-31-%EC%96%B4%EC%85%88%EB%B8%94%EB%A6%AC-%EC%96%B8%EC%96%B4%EC%99%80-%EC%B9%9C%ED%95%B4%EC%A7%80%EB%8A%94-%EC%B2%AB-%EA%B1%B8%EC%9D%8C

[CSAPP 3장 완전 정복] 3.1 어셈블리 언어와 친해지는 첫 걸음

 

 

키워드

■ 그리디 알고리즘
그리디 알고리즘: 현재 상황에서 가장 좋아 보이는 선택을 반복해 답을 구하는 알고리즘
단, 항상 최적해를 보장하지는 않으며, 각 단계에서의 선택이 전체 최적해의 일부가 되어야 정확한 결과를 얻을 수 있다.

■ 다이나믹 프로그래밍(DP)
중복되는 계산을 줄여 효율적으로 문제를 해결하는 알고리즘. 흔히 똑똑한 재귀라고도 불린다.
연산에 이미 계산한 결과(하위 문제의 해)가 필요하다면 다시 계산하지 않고 DP 테이블에서 바로 가져와 활용한다.

■ LCS (최장 공통 부분 수열)
두 수열이 주어졌을 때, 순서를 유지하면서 공통적으로 나타나는 가장 긴 부분 수열을 찾는 문제.
이때, 요소들이 연속해서 등장할 필요가 없고, 중간에 다른 값이 있어도 순서만 맞는다면 공통 수열로 인정된다.
▶ DP 점화식
if A[i] == B[j]:
	dp[i][j] = dp[i-1][j-1] + 1
else:
	dp[i][j] = max(dp[i-1][j], dp[i][j-1])
	
■ Knapsack Problem (배낭 문제)
각 물건이 무게(weight)와 가치(value)를 가지고 있을 때, 최대 무게 제한이 있는 배낭에 물건들을 선택적으로 담아,
총 가치를 최대로 만드는 물건의 조합을 찾는 문제
▶ DP 점화식
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

■ Linked List (연결 리스트)
각 데이터가 메모리 상의 불연속적인 위치에 저장되며, 다른 데이터(노드)의 위치 정보를 함께 저장하는 자료구조

■ 포인터(pointer), & 연산자와 * 연산자
포인터: 메모리 주소를 저장하는 변수
& 연산자: 변수의 주소를 얻는 연산자
* 연산자: 포인터가 가리키는 주소에 접근하는 연산자