정글 7기 27, 28일차 / CS:APP 3장, 3주차 쪽지 시험, 배낭 문제 (알고리즘)

🐸  9월 30 일 / 27일차

이날은 오전,오후는 하루종일 배낭 문제를 풀었고  저녁을 먹고나서CS:APP을 공부하였다.

확실히 주말에 공부를 안하니 할게 정말 많이 밀린다... 

DP는 왠지 모르게 늘 새롭다 ㅠㅠ 

계속 문제를 많이 풀어서 익숙해져야한다. (반드시!!)

 

[Python][백준] 12865. 평범한 배낭 / DP, 배낭 문제 (G5)

 

3장-컴퓨터-시스템 ComputerSystems A Programmers Perspective

 

아직 컴퓨터 시스템을 블로그에 정리하지는 못했다...

(얼른 정리해서 업로드 할 예정 ㅠㅠ)

 

3장에서 특히 3.4를 집중적으로 보았고, 

인스트럭션들을 이해하려고 하였다. 

 

1. 오퍼랜드 형식

2. 데이터 이동 인스트럭션

3. 스택 데이터의 저장 및 추출

 

잘 이해했나를 확인 할 수 있는 가장 좋은 방법은 문제 푸는 것이라 생각한다.

그래서 해당 문제들을 열심히 풀었지만, 

생각보다 복잡하고 또 시간이 부족한데 너무 깊게 들어가는 느낌을 받았다.

 

내가 인스트럭션을 열심히 보려는 것은 사실 이거 자체가 특별한 경험이기 때문이다.

나중에 정글에서 pint os  같은 프로젝트를 할 때 유용하게 쓸 수도 있을거 같다.

 

하지만 시간이 부족하기 때문에 조금만 더 가볍게 책을 읽어야 될 것 같다.

 

🐸  10월 1일 / 28일차

 

오늘 아침에 출근부를 찍으면서, 나의 출석부를 보았다. 

어느덧 30일 정도가 지났고, 약 110일 정도 남았다.

아직 쌓은게 없는데 벌써 이렇게 시간이 지나간게 낯설다.

 

정글이 편하면 안되는데, 나는 너무 편하게 지내는 것 같다.

요즘들어 가장 무서운 것은 정글 수료 후에도 전과 같은 상황을 마주하는 것이다. 

나름 공부를 하려고 하루종일 교육관에 있지만, 나는 지금 열심히 하고 있는 걸까 ? 

 

10월1일 화요일은 쪽지 시험은 보는 날이다. 

 

아침에 간단하게 LCS 알고리즘을 풀고,

CS:APP 3.4장의 문제들을  조금 더 공부를 했다. 

책의 문제를 풀어보니 어느 정도 개념이 잡혀서 좋았다. 

(이거를 블로그에 써야하는데, 어떻게 해야할지 ... 막막하다.)

 

그리고 오후 2시에 쪽지 시험을 보았다. 

오늘의 포스팅은 쪽지 시험 위주로 작성한다. 

---

 

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

 

[내 풀이]
스택은 가상 메모리 속 공간으로 동적으로 늘거나 줄어든다.
주로 지역변수, 함수들이 들어가는 공간이다. 
레지스터 같은 경우 보통 CPU 내부에 존재하고, 다양한 종류의 레지스터가 있다. 
메인 메모리에서 레지스터로 적재되고, 제어 장치에서 해당 연산을 처리한다.

 

→ 스택은 가상 메모리가 아닌 RAM의 특정 영역에서 관리된다. 또한, 스택은 동적으로 늘거나 줄지만, 이는 함수 호출 시 자동으로 이뤄지는 방식으로 동적 메모리 할당이라고 하지 않는다. 

 

→ 메모리의 데이터를 메인 메모리에서 레지스터로 바로 가져오는 것이 아니라, CPU가 명령을 실행할 때 필요한 데이터와 명령으로 바르게 접근하기 위해 사용된다.

 

[정답]

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

1. 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다.
2. 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다.
3. 자동으로 메모리를 관리하고 해제하고 구현이 간단하다.

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

1. 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용 
2. 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용
3. 매우 높은 데이터 접근 속도 제공

 

---

2. 꼬리 재귀 최적화 (Tail Recursion Optimization)을 호출 스택(Call stack)의 관점에서 설명하세요.

 

[정답]
Tail Recursion Optimization은 재귀 함수 호출 시 호출 스택의 사용을 최적화하는 기법이다. 
재귀 함수가 호출될 때마다 스택 프레임이 생성되는데, 이는 메모리 사용량을 증가시키고 스택의 오버플로우의 원인이 된다. Tail Recursion Optimization는 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거한다. 이렇게 할 경우 반환될 떄 호출 스택을 재사용 할 수 있다. 

 

def factorial(n, accumulator=1):
    if n == 0:
        return accumulator
    else:
        return factorial(n - 1, n * accumulator)

 

위와 같은 경우 factorial(n - 1, n * accumulator)가 호출된 후에

더 이상 다른 연산이 필요하지 않아 Tail Recursion Optimization가 적용된다.

 

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

 

위의 코드 같은 경우 재귀 호출 후에도 n * 이라는 추가 연산이 필요하기 때문에 꼬리 재귀가 아니다. 

이 경우 기존 스택 프레임을 보존해야한다.

 

나는 이 문제에 대해 풀지 못했다 ... 

 

---

 

3. 단어 "DATABASE" 와 "ALPHABET" 의 LCS (LongestCommonSubsequence, 최장공통부분수열) 를 구하고, 풀이를 위해 생성되는 행렬과 탐색경로를 함께 기록하세요.

 

[내 풀이]

 

 

[정답]

나는 탐색 경로를 그리지 못했다. 

탐색 경로에서 대각선이 되는 방향을 리스트에 저장하면,

공통 부분 수열을 구할 수 있다. 

 

---

 

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

[내 풀이]
Greedy 알고리즘은 DP 알고리즘에 포함되는데 특수한 상황일때 사용이 가능하다. 해당 방식은 그 순간 가장 최선의 선택을 하지만, 이것이 최고의 결과를 낳는 것은 아니다. 특정 수열이 부분 수열을 포함 할 때는 Greedy 알고리즘 사용시 최고의 결과를 만들어 낸다. DP 알고리즘은 메모리제이션으로 중복되는 연산을 막아주어 효율성을 높여준다. 즉, 기전 연산 값에서 중복되는 부분을 현재 연산에서 이전 연산자 값의 참고로 연산량을 아껴준다,

 

→ Greedy 알고리즘은 DP 알고리즘의 하위 개념이 아니다. 

 

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

DP : 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘이다. 중복된 하위 문제들을 여러 번 해결하는 것을 메모이제이션 또는 테뷸레이션 기법으로 방지하여 효율성을 높힌다. 

상향식(Bottom -Up) : 작은 문제부터 차례대로 해결해 나가면서 큰 문제의 해결책을 구한다.
하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결한다.

 

---

5. Floyd-warshall 알고리즘을 사용해 방향 그래프의 이행적 폐쇄를 구하는 과정을 단계별로 도시하세요.

 

이행적 폐쇄 (Transitive Closure) :
그래프 이론에서 사용되는 개념으로, 그래프의 모든 정점 쌍에 대해 직접적인 경로가 없더라도 간접적으로 도달할 수 있는지를 나타낸다. 보통 두 정점 사이에 경로가 있는지를 빠르게 확인 할 수 있어 그래프의 연결성을 파악하고, 그래프가 강하게 연결 되어 있는지 확인 가능하다. 

 

ex)

A -> B -> C

 

이런 경우  A -> C로 가는 직접적인 간선을 추가하여 표시한다. 

 

(내가 생각했을떄 이행적 폐쇄는 간단하게 A와 C 정점이 직접적으로 연결되어 있지 않아도, 다른 정점에 의해 연결되면 연결 된다고 가정하는 것 같다.)

 

 

 

해당 풀이는 자세하지 않아 따로 찾아서 추가했다.