DP 검색 결과
9 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 10826 피보나치 수 4(BigInteger)(Kotlin - 코틀린)

백준 10826번 문제입니다. (solved.ac)기준 실버 4 문제입니다. https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 문제 접근 우선 재귀호출로는 시간초과가 발생할 수 있을 것 같아 다이나믹 프로그래밍(DP)방식으로 문제를 풀었습니다. 10,000번째 피보나치 수 3364476487643178326662161200510754331030214846068006390656476997468008144..

2022. 4. 22. 00:25
알고리즘 문제풀이[Algorithm]

[백준] 2156번 포도주 시식(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 2156번 문제입니다. (solved.ac)기준 실버 1 문제입니다. 아래에 있는 백준 2579번 계단 오르기 문제와 굉장히 유사한 문제입니다. [백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python) [백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python) 백준 2579번 문제입니다. (solved.ac)기준 실버 3 문제입니다. https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host=".. soopeach.tistory.com 문제 접근 포도주를 마시는데에는 두 가지 규칙이 존재합니다. 1. 포도주 잔을 선택하면 그 잔에 들어있는 포도..

2022. 2. 18. 17:05
알고리즘 문제풀이[Algorithm]

[백준] 1932번 정수 삼각형(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 1932번 문제입니다. (solved.ac)기준 실버 1 문제입니다. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 접근 처음에는 하나 하나 어떻게 비교하나 생각을 했었는데.. 생각을 해보니 위에서부터 아래로 내려가면서 더 큰 값을 더해주고 맨 마지막 줄에서 가장 큰 값을 출력하게 만들면 되는 문제였습니다..! 예를 입력 1로 예를 들면 두번째 줄에 있는 3, 8은 선택의 여지없이 7을 받아 각각 10과 15가 되고 세 번째 줄에 있는 8, 1, 0 중 가장 왼쪽에 있는 8은 반드시 10(7+3)을 받아..

2022. 2. 14. 21:46
알고리즘 문제풀이[Algorithm]

[백준] 11053번 가장 긴 증가하는 부분 수열(LIS)(DP)(Python - 파이썬)

백준 11053번 문제입니다. (solved.ac)기준 실버 2 문제입니다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 부분 수열이란? 원소가 n개인 수열의 일부 원소를 골래내어 만든 수열이 부분 수열입니다. seq = [ 10, 20, 10, 30, 20, 50]이라는 수열이 존재할 때 이 수열의 부분 수열로는 [10,20], [20, 10, 50], [30,..

2022. 2. 13. 02:40
알고리즘 문제풀이[Algorithm]

[백준] 2579번 계단 오르기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 2579번 문제입니다. (solved.ac)기준 실버 3 문제입니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 접근 첫째 줄에 계단의 개수가 주어지고 둘째 줄 부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여있는 점수가 주어집니다. 계단 오르기 게임에서 얻을 수 있는 최대 점수를 출력하면 됩니다. 게단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임입니다. 계단을 오르는데에는 3가지 규..

2022. 2. 10. 17:01
알고리즘 문제풀이[Algorithm]

[백준] 1463번 1로 만들기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 1463번 문제입니다. (solved.ac)기준 실버 3 문제입니다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 접근 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어집니다. 아래에 나와있는 세 가지 연산법만을 사용하여 최소횟수로 1로 만들고 그 최소 횟수를 출력하면 되는 문제입니다. 1. N이 3으로 나누어 떨어지면, 3으로 나눈다. 2. N이 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 빼준다. 다이나믹프로그래밍 알고리즘으로 접근하였습니다. d[]리스트를 (n+1)개만큼 생성 후 d[n] 에 정수 n을 1로 만들..

2022. 2. 8. 23:45
알고리즘 문제풀이[Algorithm]

[백준] 9095번 1, 2, 3 더하기(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 9095번 문제입니다. (solved.ac)기준 실버 3 문제입니다. https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 접근 첫째 줄에 테스트 케이스 T가 주어지고 테스트 케이스 만큼 정수 n을 입력받습니다. n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 되는 문제입니다. 처음에 DP로 접근하는 것이 어려웠는데 접근하고 나서는 간단한 점화식으로 문제를 해결할 수 있었습니다. 1, 2, 3을 이용하여 1을 만드는 방법은 (1)으로 한 가지 방법 / 2를 만드는 방법은 (1+1), (2)으로 두 가지 방법 / 3을 만드는 방..

2022. 2. 7. 15:21
알고리즘 문제풀이[Algorithm]

[백준] 2839번 설탕 배달(다이나믹 프로그래밍)(DP)(Python - 파이썬)

백준 2839번 문제입니다. (solved.ac)기준 브론즈 1 문제입니다. 첫째 줄에 상근이가 배달해야하는 설탕의 무게인 N을 입력 받습니다. 3킬로그램 봉지와 5킬로그램 봉지가 있는데 최대한 적은 봉지를 사용하여 배달을 하고자 하는데 그 때 필요한 봉지의 개수를 출력하는 문제입니다. 만약 3킬로그램 봉지와 5킬로그램 봉지로 정확히 나눌 수 없다면 -1을 출력하는 문제입니다. 문제 접근 그리디 알고리즘을 사용하여 간단하게 풀 수도 있는 문제이지만 현재 다이나믹 프로그래밍(DP)을 공부중이라 DP를 사용하여 문제에 접근하였습니다. 정답 코드 # 배달해야하는 설탕의 무게(n)을 입력 받음 n = int(input()) # d 리스트는 배달하는 봉지의 최소 개수를 담을 리스트임 # DP를 사용하여 문제를 풀..

2022. 2. 6. 23:37
알고리즘 문제풀이[Algorithm]

[백준] 10870번 피보나치 수 5(인덱스 에러 해결법)(Python - 파이썬)

백준 10870번 문제입니다. (solved.ac)기준 브론즈 2문제입니다. https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 0 혹은 자연수인 n을 입력받아 n번째 피보나치 수를 출력하는 문제입니다. n번째 피보나치 수는 n-1 번째 피보나치 수 + n-2번째 피보나치 수 입니다. 0번째 피보나치 수는 0이고 1번째 피보나치 수는 1입니다. 따라서 2번째 피보나치 수는 1 + 0으로 1이며 3번째 피보나치..

2022. 2. 1. 02:42