[중간정리] 4주차 - 스택과 레지스터, LCS, 그리디와 DP, 피보나치, 방향 그래프의 이행적 폐쇄

스택과 레지스터

스택(Stack)

정의

프로시저 호출 시 지역 변수와 매개 변수를 저장하기 위한 메모리 공간. 선언되는 순서와 반대로 메모리가 해제되는 LIFO(Last In First Out) 구조를 가지고 있다.

용도

• 함수의 로컬 변수 저장: 각 함수 호출 시 그 함수의 지역 변수들을 저장
• 함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보를 저장

장점

• 동적으로 메모리를 할당/해제할 수 있다.
• 구현이 간단하며, 메모리 관리 오버헤드가 낮다.

레지스터(Register)

정의

프로세서 내부에서 데이터를 저장하는 초고속 저장장치. 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용된다.

용도

• 중간 연산 결과의 저장: 연산 중 생성되는 중간 값을 빠르게 저장하고 접근
• 빠른 데이터 접근: 특정 데이터나 주소를 빠르게 저장하고 로드

장점

• 매우 높은 데이터 접근 속도를 가지고 있다.
• 데이터를 메모리에서 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가한다.

 

LCS(최장 공통 부분수열) 길이 구하기 및 경로추적

word1 = "DATABASE"
word2 = "ALPHABET"
n, m = len(word1), len(word2)

d = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if word1[i-1] == word2[j-1]:
            d[i][j] = d[i-1][j-1] + 1
        else:
            d[i][j] = max(d[i-1][j], d[i][j-1])

# print(d[n][m])    출력: 4

i, j = n, m
result = []
while i > 0 and j > 0:
    if word1[i-1] == word2[j-1]:
        result.append(word1[i-1])
        i -= 1
        j -= 1
    elif d[i-1][j] >= d[i][j-1]:
        i -= 1
    else:
        j -= 1

print(''.join(reversed(result)))    # AABE

 

 

그리디 알고리즘과 동적 프로그래밍

그리디 알고리즘 (Greedy Algorithm)

정의

매 순간마다 가장 좋아 보이는 선택을 하는 알고리즘.

특징

• 각 단계에서 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나간다.
• 각 단계에서의 결정은 지금까지의 상황을 고려하며, 이후의 상황은 고려하지 않는다.

동적 프로그래밍 (Dynamic Programming)

정의

복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘.

특징

중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높인다.

메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 기법을 사용한다.

 

 

피보나치 수열의 DP 구현(Top-down)

def fib(n, memo):
    if n <= 1:
        return n
    
    if n not in memo:
        memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

memo = {}
n = 5
print(fib(n, memo))     # 출력: 5

 

 

방향 그래프의 이행적 폐쇄

방향 그래프의 이행적 폐쇄(Transitive Closure)는 그래프에서 직접적으로 연결되어 있지 않더라도, 경로를 통해 도달할 수 있는 정점을 모두 연결한 그래프를 말한다. 즉, 정점 A에서 정점 B로 가는 경로가 하나라도 존재하면, A에서 B로 직접 간선이 있다고 가정하는 그래프를 만드는 것이다.

 

이걸 구해야 하는 이유

"여기서 저기까지 정말 갈 수 있어?"라는 질문에 확실히 답하려면, 단순한 간선 정보만으로는 부족하다. 따라서 그래프 내 모든 정점 쌍에 대해 실제로 경로가 존재하는지를 판단해야 하며, 이 과정에서 이행적 폐쇄를 구하면 정점 간 도달 여부를 명확하게 판단할 수 있다.

 

이를 효율적으로 계산하기 위해 플로이드–워셜 알고리즘을 사용하며, 결과적으로 "정점 i에서 j로 갈 수 있는지"에 대한 도달성 행렬(=이행적 폐쇄)을 얻게 된다.

 

간단한 예시

다음과 같은 방향 그래프가 있다고 가정한다면,

A → B → C

이 그래프에서는,

• A → B 간선 존재
• B → C 간선 존재
• A → C는 직접 연결되지 않았지만, A → B → C 경로로 도달 가능

이 그래프의 이행적 폐쇄는 다음과 같다.

A → B
A → C   ← 새로 추가됨 (A → B → C 경로가 존재하므로)
B → C

 

수학적 정의

그래프 G=(V, E)의 이행적 폐쇄란, 모든 두 정점 쌍 u, v에 대해, 만약 u→v로 어떤 식으로든 도달 가능한 경로가 존재하면,
그에 해당하는 간선 (u,v)를 추가한 그래프예요.

 

구현 방법과 목표

구현 방법

• 플로이드–워셜 알고리즘: 모든 정점 쌍에 대해 도달 여부를 판별하는 데 많이 사용
• DFS/BFS: 각 정점에서 도달 가능한 정점을 전부 찾는 방식

목표

• 방향 그래프가 주어졌을 때, 정점 간 도달 가능성을 판단해,
• 모든 가능한 간선을 추가한 이행적 폐쇄를 구하는 것.