본문 바로가기
반응형

백준144

백준 #1016 제곱 ㄴㄴ수 이번 문제는 1을 제외한 제곱수로 나누어 떨어지는 수를 구하는 것입니다. 에라토스테네스 체의 확장판이라고 생각하시면 될 것 같네요. 그리고 숫자의 범위는 작지만 숫자 자체가 꽤 커서 소수를 꽤 많이 구해야 합니다. 어떤 수 \(n\)이 소수인지는 \(O(\sqrt{n})\)의 복잡도로 판단할 수 있어서, 숫자가 \(10^{12}\) 오더이긴 하지만 제곱수이기 때문에 실제 구해야할 소수는 \(10^6\) 오더입니다. 계산량으로 보면 제한시간의 절반 이하로 가능합니다. 그런데 정답비율은 18%로 아주 낮습니다. 문제는 아래의 링크에 있습니다. https://www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,.. 2019. 12. 24.
백준 #1012 유기농 배추 텃밭에 배추가 심어져 있는데, 유기농으로 배추를 기르기 위해서 배추 흰지렁이를 풀어놓고자 합니다. 배추 흰지렁이는 배추가 모여있는 곳에는 한마리만 풀어놓아도, 인접한 배추로 옮겨다니면서 해충을 예방할 수 있습니다. 이 문제는 섬의 갯수 문제 등 자주 나오는 문제로, 그래프 이론 중 가장 기초적인 DFS, BFS 알고리즘을 이용해서 해결할 수 있습니다. 아래는 백준 사이트의 문제 링크입니다. https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이.. 2019. 12. 22.
백준 #1011 Fly me to the Alpha Centauri 이번 문제는 알파 센타우리까지 우주선을 타고 갈 때, 워프기계는 최소 몇번 작동으로 갈 수 있는지 구하는 문제입니다. 우주적인 문제이지만, 사실상 거리의 절반까지 가는데, 1+2+3+...+k 의 값이 거리의 절반보다 작으면서 가장 큰 수가 되는 것을 구하는 문제입니다. 알파 센타우리는 지구로부터 4.37 광년정도 떨어져 있습니다. 우주선이 빛의 속도로 가도 4.37년이 걸리는 곳입니다. 태양과는 주계열성으로는 가장 가까운 별이라서 지구에서 관측할 때 아주 밝게 빛나는 별입니다만, 아쉽게도 우리나라가 있는 위도상에서는 관측이 힘듭니다. 영화에서도 새로운 지구로 자주 쓰이는 별입니다. 영화 패신저스에서도 알파 센타우리가 쓰였죠. 가는데 백여년이 걸려서 사람을 동면시켜서 갑니다. (사실상 그곳까지 가는 기술.. 2019. 12. 22.
백준 #1009 분산처리 분산처리 문제는 무식하게 풀려면 얼마든지 풀 수 있지만, 효율적인 동작을 위해서는 정수론이 필요합니다. 문제 자체는 이해 자체가 어렵지는 않습니다. 데이터가 N개 있는데, 10대의 컴퓨터로 순차적으로 데이터 1개씩을 처리할 경우, 마지막 데이터를 처리하는 컴퓨터는 어떤 것이 될 것인가가 문제입니다. 아래는 이 문제의 링크입니다. https://www.acmicpc.net/problem/1009 그런데 여기서 주어진 N이란 숫자가 두개의 숫자 a, b 가 주어졌을 때, \(a^b\)이란 것입니다. 더구나 a 의 범위는 100까지이고, b란 범위는 1,000,000 까지입니다. 나머지 연산을 할 경우, 밑수를 나머지 연산을 할 수 있지만, 지수를 나머지 연산하는 것은 중학 수학 범위에서는 벗어납니다. 그래도.. 2019. 12. 20.
#1007 벡터 매칭(Mathematics) 이 문제는 Gold II 문제입니다. 처음에는 동적 프로그래밍을 이용한 TSP프로그램인 줄 알고 열심히 짰다가, 예제 결과가 틀렸길래 뭐지 하고 봤었네요. 제가 문제를 풀 때만 해도 Gold I 문제였는데, 그동안 난이도가 떨어졌네요. 어쩐지 벡터 매칭이 문제 이름인데, TSP 문제일리가 없었죠. 그리고 TSP 문제였다면 조금 더 난이도 값이 주어졌을 것 같네요. TSP 문제였다면, 비트매스킹을 써서 동적 프로그래밍으로 답을 해야하죠. 그 귀찮은 프로그래밍을 다 했었는데. 최대 점들의 갯수가 20개이므로, TSP 문제였다고 해도 시간안에 대충 풀었을 듯 합니다. 문제는 2차원 공간상에 점들이 주어지면, 이 점들중 두개씩 짝을 이루어 벡터를 만들었을 때, 그 벡터들의 합이 최소가 되도록 하는 것입니다. 문.. 2019. 12. 20.
백준 #1003 피보나치 함수 이 문제는 6개월전에 백준 문제들을 본격적으로 풀면서 풀었던 문제입니다. 난이도는 Silver III 문제입니다. 피보나치 함수는 아주 간단한 구조를 가지고 있는데, 다양한 성질 등이 발견되면서 자주 거론되는 수열입니다. C/C++ 언어를 배울 때에는 재귀함수(자기호출함수)의 개념을 익히는 데에 하노이 타워와 자주 거론됩니다. 이 문제는 정답률이 높은 편은 아닙니다. 아마 초기문제여서 그럴 수도 있겠네요. https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치 수열은 초기화 값에 따라서 수열이 조금씩 틀려지는데요. fib(0) = 0, f.. 2019. 12. 16.
728x90

티스토리툴바