정수 삼각형

이번 포스팅은 동적계획법을 이용하는 정수 삼각형 문제입니다.

 

programmers.co.kr/learn/courses/30/lessons/43105?language=python3

코딩테스트 연습 - 정수 삼각형

이번 문제는 이진트리와 유사해 보이는 피라미드 형식의 Data가 주어질때

 

오직 좌하 or 우하 로만 이동하여 모든값의 합이 최대가 되게하는 문제입니다.

 

아래 예시를 보시죠.

예제의 해답

하지만 해당 문제는 이진트리도, 이진 탐색트리도 아니기 때문에

 

위에서부터 답을 찾아내려가면 애로사항이 발생합니다.(요 경우는 욕심쟁이 방법이라고 봐야겠죠?)

 

예를들어서, 7 -> 8 -> 1 -> 7 -> 5 로 이동할 경우 해당 위치에서 항상 최선의 선택을 합니다.

 

하지만 이 경우 국소해가 전체 문제의 해와 일치하지 않습니다.

 

그렇다고, 위에서 내려오는 모든 경우의 수를 탐색하는것을 비효율적입니다.

 

□문제의 해답

제가 푼 방법은, 삼각형의 하부부터 올라오는 방법 입니다. 위 예제의 일부를 따서 보시죠

 

상향식으로 국소해를 찾아가는 방법

Leaf(삼각형의 최 하부)부터 바로 위의 Layer에서의 최적해를 찾아갑니다.

 

이렇게되면 최 상부에 도달했을 때 도출된 최적해는 전체 Data의 최적해가되어

 

해당 문제의 정답을 구할수 있게 됩니다.

 

아래는 Python으로 작성된 문제의 해답입니다.

def solution(triangle):
    answer = 0
    #정수삼각형을 뒤집어줍니다.(코드의 편의성을 위해서)
    triangle.reverse()
    #하부부터 순차적으로 국소해를 찾아갑니다.
    for i in range(len(triangle)-1):        
        for j in range(len(triangle[i+1])):        	
            #한층 위의 Layer의 Element마다
            #↙,↘위치한 Element들과 더한 값을 비교하고
            #더 큰 값으로 값을 치환해줍니다.
            if (triangle[i+1][j] + triangle[i][j])>(triangle[i+1][j] + triangle[i][j+1]):
                triangle[i+1][j] = triangle[i+1][j] + triangle[i][j]
            else:
                triangle[i+1][j] = triangle[i+1][j] + triangle[i][j+1]
    #모든 최적해 산출이 끝나면 정수삼각형 맨 윗 부분에는
    #모두 더했을때 최대값이 남습니다.
    answer = triangle[-1][0]
    return answer