Programming456 #1351 무한 수열 (Dynamic Programming) 이번 문제는 Gold IV 난이도로 설정되어 있습니다. 무한히 이어지는 수열이 있는데, 이 수열은 다음과 같은 규칙을 가지고 있습니다. 주어진 자연수 P, Q에 대하여 \(A_i\) 항은, \[ A_i = A_{ \lfloor i/P \rfloor } + A_{\lfloor i/Q \rfloor } \] 계속 나누어주는 것이기 때문에 \(A_0\)까지 가는데 빠릅니다. 많아야 \( \log_{P} N + \log_{Q} N \) 번이니까요. 동적 프로그래밍을 이용해서 풀어놓기는 했지만, 그냥 풀어도 적절한 시간안에 풀 수 있는 문제일거라고 보입니다. N의 숫자가 크기 때문에 저는 map 자료구조를 이용해서 풀었습니다. 풀어놓고 보면, 정말 쉬운 문제입니다. 소스도 크게 어려울 것이 없습니다. 제가 작성한.. 2020. 2. 1. #1344 축구(Mathematics) 이번 문제는 총 18번 안에 소수번의 경우의 수가 발생할 확률을 계산하는 것입니다. 제가 축구를 잘 몰라서 총 경기시간이 90분이라는 것도 몰랐네요. 한 100분 하는 줄 알았네요. 아주 단순한 확률 계산만 하면 됩니다. 어떤 사건이 일어날 확률이 \(p\) 라고 한다면, 18번안 에 k번 해당 사건이 일어날 확률은 이산확률로 계산이 됩니다. \[ P(k) = _{18}C_k p^k (1-p)^{18-k} \] 18 이하의 소수는 2, 3, 5, 7, 11, 13, 17 이 있으니까요. k값을 달리하면서 확률을 더해주면 됩니다. A팀과 B팀이 있으니까, 두 팀의 확률을 더하고, 두 팀이 동시에 소수 점수를 낼 확률을 빼주면 됩니다. Gold IV 난이도이긴 하지만 중학 수학 정도의 지식만 있으면 풀 수 .. 2020. 1. 30. #78 코인 나누기(Dynamic Programming) 코인 나누기는 유명한 문제 중 하나입니다. 동적 프로그래밍을 이용해서 구할 수 있는데, 그것을 하기 위해서는 수학적 기반 지식이 있어야 합니다. 코인 나누기라는 것은 N개의 코인을 가지고 코인 갯수를 나누는 방법의 수를 구하는 것입니다. 또는 무한정의 1$, 2$, 3$, .., N$ 코인으로 N$를 만드는 방법의 수라고 할 수도 있습니다. 예를 들어서 코인이 5개 있다면, 아래의 그림과 같이 7가지 방법으로 나눌 수 있습니다. 문제에서 요구하는 것은 이 경우의 수가 1,000,000으로 나누어 떨어지는 가장 적은 수를 구하라는 문제입니다. 단순하게 N에 대해서 경우의 수를 구하는 문제였다면 크게 어렵지 않았을겁니다. 난이도가 30%로 설정된 이유도 아마 비슷할 것이라고 봅니다. 수학적으로 본다면 다음과.. 2020. 1. 27. #1342 행운의 문자열(Back tracking) 이번 문제는 주어진 문자열에 대해서 인접하는 문자가 같은 경우가 없도록 배치할 수 있는 경우의 수를 출력하는 것입니다. 예를 들어서 aabb 란 문자열이 주어진다면, 서로 인접한 문자가 같지 않게 배치될려면, abab baba 두가지 경우가 가능하겠죠. 그러면 2를 출력하면 됩니다. 난이도는 Gold III인데, 딱히 어려운 문제라는 생각은 안 들었습니다. 제 경우에는 빈도를 계산해서, 그 빈도를 이용해서 백트래킹 기법을 이용해서 모든 경우를 계산했습니다. 동적 프로그래밍으로 중복을 줄여서 계산할 수도 있을 것 같기는 했지만, 그건 포기했습니다. 문자열 길이가 10밖에 안 되니까 어찌어찌 가능할 것 같기는 하지만요. 문자가 소문자로만 주어지는지 몰라서 처음에 빈도로 계산 안 하고, 정렬을 통해서 해결했었.. 2020. 1. 26. #1339 단어 수학(Mathematics) 이번 문제는 복면산과 비슷한 개념의 문제입니다. A~Z까지의 문자가 사용되며, 각각의 문자는 서로 다르면서 0~9까지의 숫자 중 하나가 사용될 수 있습니다. 복면산 문제들은 퍼즐 형태로도 나와서 아마 풀어본 분들이 많을겁니다. 대표적인 복면산 문제들이 몇가지가 있죠. 예를 들어서 아래 그림과 같이 "Send More Money"라는 문구를 가지고 만든 복면산은 널리 알려져 있습니다. 이번문제는 A~Z로 이루어진 여러개의 단어의 합을 최대로 하기 위해서 적절한 숫자를 대입해서 그 합을 출력하는 것입니다. 문제 자체는 아주 쉽고, 사실 풀이도 어렵지 않지만, 난이도 Gold IV 문제입니다. 제가 푼 방식은 단어가 나올 때마다, 각 자릿수의 문자를 기록하고, 그 합을 계산했습니다. 예를 들어서 ABC, BC.. 2020. 1. 26. #77 소수들의 합(Dynamic Programming, Back tracking) 이번 문제는 난이도 25%로 설정되어 있지만, 워낙 작은 숫자들로 이루어져 있기 때문에 어렵지 않게 풀 수 있습니다. 10을 소수들의 합으로 표현한다면, 다음과 같이 총 5가지로 표현할 수 있습니다. 동일한 소수를 여러번 쓰는 것이 가능하고, 순서없는 조합으로 표현했을 때입니다. 아래와 같이 큰 소수부터 차례대로 나열할 수도 있고, 소수의 빈도만 따져도 됩니다. 이러한 경우의 수가 5,000이 넘는 가장 가장 작은 수를 찾으라는 것이 문제입니다. 사실 어떤 수가 주어졌을 때, 경우의 수를 따지는 것은 크게 어렵지 않습니다. 백트랙킹 방법을 이용해서 풀 수도 있고, 동적 프로그래밍을 이용해서 풀 수도 있습니다. 하지만 경우의 수가 특정수를 넘는 가장 작은 수를 찾는 것은 동적 프로그래밍으로는 조금 한계가 .. 2020. 1. 24. 이전 1 ··· 40 41 42 43 44 45 46 ··· 76 다음 728x90
