반응형 dynamic programming24 [C/C++] 프로젝트 오일러 #92 Square Digit Chains(동적계획법) Project Euler 문제 92번은 숫자의 반복적인 변환 과정을 다룹니다. 기본적으로, 하나의 숫자를 각 자릿수로 나눈 뒤 각각의 자릿수를 제곱하여 더하는 과정을 반복하는데, 모든 숫자는 결국 1이나 89로 수렴하게 됩니다. 이 문제에서 중요한 점은 어떤 숫자들이 89로 도달하게 되는지 찾는 것입니다.예를 들어 숫자 44로 시작한다고 가정해봅시다. 4의 제곱은 16이므로, 44의 자릿수인 4와 4를 각각 제곱하면 16과 16이 되어 합계는 32입니다. 32를 다시 같은 방식으로 계산해보면 3²과 2²의 합인 13이 됩니다. 이어서 13을 1²과 3²로 계산하여 10을 얻고, 마지막으로 1²과 0²의 합을 통해 1에 도달하게 됩니다. 따라서 44는 최종적으로 1에 수렴하는 수라는 결론에 도달합니다.다른.. 2024. 11. 13. [C/C++] 백준 #2718 타일 채우기(동적계획법) 경우의 수를 알아내라는 문제들 상당수는 동적계획법(Dynamic Programming)으로 해결할 수 있습니다.하지만 동적계획법을 사용하기 위해서는 문제를 올바르게 이해하는 것이 선행되어야 합니다. 2xn일 때에는 피보나치 수열과 비슷한 점화식을 얻을 수가 있습니다. 하지만 3xn, 4xn 과 같이 수가 늘어나면 조금 더 복잡한 점화식이 필요합니다. 일단 제가 모델링한 것은 조금 복잡합니다.이전값에 대해서 4개값까지 참고를 하니까요. 문제는 다음 링크와 같습니다.https://www.acmicpc.net/problem/2718 프로그램 설명: 1. 함수 solve(int n) • 이 함수는 주어진 n 크기의 바닥을 채우는 방법의 수를 계산하고 출력합니다. • 이 문제에서는 특이한 점이 있는데, 점화.. 2024. 8. 10. [C/C++] 백준 #2698 인접한 비트의 개수(동적 계획법) 동적 계획법(Dynamic Programming)으로 문제를 풀기 위해서는, 해당 문제에 대한 모델링을 해주어야 합니다. 모델링(modeling)을 할 때에는 N의 문제를 그보다 크기가 작은 N-1이나 N/2의 문제 등 보다 작은 형태로 나누어 주어야 하죠. 보통 N-1 문제로 표현할 수 있는 경우에는 시간 복잡도가 \(O(N)\)이 되며, N/2 문제로 표현할 수 있는 문제는 \(O(\log N)\) 또는 \(O(N \log N)\) 문제로 표현될 수 있습니다. 예를 들어서 피보나치 수열의 경우에는 N의 문제를 N-1 문제와 N-2 문제로 해결하며, 이 것을 그대로 적용하면 \(O(N)\)이 되며, 보다 적극적인 방법으로 이분 탐색을 진행한다면, \(O(\log N)\) 복잡도로 해결할 수 있습.. 2024. 8. 9. [C/C++] 백준 #2624 동전 바꿔주기(동적계획법) 동전 바꿔주기 문제는 여러 종류의 동전을 가지고 원하는 액수의 금액을 맞추어주는 경우의 수 문제입니다.실생활에서는 크게 도움이 되지 않겠지만, 동적계획법을 이용한 알고리즘 문제로는 매우 유명합니다. 동적계획법을 사용할 때에는 보통 다차원 배열을 이용하게 되는데, 다차원 배열 대신에 맵(map) 또는 딕셔너리(dictionary) 자료를 이용해서도 문제를 풀 수 있습니다. 중간에 생기는 상태값의 갯수에 비해서 키(key)의 범위가 매우 큰 경우에는 다차원 배열보다는 맵 자료형을 사용하는 것이 좋습니다. 이것은 대략적인 감에 의존할 수밖에 없습니다. 다차원 배열이나 정렬되지 않은 맵(unordered map) 모두 \(O(1)\) 검색 알고리즘이지만, 정렬되지 않은 맵을 처리하기 위해서는 오버로드가 .. 2024. 5. 10. [C/C++] 백준 #2579 계단 오르기(동적 계획법) 계단 오르기 조건들이 주어지면서, 계단에 적힌 값을 최대, 또는 최소가 되도록 하는 문제들이 꽤 많습니다. 보편적으로 이러한 문제들은 동적 계획법을 이용해서 풀 수 있습니다. 백준 사이트에서 주어진 문제 링크입니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단 오르기의 조건은 1) 한계단 내지 두계단을 밟을 수 있다. 2) 연속된 3개의 계단을 밟을 수 없다. 3) 도착 계단을 반드시 밟아야 한다. 입니다. 이것을 동적 계획법으로 풀기 위해서는 최.. 2023. 11. 9. [C/C++] 백준 #2502 떡 먹는 호랑이(구현) 이번 문제는 알고리즘이 무엇이라고 이야기하기가 어렵습니다. 그냥 구현이라고 하도록 하겠습니다. https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 피보나치 수열은 동적 계획법(dynamic programming)이나 재귀함수(recursion)이 나올 때 자주 등장하는 문제입니다. 일반적으로는 첫번째 항이 1, 두번째 항이 1인 경우입니다. 이번 문제는 d번째 항의 값이 주어졌을 때, 가능한 첫번째 항과 두번째 항 중 하나를 출력하면 됩니.. 2023. 5. 28. 이전 1 2 3 4 다음 728x90
