따봉도치야 고마워

문제 설명 programmers.co.kr/learn/courses/30/lessons/43105?language=java# 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요...

문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 연속된 배열에서 합이 최대가 되는 연속 부분 합을 찾아라 ex) 풀이 1.완전탐색 2.부분합 배열 사용 3.분할정복 4.동적계획법 - 일단 f(i) = i를 끝으로 하는 배열의 최대합으로 생각하면 - f(i) = max(0, f(i-1)) + 현재 원소값이 된다. 무슨 소리냐면 이전까지 더해온 합이 음수라면, 현재 원소값을 더한 값 < 현재 원소값 이 확정이기 때문에 0으로 초기화 해준다. #inclu..

문제 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2Xn크기의 직사각형을 2X1, 1X2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래는 2X5의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1

문제 하나의 막대기가 있다. 막대기 길이에 따라 가격이 다르다. 최고의 수익을 얻도록 막대기를 자르라. 입력 막대의 길이, 길이 별 가격 출력 최고 수익 풀이 - 길이가 4인 막대가 있다고 할 때 나올 수 있는 경우의 수는 아래와 같다 막대기를 1만큼 자른게 R1이라고 했을 때 최종 가격은 R1+R1+R1+R1 , R1+R3 , R2+R2 , R4 중 최적의 값이 된다. 여기서 R3은 R1+R2의 조합으로 볼 수 있고, R2도 마찬가지로 R1+R1의 조합으로 볼 수 있다 즉 각각의 길이에 맞는 최대값을 구해놓으면 최적의 값 계산이 가능하다. ex) R1은 더 자를 수 없으니 1이 최대 값이고 R2는 R1+R1의 조합인 2와 자르지 않은 가격인 5를 비교해 더 큰 값인 5 가 된다 R3은 R1+R2(1+5..

최적화 문제를 푸는 방법은 두 가지가 있다 1. 모든 상황을 고려해 최적의 방법을 찾는 것 -> 동적계획법 2. 그때 그때 가장 최선의 방법을 선택해 답을 구하는 방법 -> 탐욕법 동적계획법 (Dynamic Programming) - 전체 문제를 여러 개의 하위 문제로 나누고, 하위 문제들의 해결 방법을 결합해 최종 문제를 해결하는 방식 예제 1. 배낭문제 2. 막대기 자르기 . . 탐욕법 (탐욕 알고리즘, Greedy Algorithm) - 문제를 해결하는 과정에서 순간순간마다 최적이라고 생각하는 결정을 내려 진행해 최종 문제를 해결하는 방식 - 전체 문제해결의 최적의 답을 보장하진 않지만, 계산 속도가 빠르다는 장점이 있다. 위의 문제 (가장 큰 수 찾기)에서도 실제로 가장 큰 수는 99이지만, 그리..