문제

문제 링크

코드

DP (Cache)

def make_hash(lst):
    result = []
    for row in lst:
        result.extend(row) # 평준화
    return hash(tuple(result)) # hash는 빌트인 함수

cache = dict()

def find_max(triangle):
    # 캐시 없으면 시간 초과 발생함
    hash_value = make_hash(triangle)
    if hash_value in cache.keys():
        return cache[hash_value]
    
    if len(triangle) == 2:
        root = triangle[0][0]
        return root + max(triangle[1])
    
    root = triangle[0][0]
    del triangle[0]
    
#     sub_triangle_1 = []
#     for i, row in enumerate(triangle):
#         sub_triangle_1.append(row[:i+1])
    
#     sub_triangle_2 = []
#     for row in triangle:
#         sub_triangle_2.append(row[1:])
    
    sub_triangle_1 = list(map(lambda x : x[:len(x)-1], triangle))
    sub_triangle_2 = list(map(lambda x : x[1:], triangle))
    
    # 캐시가 없을 때 코드
    # return root + max(find_max(sub_triangle_1), find_max(sub_triangle_2))
    
    cache[hash_value] = root + max(find_max(sub_triangle_1), find_max(sub_triangle_2))
    return cache[hash_value]
    

def solution(triangle):
    return find_max(triangle)
    

접근법

전형적인 캐시를 이용한 문제 풀이 방법이었다. 그럼에도 불구하고 캐시는 분명 속도 개선의 효과를 주었다. 그래서 느낀 점은 분할 정복이 가능하기에 재귀함수를 통해서 문제를 풀려고 할 때, 어쩌면 캐싱이 안될 지도 모를 것 같기에 캐시를 생략하기 보단 일단 운 좋게 hit할 수도 있기 때문에 무조건 캐시를 써야 한다는 것이다.
그리고 내가 사용했던 점화식의 삼각형 간의 관계는 아래와 같다.

                                      root
                               ________|________
                  sub_triangle_1               sub_triangle_2


		    return root + max(fun(sub_triangle_1), fun(sub_triangle_2))
            
         

위와 같은 꼴의 재귀함수는 캐싱이 될 경우, 시간 복잡도와 공간 복잡도 모두 개선이 될 여지가 있다. 그러나 이 문제의 원래 의도는 root로부터 시작하여 경로의 모든 누적합을 구하는 것이었기에 완벽하게 문제를 풀어내주진 못했다.

시도했던 최적화 기법

해시 함수

def make_hash(lst):
    result = []
    for row in lst:
        result.extend(row) # 평준화
    return hash(tuple(result)) # hash는 빌트인 함수

캐시에 키값을 저장할 때 먼저 해싱을 한 뒤에 키로 사용하였다. 원래는 서브 삼각형을 평준화 한 뒤에 이것을 튜플로 만들어서 키로 사용했다. 그렇게 하면 튜플 자체도 크기가 커서 해시함수를 미리 한번 더 거쳤다. 근데 키로 변하는 순간부터 해시함수가 적용되서 크게 효과는 없었으리라 생각한다. 지금 생각해보니

리스트 선언

원래 코드

     sub_triangle_1 = []
     for i, row in enumerate(triangle):
         sub_triangle_1.append(row[:i+1])
    
     sub_triangle_2 = []
     for row in triangle:
         sub_triangle_2.append(row[1:])

최적화 코드

    sub_triangle_1 = list(map(lambda x : x[:len(x)-1], triangle))
    sub_triangle_2 = list(map(lambda x : x[1:], triangle))

map() 함수를 사용하면 python 내부적으로 연산과 메모리를 관리하기 때문에 효율적으로 모든 요소에 함수를 적용할 수 있습니다. lambda 예약어를 사용해 함수를 만들고 이 함수를 a 변수에 적용했습니다.

참고자료

위와 같은 이유로 속도가 향상된다고 한다. 람다를 애용하자!

DP (누적합)

def solution(triangle):
    cache = triangle # cache 초기화

    for i in range(1, len(triangle)): # 두 번째 행부터 시작
        for j in range(i+1): # 각 행의 요소들에 대해
            # 새로운 최대 합 계산
            if j == 0: # 맨 왼쪽 요소일 경우
                cache[i][j] = cache[i-1][j] + triangle[i][j]
            elif j == i: # 맨 오른쪽 요소일 경우
                cache[i][j] = cache[i-1][j-1] + triangle[i][j]
            else: # 그 외의 요소들은 위쪽 왼쪽, 위쪽 오른쪽 요소 중 큰 값과 더해짐
                cache[i][j] = max(cache[i-1][j-1], cache[i-1][j]) + triangle[i][j]

    return max(cache[-1]) # 마지막 행에서 최대값을 반환

chat gpt에게 내가 짠 코드를 최적화 해달라고 하니, 그냥 다 버리고 누적합으로 다시 풀어버렸다.
그렇다. 애초에 접근부터가 잘못됐던 것이다. 누적합 유형을 익혀둬야겠다.