2025.04.08
TIL(TODAY I LEARN)
-
WEEK04 :
동적 프로그래밍, 그리디 알고리즘
CSAPP 3장. 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8) -
오늘은 퀴즈를 쳤다. 나름 끄적거렸다.
4주차 퀴즈
1. 스택과 레지스터가 어떤 것인지 설명하고, 용도와 장점을 설명하세요.
- 스택(stack)은 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간입니다.
- 선언되는 순서와 반대로 메모리가 해제되는 LIFO(Last In First Out) 구조를 가지고 있습니다.
- 용도:
함수의 로컬 변수 저장: 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장됩니다.
함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장됩니다.- 장점:
동적으로 메모리를 할당하고 해제할 수 있습니다.
구현이 간단하며, 메모리 관리 overhead가 낮습니다.
- 레지스터(register)는 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는
변수나 중간 계산값을 저장하기 위해 사용됩니다.- 용도:
중간 연산 결과의 저장: 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용됩니다.
빠른 데이터 접근: 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용됩니다.- 장점:
매우 높은 데이터 접근 속도를 제공합니다.
데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가합니다.
1번 퀴즈였는데 알고있다고 생각했다.
제대로 알고있지 않은 것 같다.
다시 정리를 제대로 해두자.
3. 그리디 알고리즘과 동적 프로그래밍의 정의를 각각 쓰세요.
그리디 알고리즘 (Greedy Algorithm)
- 정의: 매 순간마다 가장 좋아 보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대합니다.
- 특징: 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식입니다. 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않습니다.
동적 프로그래밍 (Dynamic Programming)
- 정의: 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘입니다.
- 특징: 중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높입니다.
메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 기법을 사용합니다.
| 용어 | 정의 | 방식 | 대표 사용 |
|---|---|---|---|
| 메모이제이션 (Memoization) | 이미 계산한 값을 저장해서, 같은 문제 다시 풀지 않기 | Top-down (재귀) | 피보나치, 백트래킹+DP |
| 태뷸레이션 (Tabulation) | 작은 문제부터 테이블에 차례로 채워서 전체 문제 해결 | Bottom-up (반복문) | 대부분의 DP 문제 |
퀴즈 중 일부를 가져와 봤다. 개념 정립이 필요할 것 같다. 좀 애매하게 알고 있는 듯?
더욱 정진하자.
오늘의 백준 풀이
1700 - 멀티탭 스케줄링 - 골드1
문제 링크 - https://www.acmicpc.net/problem/1700
내 코드
import sys
from collections import deque
input = sys.stdin.readline
n,k = map(int,input().split())
elec = deque(map(int,input().split()))
se = set()
cnt = 0
while elec:
x = elec.popleft()
if len(se) < n: #자리 있음 꽂아
se.add(x)
continue
if x in se: # 이미 꽂혀있음 pass
continue
# 다 등장하면 마지막애 뽑고, 다 등장 안하면 안한애 뽑고
check = -1
target = 0
for plugged in se:
if plugged in elec:
idx = elec.index(plugged)
else:
idx = float('inf') # 앞으로 안나옴
if idx > check: # 더 먼 친구가 있으면 idx 갱신
check = idx
target = plugged
se.discard(target)
cnt +=1
se.add(x)
print(cnt)
문제 분류
주석과도 같이 3가지 경우를 생각해야 했다
- 빈 자리가 있을 때 - 그냥 꽂는다
- 자리가 꽉 차있을 때
1 - 이미 꽂혀있다 - pass
2 - 플러그에 꽂혀있는 전자제품들이 뒤의 배열에서 등장하면 가장 멀리 있는 전자제품의 플러그를 뽑고,
뒤 배열에서 존재하지 않으면 등장하지 않는 전자제품의 플러그를 뽑는다.
2-2 의 아이디어를 떠올리고 구현하는게 이 문제의 키포인트라고 생각한다.
너무 어렵다!
계속해서 알고리즘 문제 푸는중!
DP는 감이 안온다! 어렵다!
^_^