늘 겸손하게

안녕하세요 besforyou입니다 백준 16395 - 파스칼의 삼각형 문제 풀이를 설명하겠습니다 문제 풀이 동적 계획법 (Dynamic Programming)을 사용해야 합니다. 일일이 다 구하려 하지 마시고, 주어진 n값만큼의 행을 가진 파스칼 삼각형을 메모이제이션(memoization)으로 구한 뒤 n행 k번째 값을 출력해주기만 하면 됩니다. 파스칼 삼각형 만드는 법 2차원 배열 mat을 선언하고 파스칼 삼각형의 (왼쪽에서부터 1번 ) 1행 1번 -> mat [1][1] 2행 1번 -> mat [2][2] , 2행 2번 -> mat [2][1] 3행 1번 -> mat [3][3], 3행 2번 -> mat [3][2], 3행 3번 -> mat [3][1] . . . 방식으로 파스칼의 삼각형을 생성하면 ..

DP 문제를 처음으로 스스로 풀었네요 문제 풀이 모든 경우를 다 구하려면 시간 초과가 나오므로 dynamic programming으로 풀어야 한다. 1. 합이 최대가 되는 경로에 있는 수의 합을 출력해야 하고, 위에서 아래로 내려갈 때 더 큰 숫자가 있는 방향으로 나아가야 하므로 두 개의 숫자를 비교한 후 더 값이 큰 숫자를 반환하는 함수를 만들어두자. 2. 삼각형의 맨 위에서 아래로 내려가는데, 더 큰 수가 있는 방향으로 내려가고 더 큰 수를 합하면서 맨 아래까지 내려가야 한다. -> 이 과정에서 지금까지 합한 값을 기록해야 하고 다음 값을 계산할 때 기록한 값을 사용한다. 3. edge case 주의 : 맨 오른쪽 정수는 바로 윗줄의 맨 오른쪽, 맨 왼쪽 정수는 바로 윗줄의 맨 왼쪽만 선택 가능하다...

출처 : https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 문제를 풀기 위해, 문제를 여러 개의 하위 문제 (subproblem)으로 나누어 푼 다음, 그것을 결합하여 최종 목적에 도달하는 것 하위 문제의 해결방법을 찾았는데 같은 하위 문제가 계속해서 나올 경우 계산 횟수를 줄일 수 있다. 출처 : https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182 이름은 다이내믹 프로그래밍이지만 전혀 다이나믹하지도 않고 프로그래밍이라기보다는 테이블을 만드는 기법입니다. 대표적인 동적 프로그래밍으로 ..