본문 바로가기
반응형

dynamic programming24

#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.
#1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19.
#76 합의 경우의 수(Dynamic Programming) 이번 문제는 경우의 수를 계산하는 것입니다. 보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다. 문제는 짧은 편입니다. N이란 숫자가 주어지면, 1부터 N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다. 예를 들어서 N=5라고 한다면, \( 5 = 1 + 1 + 1 + 1 + 1 \) \( 5 = 1 + 1 + 1 + 2 \) \( 5 = 1 + 1 + 3 \) \( 5 = 1 + 4 \) \( 5 = 1 + 2 +2 \) \( 5 = 2+ 3 \) 위와 같이 총 6가지가 나옵니다. 이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다. 문제의 원본.. 2020. 1. 15.
728x90

티스토리툴바