크래프톤 정글 WEEK3

 

회고

오늘은 3주차 마지막 수요일이다. 내일 시험 보면 또 조가 바뀌고 새로운 발제가 시작된다.

다음주부터는 c언어랑 R-B트리 등 등 배운다는데 벌써부터 어려울 것 같다..
이번 3주차를 요약하자면 2주차 시험을 탈탈 털려버린 것과 코치님과 커피챗을 하게 됐는데 나의 문제점을 정확히 짚어주셔서 팩팩폭을 맞아버린 것이 가장 큰 것 같다.
나의 큰 문제는 
정확성이 없는 것과 시간 분배를 못하는 것, 
내 것으로 만들지 못한다는 것? 
끝까지 가지 않고 하다가 만다는 것.. 더 열심히 해야되겠다..

 

공부 키워드
그리디 알고리즘(탐욕법, Greedy Algorithm), 다이나믹 프로그래밍(동적 프로그래밍), Knapsack Problem, LCS, 분할정복, 연결리스트(Linked List), 포인터

CSAPP
3장 전체
-> 3-4, 3-7, 3-8, 3-9, 3-10장 정독

 

 

DP 알고리즘은 점화식만 찾으면 다 풀리는 문제인데, 그 점화식을 찾는게 힘들어서 잘 풀지 못하였다.

풀이를 봐도 이해가 안가는 점화식이 있는 반면, 이걸 왜 생각 못 했지? 하는 부분도 있었다.

정글 동료분이 말씀해주실 교수님께서 코테에 DP 문제가 나오면 과감하게 버려라 ..라고 했다고.. 그 정도로 너무 어렵다.

그래도 그리디 알고리즘은 좀 풀만(?)한 건 아니고 사실 아직도 잘 못하지만 그래도 뭔가 접근 방식이 좀 보인다고 해야되나 근데 DP는 진짜 아무것도 안 보여서 너무 막막하다

 

퀴즈에 스택과 레지스터 용도, 장점 설명, 그리고 꼬리 재귀최적화가 무엇인지에 묻는 질문에 제대로 된 답을 쓰지 못하였다. 특히 꼬리 재귀는 진짜 처음 들어서 퀴즈 끝나고 바로 찾아서 공부하였다.

 

다른 키워드와 CSAPP는 카테고리에 정리해두었으니 퀴즈 정리를 해봤다.

---

1. 스택과 레지스터가 어떤 것인지 설명하고, 용도와 장점을 설명

 

스택은 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간이다.

선언되는 순서와 반대로 메모리가 해제되는 LIFO(Last In First Out) 구조를 가지고 있다.

• 용도
  • 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다.
  • 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다.
• 장점
  • 동적으로 메모리를 할당하고 해제할 수 있다.
  • 구현이 간단하며, 메모리 관리 오버헤드가 낮다.

 

레지스터는 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다.

• 용도
  • 중간 연산 결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용
  • 빠른 데이터 접근 : 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용된다.
• 장점
  • 매우 높은 데이터 접근 속도를 제공한다.
  • 데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가한다.

 

2. 꼬리 재귀 최적화(Tail Recursion Optimization)를 호출 스택의 관점에서 설명

 

• 꼬리 재귀 최적화는 재귀 함수 호출 시 호출 스택의 사용을 최적화하는 기법이다.
• 재귀함수가 호출 될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 된다.
• 꼬리 재귀 최적화는 재귀함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거한다.
• 이를 통해 함수가 반환될 때 호출 스택을 재사용할 수 있다.
  • 꼬리 재귀함수는 반환값을 바로 return하기보다는 파라미터로 전달된다.
  • 이렇게 하면 호출 스택에 쌓이지 않고 후속 호출로 이동한다.
  • 함수 호출 후 더 이상 수행할 작업이 없는 경우, 이전 호출 스택 프레임을 재사용하므로 메모리 사용량이 일정하게 유지된다.

❓ 재귀(Recursion)

"자기 자신을 호출하는 함수"
함수가 한 번 호출될 때마다 입력값(매개변수), 결과값(리턴값), 그리고 리턴 후 돌아갈 위치등이 스택에 보관
→ 재귀 함수는 호출 시 마다 스택 공간에 뭔가를 저장하기 때문에, 무리하게 호출하면 ‘스택 오버플로우’가 발생!!

❓ 꼬리 재귀(Tail Recursion)

재귀 호출이 끝나면 "아무 일도 하지 않고 결과만 바로 반환" 되도록 하는 방법이다.
이전 함수의 상태를 유지하지도 않고 추가 연산을 하지도 않아서 스택 오버플로우 해결!

 

 

C언어로 factorial을 일반 재귀와 꼬리 재귀 최적화로 구현한 코드

//일반 재귀 구현
int factorial(int n){
	it (n==1){
		return 1;
	}
	return n*factorial(n-1);
}

 

일반 재귀는 값을 받으면, 그 값에 연산을 하고 다른 함수에게 전달, 리턴 후 돌아갈 위치 값이 저장되어야 함

꼬리 재귀는 아무것도 하지 않고 값을 전달, 리턴 후 돌아갈 위치값 저장할 필요 없음

//꼬리 재귀 최적화 구현
int factorialTail(int n, int acc){
	it (n==1){
		return acc;
	}
	return factorialTail(n-1,n*acc);
}

int factorial(int n){
	return factorialTail(n,1);
}

 

 

꼬리 재귀는 자신이 호출한 함수한테 받은 결과 값에 아무 일도 하지 않고 바로 반환하기 위해 꼬리에서 함수를 호출하는 방식이다!!!!!

 

 

3. 그리디 알고리즘과 동적 프로그래밍의 정의를 각각 쓰시고, 동적 프로그래밍에서 상향식, 하향식의 차이에 대해 설명해 보세요.

 

그리디 알고리즘

• 정의 :매 순간마다 가장 좋아보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대한다.
• 특징 : 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식이다. 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않는다.

동적 프로그래밍

• 정의 : 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘이다.
• 특징 : 중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높인다.
  • 상향식(Bottom-up) : 작은 문제부터 차례대로 해결해 나가면서 큰 문제의 해결책을 구한다.
  • 하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결한다. 필요할 때 하위 문제를 해결한다.
• 메모제이션 또는 타블레이션 기법을 사용

 

참고

https://joooing.tistory.com/entry/재귀-→-꼬리-재귀-Tail-Recursion