본문 바로가기
반응형

BOJ50

#1407 2로 몇 번 나누어질까(Mathematics) 이번 문제는 주어진 수 n를 나눌 수 있는 최대 2의 거듭제곱수를 구하고, 일정 범위의 수에 대하여 그 거듭제곱수의 합을 구해야 하는 문제입니다. 난이도는 Gold IV로 높지는 않습니다. n이란 수가 12라면 12를 나눌 수 있는 최대 2의 거듭제곱수는 4이므로 f(12) = 4가 됩니다. 또는 다음과 같이 해도 됩니다. n이란 수를 나눌 수 있는 최대 2의 거듭제곱수는 n을 2진수로 표현했을 때, 가장 오른쪽 1의 위치이다와 동일합니다. 12는 2진수로 1100이므로, 가장 오른쪽 1을 찾게되면 2진수로 100이 되고, 이 값은 4가 됩니다. 그리고 이것을 C 언어에서는 비트연산자를 이용해서 간단하게 계산할 수 있습니다. x & (-x) 를 계산하면 가장 오른쪽 비트를 얻게 됩니다. 하지만 이 문제는.. 2020. 2. 26.
#1405 미친 로봇(Full Search, Back Tracking) 이번 문제는 경로를 다니면서, 지나온 길을 거치지 않을 확률을 계산하는 것입니다. 난이도 Gold V로 어렵지는 않은 문제이고요. 복잡한 알고리즘이 아니라, 단순한 백트랙킹을 구현하면 됩니다. 동서남북으로 움직일 수 있는 확률이 주어지고, 동서남북으로 확률적으로 N칸 움직였을 때, 지나온 경로를 다시 방문하지 않는 경로로 움직일 확률이 얼마일까를 계산하는 문제입니다. 예를 들어서 로봇이 NESW로 순차적으로 움직였다면, 원위치로 돌아왔으니, 지나온 경로를 지나게 됩니다. NNES 라던지, SWWS 와 같은 경로는 4칸을 움직이면서 지나온 경로를 지나지 않는 움직임이 됩니다. 문제를 풀기 위해서는 BFS, DFS 들 중 어떤 것을 사용하든 상관이 없습니다. 전 편한 DFS를 사용했습니다. 최대 움직임은 1.. 2020. 2. 23.
#1395 스위치(Segment Tree) 이번 문제는 Platinum III 난이도로 매겨진 좀 난이도가 있는 문제입니다. 기본적으로 이용하는 자료구조는 세그먼트 트리입니다. 세그먼트 트리 자료구조는 제가 나중에 한번 알고리즘적 적용 방법에 대해서 이야기하고자 합니다. 백준 사이트에서 세그먼트 트리와 관련된 문제가 꽤 여러개가 보입니다. 다 난이도가 높게 책정된 문제들입니다. 그런데 세그먼트 트리는 하나의 데이터를 업데이트할 때, \(O(\log N)\) 의 데이터 효율을 가집니다. 그리고 범위에 대해서 연산결과를 내는 것도 역시 \(O(\log N)\)의 효율을 보입니다. 그런데, 범위로 데이터를 업데이트한다고 할 때에는 이게 쉽지 않습니다. 해당 범위내의 것을 모두 업데이트를 일일이 한다고 하면, 세그먼트 트리를 쓰지 않고 배열 자료구조가 .. 2020. 2. 14.
#1353 합과 곱(Mathematics, Binary Search) 이번 문제는 Platinum V 난이도로 설정된 문제입니다. 정답자도 39명뿐입니다. 난이도에 비해서 많이 풀지 않은 문제입니다. 수학적 지식으로는 산술평균과 기하평균의 대소 비교만 알고 있으면 쉽게 풀 수 있습니다. 수열 A가 있는데, 이 수열에 있는 수들을 합하면 S, 곱하면 P의 값을 가집니다. 예를 들어서 { 1, 3, 2 } 수열이라면, S=6, P=6이 됩니다. 문제는 이러한 S와 P가 주어질 때, 만족하는 양의 실수 수열의 최소 크기를 구하라는 것입니다. 문제에서는 음이 아닌 실수이지만, P의 범위가 1 이상이므로 양의 실수만 생각해도 됩니다. S=6, P=6 이라면, { 1, 3, 2 } 도 되지만, { 6 } 도 가능하므로, 최소 수열의 수 갯수는 1이 됩니다. 이 문제를 풀기 위해서는 .. 2020. 2. 1.
#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.
728x90

티스토리툴바