본문 바로가기
반응형

dynamic programming20

#1520 내리막 길 내리막 길 문제는 나올 수 있는 모든 경로의 개수를 구하는 프로그램입니다. 일반적으로 이렇게 경우의 수를 물어보는 문제는 동적 계획법(dynamic programming)을 이용하면 풀기 쉬워집니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 그러면 어떻게 하면 좋을까요? 상하좌우로 움직일 수 있으니, \((i, j)\)에서의 경우의 수 \(d_{i, j}\)는 주변의 값들의 합으로 나타낼 수 있습니다. \[ d_{i,.. 2022. 8. 29.
#1489 대결 이번 문제는 Gold I 문제네요. A팀과 B팀이 n명의 사람들이 각각 1:1 대결해서 승패를 가리는데, 이기면 2점, 비기면 1점, 지면 0점을 받게 됩니다. 승부를 벌이는 두 사람의 능력치로 승패가 좌우되는데, 높은 능력치가 이기고, 능력치가 같으면 비기게 됩니다. 승부를 벌이는 두 팀의 n명의 능력치를 알고 있을 때, A팀이 얻을 수 있는 최대 점수를 계산하는 것이 목표입니다. 제가 생각한 방법은, 첫번째로 두 팀을 모두 정렬을 합니다. 두번째로 동적 계획법을 이용해서 A 팀이 얻을 수 있는 최대 점수를 구한다입니다. A 팀의 능력치를 오름차순으로 정렬했을 때, \( a_1, a_2, ..., a_n \)이라고 하고 B 팀 역시 \( b_1, b_2, ..., b_n \) 이라고 할 때, 다음과 같.. 2022. 8. 19.
#1354 무한 수열 2(Dynamic Programming) 이번 문제는 #1351과 같은 문제이지만, 숫자 범위가 좀 더 커지고, 두개의 숫자 인덱스를 계산하는 것이 좀 다릅니다. 그러다 보니 제한시간이 2초에서 10초로 대폭 늘었습니다. 난이도도 Gold IV에서 Gold III로 조금 높게 평가되었습니다. 그렇지만 똑같이 동적 프로그래밍을 이용하고 있고, 동적 프로그래밍상 히트율이 많이 낮아져서 시간이 많이 걸립니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //---------------------------------------------------------- // baekjoon #1354 - Infinity Series 2 // - by Aubrey Choi // - created at 2020-02-02 //---------------.. 2020. 2. 2.
#78 코인 나누기(Dynamic Programming) 코인 나누기는 유명한 문제 중 하나입니다. 동적 프로그래밍을 이용해서 구할 수 있는데, 그것을 하기 위해서는 수학적 기반 지식이 있어야 합니다. 코인 나누기라는 것은 N개의 코인을 가지고 코인 갯수를 나누는 방법의 수를 구하는 것입니다. 또는 무한정의 1$, 2$, 3$, .., N$ 코인으로 N$를 만드는 방법의 수라고 할 수도 있습니다. 예를 들어서 코인이 5개 있다면, 아래의 그림과 같이 7가지 방법으로 나눌 수 있습니다. 문제에서 요구하는 것은 이 경우의 수가 1,000,000으로 나누어 떨어지는 가장 적은 수를 구하라는 문제입니다. 단순하게 N에 대해서 경우의 수를 구하는 문제였다면 크게 어렵지 않았을겁니다. 난이도가 30%로 설정된 이유도 아마 비슷할 것이라고 봅니다. 수학적으로 본다면 다음과.. 2020. 1. 27.
#77 소수들의 합(Dynamic Programming, Back tracking) 이번 문제는 난이도 25%로 설정되어 있지만, 워낙 작은 숫자들로 이루어져 있기 때문에 어렵지 않게 풀 수 있습니다. 10을 소수들의 합으로 표현한다면, 다음과 같이 총 5가지로 표현할 수 있습니다. 동일한 소수를 여러번 쓰는 것이 가능하고, 순서없는 조합으로 표현했을 때입니다. 아래와 같이 큰 소수부터 차례대로 나열할 수도 있고, 소수의 빈도만 따져도 됩니다. 이러한 경우의 수가 5,000이 넘는 가장 가장 작은 수를 찾으라는 것이 문제입니다. 사실 어떤 수가 주어졌을 때, 경우의 수를 따지는 것은 크게 어렵지 않습니다. 백트랙킹 방법을 이용해서 풀 수도 있고, 동적 프로그래밍을 이용해서 풀 수도 있습니다. 하지만 경우의 수가 특정수를 넘는 가장 작은 수를 찾는 것은 동적 프로그래밍으로는 조금 한계가 .. 2020. 1. 24.
#1325 효율적인 해킹(DFS) 이번 문제는 Silver II 난이도의 문제입니다. 저는 처음에 너무 단순하게 생각해서 한번 틀렸네요. 신뢰관계의 종속성이라는 문제때문인데요. A 가 B를 신뢰하고, B가 C를 신뢰하면, A가 C를 신뢰한다는 사실입니다. 이에 대한 이해도가 틀리면, 해결방법도 당연히 틀리겠죠. 문제의 요지를 살펴보면, N개의 컴퓨터들이 있고, M개의 신뢰관계가 존재할 경우에, 신뢰를 받는 최상위 컴퓨터를 찾는 것입니다. 예를 들면 다음의 그림과 같이 5대의 컴퓨터가 있고, 4개의 신뢰관계가 주어졌다고 해보죠. 화살표 방향으로 신뢰관계가 주어집니다. E는 C를 신뢰하고, C는 A와 B를 신뢰합니다. 직관적으로 보면, 저 위의 그림의 경우에 A 또는 B를 해킹하면, 총 4대의 컴퓨터를 한번에 해킹할 수 있습니다. 전 이 문.. 2020. 1. 24.
728x90

티스토리툴바