크래프톤 정글 week03, day23 - 퀴즈 복습, 알고리즘 문제

스택과 레지스터의 용도와 장점

• 스택
  • 프로시저 호출 시 지역 변수와 매개변수를 저장하기 위한 메모리 공간이며, LIFO(Last in First Out)이라는 마지막에 들어온 값이 먼저 나가는 구조를 가지고 있다.
  • 용도
    • 함수의 로컬 변수 저장 : 각 함수 호출 시 그 함수의 로컬 변수들이 스택에 저장된다.
    • 함수의 제어 흐름 관리 : 함수가 다른 함수를 호출할 때, 반환 주소와 이전 함수의 스택 프레임 정보가 스택에 저장된다.
  • 장점
    • 동적으로 메모리를 할당하고 해제할 수 있다.
    • 구현이 간단하며, 메모리 관리의 오버헤드가 낮다.

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

 

꼬리 재귀 최적화

• 재귀 함수 호출 시 호출 스택의 사용을 최적화 하는 기법
• 재귀 함수가 호출될 때마다 스택 프레임이 생성되며, 이는 메모리 사용량 증가와 스택 오버플로우의 원인이 되는데, 꼬리 재귀 최적화는 재귀 함수의 마지막 연산만 호출 스택에 남겨두고, 나머지를 제거하는 것으로 해결할 수 있다.
  • 이를 통해 함수가 반환되면 다시 호출 스택을 재사용할 수 있다.

• 꼬리 재귀 함수는 반환값을 바로 return하기 보단 파라미터로 전달하는데, 이렇게 하면 호출 스택에 쌓이지 않고 후속 호출로 이동된다.
  • 결국 마지막 호출에서 스택 프레임을 재활용하기 때문에, 메모리 사용량이 일정하게 유지된다.

​

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

• 그리디 알고리즘
  • 매 순간마다 최선의 값만 찾는 선택을 하는 알고리즘
  • 각 단계에서의 최적의 해를 찾으면서 전체 문제의 최적의 해를 구하는 방식
    • 현 상황의 최적의 해를 구하기 때문에 언제나 결과가 최적의 결과일수는 없다.

• 동적 프로그래밍
  • 복잡한 문제를 여러 개의 작은 문제로 나누어 해결하고, 그 결과를 저장해 중복 문제가 발생했을 때 빠르게 저장한 곳에서 가져올 수 있는 알고리즘
  • 중복 문제들을 여러 번 반복하는 것을 방지할 수 있어 효율성을 높인다.
  • 유형
    • 상향식(Bottom-Up) : 작은 문제부터 차례대로 해결해 나가며 큰 문제의 해결책을 구한다. 타뷸레이션 기법을 사용
    • 하향식(Top-Down) : 큰 문제를 작은 문제로 나누어 해결하며, 필요할 때 하위 문제를 해결한다. 메모이제이션 기법을 사용

---

아주 평범한 배낭

• 넣을 무게가 정해진 배낭에 물품을 넣으며 가장 가치가 높은 경우의 수를 찾기

import sys

# def backpack():
#     n, k = map(int, sys.stdin.readline().split())
#     items = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

#     dp = [0 for _ in range(k+1)]
#     # 전체 물건을 순회하면서 
#     for i in range(n):
#         # 가방 무게부터 현재 물건의 무게보다 작은 값까지 -1씩 반복
#         for j in range(k, items[i][0]-1, -1):
#             # 현재 물건을 배낭에 넣는 것이 가치가 더 크면 넣고
#             # 그렇지 않으면 넣지 않는다
#             dp[j] = max(dp[j], dp[j-items[i][0]] + items[i][1])

#     print(dp[k])

# backpack()

def backpack():
    n, k = map(int, sys.stdin.readline().split())
    item = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    # 해시 맵으로 저장
    max_value_bag = {0:0}
    # 입력받은 물품들 내림차순으로 정렬
    max_firth_wv = sorted(item, reverse=True)
    # 정렬한 물품들 돌리면서 무게,가치 가져오기
    for w, v in max_firth_wv:
        # 물건 추가할 때 쓸 딕셔너리 생성
        backpack = {}
        # 고려한 물건들로 만들 수 있는 조합을 검토
        for _v, _w in max_value_bag.items():
            # 무게와 가치를 계산
            w_if_added = _w + w
            v_if_added = _v + v
            # 만약 무게가 가방의 한도를 초과하지 않으면 
            if w_if_added < max_value_bag.get(v_if_added, k + 1):
                # 임시 딕셔너리에 추가
                backpack[v_if_added] = w_if_added
        # 임시 딕셔너리를 원래 딕셔너리에 업데이트
        max_value_bag.update(backpack)
        
    return max(max_value_bag.keys())

print(backpack())

 

동적 프로그래밍의 대표 문제인 knapsack 문제, 코드가 너무 어려워서 팀원한테 배웠다.

​

행렬 곱셈 순서

• 행렬 들의 곱셈에 순서를 다르게 하여 최소값을 구하는 문제

import sys

def hanggop():
    n = int(sys.stdin.readline())
    hangyeol = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
    table = [[0]*n for _ in range(n)]
    INF = int(1e9)

    # 행
    for gop in range(1, n):
        for start in range(n - gop):
            # 
            end = start + gop
            table[start][end] = INF
            for mid in range(start, end):
                table[start][end] = min(
                    table[start][end],
                    table[start][mid] + table[mid+1][end] 
                    + hangyeol[start][0] * hangyeol[mid][1] * hangyeol[end][1]
                )

    print(table[0][n-1])

hanggop()

이걸 왜 중급 문제로 지정했는지 모르겠다. 작성 중인 현재는 행렬의 점화식에 대해 어느정도 이해하게 되었는데 풀 당시는 뭐라는지 하나도 모르겠어서 지피티의 힘을 빌렸는데도 이해를 못했다.

​

학습 시간 : 10 ~ 24시