programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 💡 Dynamic Programming으로 풀이했습니다. 먼저 주어진 triangle과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그대로 0이므로 고려하지 않아도 됩니다. dp의 마지막 줄에 다다를 때까지 이를 반복하고, 마지막 줄에 도달하면 while문을 종료합니다. 여기..

Edit Distance : 한 스트링이 다른 스트링으로 되기까지 필요한 editing operation의 최소 횟수 editing operation : insertion(1), deletion(1), substitution(2) (괄호 안은 각 operation의 cost, Levenshtein) * Levenshtein은 substitution의 cost를 2로 본다 ∵ insertion(1) + deletion(1) = substitution(2) 모든 distance 계산하기 어려움. 그래서 Dynamic Programming 도입 Dynamic Programming - 복잡한 계산 = subproblems를 합쳐서 구해가기 - bottom-up 방식 예를 들어, INTENTION을 EXECUTI..