본문 바로가기

동적계획법

알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 22. [BOJ 백준] 정수 삼각형(1932) Java 링크 : https://www.acmicpc.net/problem/1932 문제 설명 : 더보기 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다. 입력 : 더보기 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. 출력 : 더보기 첫째 줄에 합..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2021. 7. 20. 그래프 & DP(동적계획법) 백준 36문제 구분 문제 이름 문제 링크 풀이 그래프 집합의표현 https://www.acmicpc.net/problem/1717 https://subbak2.tistory.com/51 줄 세우기 https://www.acmicpc.net/problem/2252 https://subbak2.tistory.com/10 네트워크 연결 https://www.acmicpc.net/problem/1922 https://subbak2.tistory.com/13 lca 2 https://www.acmicpc.net/problem/11438 https://subbak2.tistory.com/60 키 순서 https://www.acmicpc.net/problem/2458 https://subbak2.tistory.com/52 게임 개..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2020. 7. 29. [BOJ 백준] 내려가기(2096) C++, Java 링크 : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 설명 : 더보기 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 ..
알고리즘 Algorithm/BOJ 백준 (초급~중급) 2020. 7. 14. [BOJ 백준] 피보나치 수 2(2748) C++, Java 링크 : https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net 문제 설명 : 더보기 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13,..

티스토리툴바