동적계획법27 [Baekjoon] 9184번: 신나는 함수 실행 https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 해결 과정 착안 구하고자 하는 값이 어떠한 점화식의 형태를 이용하여 구해지도록 함수를 구현해야 하므로, 동적계획법(dynamic programming)을 사용하여 구현해보고자 하였다. 구현 메모이제이션에 사용할 배열들을 편의상 전역 변수로 만들어 모든 함수에서 접근 가능하도록 구현하였다. * int result[21][21][21] : 계산한 값을 저장. * bool computed[21][21.. 2023. 5. 17. [Baekjoon] 24416번: 알고리즘 수업 - 피보나치 수 1 https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 의사 코드를 그대로 구현하여, 피보나치 수열(Fibonacci sequence)의 \(n\)번째 항을 구하기 위한 재귀 호출(recursive call, recursion)을 통한 계산에서의 코드 1의 실행 횟수와 동적계획법(dynamic programming)을 통한 계산에서의 코드 2의 실행 횟수를 각각 출력한다. * 참고) 경우에 따라, 피.. 2023. 5. 16. [Baekjoon] 1010번: 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 수학적인 배경 지식을 어느정도 요구하는 문제였던 것 같다. 고등학생 때 경우의 수를 구하는 문제를 정말 극도로 싫어했었는데 문제를 해결하다보니 그 때의 생각이 물씬 났다. ㅎㅎ;; 이번 문제를 해결하는 것 자체는 사실 수리논리적으로 그렇게 어려운 일은 아니지만(반박 시, 당신의 말이 옳습니다) 초보 프로그래머로서는 프로그래밍적으로는 생각해 볼 여지가 꽤 많은, 좋은 문제라고 생각한다. 문제 해결 .. 2023. 5. 6. 이전 1 2 3 4 5 다음
