본문 바로가기
반응형

알고리즘63

#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.
#1300 K번째 수 (이분탐색) k번째 수를 찾는 문제는 알고리즘 강의 시간에 시험문제로 나온 적이 있습니다. 퀵정렬 알고리즘을 가지고 k번째 원소를 찾는 문제였습니다. 사실 C++에 k번째 수를 찾는 함수를 제공하고 있으니, 이를 이용하면 아주 쉽게 찾을 수 있습니다. 가장 쉽게 풀 수 있는 방법은 정렬한 후에 k번째 원소를 출력하면 되겠지만, 이것은 너무 뻔한 이야기겠죠. 문제에서도 정렬한 다음에 K번째 수를 찾는다고 이야기가 나와있습니다. 이렇게 뻔한 방법으로 문제를 풀라는 것은 당연히 아닙니다. 숫자의 범위가 꽤 큽니다. \(10^{10}\) 이니까, 그러면 int 자료형을 예상했을 때, 자료저장공간만 해도 \( 4 \times 10^{10} \) 이니까, 128MB 메모리 제한에 당연히 걸립니다. 자료공간에 필요한 40GB 입.. 2020. 1. 16.
알고리즘 기초 알고리즘이란? 알고리즘이란 "문제 해결 절차를 체계적으로 기술"한 것입니다. 그러면 알고리즘에서 말하는 문제는 무엇일까요? 알고리즘에서 말하는 문제는 주어지는 입력이 있다면, 그 입력에 맞는 출력을 내는 것을 말합니다. 문제에는 입력과 출력이 명시되어야 하며, 어떤 출력을 원하는지 문제에서 충분히 설명되어야 합니다. 입출력의 예로 들어볼께요. 문제 해결 절차를 체계적으로 기술한다는 의미는 입력을 받아서, 그 입력을 바탕으로 출력을 만드는 기술을 의미합니다. 2020. 1. 15.
728x90

티스토리툴바