본문 바로가기
반응형

algorithm10

#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.
#1309 동물원(Dynamic Programming) 이번 문제는 Silver I 문제입니다. 이 문제를 풀기 위해서는 적절한 식을 세워야 하는데, 이것이 어느정도 훈련이 되지 않으면, 어렵습니다. 동적 프로그래밍은 점화식이 주어지지 않는 경우가 많습니다. 사실 동적 프로그래밍 뿐만 아니라 분할정복 관련된 문제들이 대부분 그렇습니다. 문제에서 식을 유도하고, 그 식을 수학적으로 정리하는 것이 필요합니다. 문제 난이도는 높지 않지만, 수학적으로 식을 유도하고, 정리하는 것이 필요해서 그 과정을 설명하고자 합니다. 2xN 동물원에 사자를 배치하는데, 가로와 세로로 연달아 배치 못하게 하는 경우의 수는 얼마인가가 문제입니다. 2칸씩 N개가 세로로 배치되는 것이니까, 2칸에 대해서 나올 수 있는 상태는 사자가 하나도 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 .. 2020. 1. 19.
알고리즘 기초 알고리즘이란? 알고리즘이란 "문제 해결 절차를 체계적으로 기술"한 것입니다. 그러면 알고리즘에서 말하는 문제는 무엇일까요? 알고리즘에서 말하는 문제는 주어지는 입력이 있다면, 그 입력에 맞는 출력을 내는 것을 말합니다. 문제에는 입력과 출력이 명시되어야 하며, 어떤 출력을 원하는지 문제에서 충분히 설명되어야 합니다. 입출력의 예로 들어볼께요. 문제 해결 절차를 체계적으로 기술한다는 의미는 입력을 받아서, 그 입력을 바탕으로 출력을 만드는 기술을 의미합니다. 2020. 1. 15.
#1256 사전(Combination Digit) 이번 문제는 사실상 조합을 찾아내는 문제입니다. 그런데 조합을 찾기 위한 숫자가 좀 큽니다. 그래보았자, 100이지만요. 난이도는 Gold IV입니다. 정답률은 28.5%이긴 하지만, 크게 어렵지 않았다고 생각했습니다. 문제의 내용을 정리하자면, N개의 a 문자와 M개의 z 문자를 조합하여 사전순으로 배열할 때, K번째 문자열을 출력하는 문제입니다. 예를 들어서 3개의 a와 2개의 z가 있다면 다음과 같이 사전순으로 나열할 수 있습니다. aaazz aazaz aazza azaaz azaza azzaa zaaaz zaaza zazaa zzaaa 이렇게 해서 총 10개의 문자열이 나옵니다. 10개의 문자열이 나온 이유는 5개의 공간 중에 2개의 공간을 선택해서 그곳에 z를 채우고, 나머지 공간에는 a로 채우.. 2020. 1. 13.
백준 #1253 좋다 이 문제는 처음에 Gold III로 난이도가 설정되어 있어서 왜 이렇게 높지 했습니다. 정답률도 20.8%로 낮아서, 정답률도 상당히 낮네하면서 설마하고 제출했는데, 틀렸습니다가 나오네요. N 개의 수가 주어지는데, 자신을 제외한 다른 두개의 수의 합으로 자신이 이루어지면, 이 수의 개수를 출력하는 문제입니다. https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 가장 편하게 생각하는 것은 두개의 수 조합으로 set 자료형에 넣고서, 수가 이 set에 있는지 검사하는 방법입니다.. 2020. 1. 11.
728x90

티스토리툴바