[WEEK03] 정글 5기 - 컴퓨팅 사고로의 전환

1. 다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming)	- 동적 계획법이라고 표현하기도 한다. - DP의 조건     · 1. 큰 문제를 작은 문제로 나눌 수 있다.     · 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에도 동일하다.
탑다운 VS 바텀업	- 탑다운(Top-Down)[하양식)     · 재귀함수     · 큰 문제를 해결하기 위해 작은 문제를 호출 - 바텀업(Bottom-Up)[상향식)     · 반복문     · 작은 문제부터 차근차근 답을 도출 - 가능하다면 재귀함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현을 권장 - 시스템상 재귀 함수의 스택 크기가 한정되어 있을 수도 있다.     · sys.setrecursionlimit()로 재귀 제한 완화 가능
DP와 분할정복의 차이점	- DP는 문제들이 서로 영향을 미친다. 분할정복 - 문제를 작게 나누어 해결하고, 이 해결을 결합하여 원래의 문제를 해결한다. - 또한 재귀를 이용하여 구현하는 것이 일반적이다. - 따라서, 부분 문제들이 서로 독립적일 때 사용하기 좋다 DP - 동적 계획법은 하위 문제들을 한 번씩만 계산하고, 이를 이용하여 상위 문제를 효율적으로 계산하는 것에 목적을 둔다. - 또한 반복문을 이용하여 구현하는 것이 일반적이다. - 부분 문제들이 서로 종속적일 때 사용하기 좋다.

 

예시) 피보나치 수열

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수(Fibonacci Function)를 재귀 함수로 구현(탑다운 다이나믹 프로그래밍)
def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 이미 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]
    
print(fibo(99))

# ========================================================================
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i - 1] + d[i - 2]
    
print(d[n])

 

---

2. 그리디 알고리즘

그리디 알고리즘

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 그리디 알고리즘은 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다.

 

---

3. LCS (Longest Common Subsequence)

LCS	- LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말한다. - 하지만 최장 공통 문자열(Longest Common Substring)을 말하기도 한다.
Longest Common Subsequence	- 부분 수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. * 최장 부분순서의 길이는 유일하지만(unique), 그 길이를 갖는 최장 부분순서는 여러 개 존재할 수 있다.
Longest Common Substring	- 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다.

 

 

최장 공통 문자열

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = 0

- LCS라는 2차원 배열을 이용하여 두 문자열을 행, 열에 매칭합니다. 1. 문자열A, 문자열B의 한글자씩 비교한다. 2. 두 문자가 다르면 LCS[i][j]에 0을 표시한다. 3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다 4. 위 과정을 반복 - 위 과정이 성립하는 이유는 공통 문자열은 연속되야 하기 때문이다. - 현재 두 문자가 같을때 두 문자의 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어질 것이고, 아니라면 본인부터 다시 공통 문자열을 만들어 가게 될 것이다.

 

최장 공통 부분수열 길이 구하기

if i == 0 or j == 0:  # 마진 설정
	LCS[i][j] = 0
elif string_A[i] == string_B[j]:
	LCS[i][j] = LCS[i - 1][j - 1] + 1
else:
	LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

- LCS라는 2차원 배열에 매칭하고 마진값(0,0 라인)을 설정한 후 검사 1. 문자열A, 문자열B의 한글자씩 비교한다. 2. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시합니다. 3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다 4. 위 과정을 반복한다. - 2번에 대해서 설명하자면 부분수열은 연속된 값이 아니다. 햔재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지된다.

 

최장 공통 부분수열 찾기

1. LCS배열의 가장 마지막 값에서 시작한다. 결과값을 저장할 result 배열을 준비한다. 2. LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾는다.     · 2-1. 만약 같은 값이 있다면 해당 값으로 이동한다.     · 2-2. 만약 같은 값이 없다면 result배열에 해당 문자를 넣고 LCS[i - 1][j - 1]로 이동한다. 3. 2번 과정을 반복하다가 0으로 이동하게 되면 종료한다. result 배열의 역순이 LCS이다.

 

- 그림으로 확인하고 싶다면?!

해당 블로그를 참조해주세요.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

---

4. Knapsack Problem (배낭 채우기 문제)

배낭 채우기 문제란?	- 도둑이 보석가게에 배낭을 메고 침입했다. - 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. - 각 보석들의 무게와 가격은 알고 있다. → 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은?
해결방법1 완전탐색(Brute-Force)	- n개의 보석이 있다고 치면, n개의 보석으로 만들 수 있는 가능한 부분집합의 수는 2^n개이다. - 최악의 경우에는 O(2^n)은 너무 느리다.
해결방법2 DP	- 큰 문제를 작은 문제들로 쪼갤 수 있다. - 배낭에 보석을 담는 과정을 작은 문제들로 생각한다.     · 배낭에 보석을 담고 나면 배낭의 무게와 가치를 업데이트하고 다시 보석을 가방에 담아야한다.
로직 생각하기!	- 로직을 반복할 때 변경되는 것은 2가지다.     · 1. 배낭의 최대무게     · 2. 담을 수 있는 봉투의 개수 및 종류 - 경우의 수가 여러 가지로 갈리기 때문에 2차원 배열을 사용하여 각 경우의 수에 따른 답을 따로 저장해줘야 한다. - 최대이익[i][w] = 최대무게가 w인 가방에서 i번째 물건까지 판단했을 때의 최대 가치
경우의 수1	1. 물건의 무게가 최대 배낭 무게(w)를 초과할 때 - 애초에 이 경우에는 물건을 배낭에 넣을 수 없다.     · 그러므로 최대 가치는 이전의 최대 가치인 K번째로 유지된다. - 아무것도 넣지 않았으므로 배낭 무게 w에는 아무런 변화가 없다. - 그리고 K + 1까지 진행했으므로     · dp[K + 1][W] = dp[K][W]     · 여기서 dp[K][W]는 기존에 있던 최대 가지를 의미한다.
경우의 수2	2. 물건의 무게가 최대 배낭 무게(W)를 초과하지 않을 때 2.1 넣지 않는다 - 이 경우는 물건의 무게가 배낭 무게를 초과할 때와 같다.     · 왜냐면 물건을 넣지 않는 것과 똑같기에        배낭 무게 W는 변하지 않고 최대 가치도 그대로 이전 K번째이기 때문. - dp[K + 1][W] = dp[K][W] 2.2 넣는다 - 최대 Wkg까지 담을 수 있는 배낭이 K + 1번째 물건을 담았을 때가 최대 가치라면     · dp[K + 1][W] = K + 1 가치 + dp[K][W-M]     · 해석하자면 K + 1번째 물건의 가치 + 그 물건의 무게 M을 뺀 (W-M)kg로        1~K 물건으로 구할 수 있는 최대 가치
로직 최종 정리	1. 물건 K의 무게 > 배낭 W 무게     · dp[K][W] = dp[K - 1][W] 2. 물건 K의 무게 <= 배낭 W 무게     · dp[K][W] = max( dp[K - 1][W], K가치 + dp[K - 1][W - K무게] )     * (왼쪽 값)과 (왼쪽 대각선 + K 값)의 최댓값

 

참고

https://howudong.tistory.com/106

---

5. 분할 정복

분할 정복이란?	- 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법 - 해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법 - 분할 정복법은 하향식(top) 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다.
분할 정복의 과정	1. 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다. 2. 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용하고 있다. 3. 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.
분할 정복의 장단점	장점 1. 빠른속도 : 큰 문제를 작은 하위 문제로 분할하고 해결하여 전체 문제를 해결하는 데 걸리는 시간을 줄일 수 있다. 2. 쉬운 병렬화 : 분할정복 알고리즘은 하위 문제를 병렬로 처리하기 쉬우므로                           멀티코어 시스템에서 성능을 크게 향상할 수 있다. 3. 유연성 : 이 알고리즘은 여러 응용 분야에서 사용될 수 있으며, 문제의 복잡도와 데이터 크기에 상관없이 적용할 수 있다. 단점 1. 추가적인 메모리 요구 : 알고리즘은 재귀적으로 호출되므로 많은 추가적인 메모리를 필요로 할 수 있다. 2. 최악의 경우 시간 복잡도 : 일부 문제에 대해서 분할정복 알고리즘이                                             최악의 경우에도 빠른 해결책을 제공하지 못할 수 있다.

---

6. Linked List / 포인터(pointer) : & 연산자와 * 연산자

 

 

---

ETC..

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

스택(stack) - 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간 - 선언되는 순서와 반대로 메모리가 해제되는 LIFO 구조를 가지고 있다. - 용도     · 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장     · 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때,                              반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다. - 장점     · 동적으로 메모리를 할당하고 해제할 수 있다.     · 구현이 간단하며, 메모리 관리 overhead가 낮다. 레지스터(register) - 프로세서 내부의 고속 작동 메모리로, 프로시저 실행 중 자주 접근하는 변수나 중간 계산값을 저장하기 위해 사용 - 용도     · 중간 연산 결과의 저장 : 연산 중 생성되는 중간 값을 빠르게 저장하고 접근하기 위해 사용     · 빠른 데이터 접근 : 특정 데이터나 주소를 빠르게 저장하고 로드하기 위해 사용 - 장점     · 매우 높은 데이터 접근 속도를 제공     · 데이터를 메모리로부터 레지스터로 빠르게 이동시킬 수 있어 연산 효율이 증가

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

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

# 일반 재귀
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

# 꼬리 재귀
def factorial_tail(n, acc):
    if n == 1:
        return acc
    return factorial_tail(n - 1, n * acc)

 

3. 그리디 알고리즘 설명	- 그리디 알고리즘(Greedy Algorithm) - 정의 : 매 순간마다 가장 좋아 보이는 선택을 하는 알고리즘으로, 지역 최적화를 통해 전역 최적화를 도달하길 기대한다. - 특징 : 각 단계에서의 최적의 해답을 찾아 나가면서 전체 문제의 최적 해답을 찾아나가는 방식이다.     · 각 단계에서의 결정은 지금까지의 상황만을 고려하며, 이후의 상황은 고려하지 않는다
4. 동적 프로그래밍 설명	- 동적 프로그래밍(Dynamic Progamming) - 정의 : 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은 하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘이다. - 특징 : 중복된 하위 문제들을 여러 번 해결하는 것을 방지하여 효율성을 높인다.     · 메모이제이션(Memoization) 또는 타뷸레이션(Tabulation) 기법을 사용
5. 상향식과 하향식의 차이	- 상향식(Bottom-Up) : 작은 문제부터 차례대로 해결해 나가면서 큰 문제의 해결책을 구한다. - 하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결한다. 필요할 때 하위 문제를 해결한다.