Programming456 [C/C++] 백준 #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. [C/C++] 백준 #1015 수열 정렬 이번 문제는 정렬 문제입니다. 정렬은 알고리즘에서 가장 기초로 배우고 있지만, 속속들이 다 배우지는 않고 있습니다.일반적으로 기본정렬에 속하는 선택정렬, 삽입정렬, 버블정렬과 고급정렬에 속하는 병합정렬, 퀵정렬, 힙정렬들을 배우고 있지만, 성능과 관련된 항목을 주로 가르치죠. 정렬에는 또 한가지 고려사항이 있는데, 입력된 데이터의 순서를 지켜주느냐 아니냐도 있습니다. 동일한 데이터가 있는 경우 순서를 지켜주는 정렬과 아닌 정렬이 있다는 것이죠. 사실 실제 프로그램 작성할 때에는 거의 무시할 수 있는 내용입니다만, C++ 기본 라이브러리에 stable sort가 있는 것으로 보아서 필요성은 있을거라고 봅니다. 문제는 다음 링크와 같습니다.https://www.acmicpc.net/problem/101.. 2019. 12. 23. [C/C++] 백준 #1012 유기농 배추 텃밭에 배추가 심어져 있는데, 유기농으로 배추를 기르기 위해서 배추 흰지렁이를 풀어놓고자 합니다. 배추 흰지렁이는 배추가 모여있는 곳에는 한마리만 풀어놓아도, 인접한 배추로 옮겨다니면서 해충을 예방할 수 있습니다. 이 문제는 섬의 갯수 문제 등 자주 나오는 문제로, 그래프 이론 중 가장 기초적인 DFS, BFS 알고리즘을 이용해서 해결할 수 있습니다. 아래는 백준 사이트의 문제 링크입니다.https://www.acmicpc.net/problem/1012 1012번: 유기농 배추차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 .. 2019. 12. 22. [C/C++] 백준 #1011 Fly me to the Alpha Centauri 이번 문제는 알파 센타우리까지 우주선을 타고 갈 때, 워프기계는 최소 몇번 작동으로 갈 수 있는지 구하는 문제입니다.우주적인 문제이지만, 사실상 거리의 절반까지 가는데, 1+2+3+...+k 의 값이 거리의 절반보다 작으면서 가장 큰 수가 되는 것을 구하는 문제입니다. 알파 센타우리는 지구로부터 4.37 광년정도 떨어져 있습니다. 우주선이 빛의 속도로 가도 4.37년이 걸리는 곳입니다.태양과는 주계열성으로는 가장 가까운 별이라서 지구에서 관측할 때 아주 밝게 빛나는 별입니다만, 아쉽게도 우리나라가 있는 위도상에서는 관측이 힘듭니다. 영화에서도 새로운 지구로 자주 쓰이는 별입니다. 영화 패신저스에서도 알파 센타우리가 쓰였죠. 가는데 백여년이 걸려서 사람을 동면시켜서 갑니다. (사실상 그곳까지 가는.. 2019. 12. 22. #73 범위안의 분수 세기 이 문제는 난이도 15% 정도의 문제입니다. 범위안의 분수를 세는 문제인데요. 프로젝트 오일러 #72 문제와 마찬가지로 분모의 범위가 주어지고, 그 안에서 1/3 와 1/2 사이의 분수의 갯수를 구하는 것입니다. 기약분수라는 조건이 달려있습니다. 즉, 1/3 와 1/2 사이에 2/5, 4/10, 6/15, .. 분수들이 있는데, 4/10, 6/15는 모두 2/5와 같은 분수이기 때문에 카운팅을 하면 안 됩니다. 프로젝트 오일러 #73 문제는 아래의 링크를 참조하세요. https://projecteuler.net/problem=73 Problem 73 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n p.. 2019. 12. 21. [C/C++] 백준 #1010 다리 놓기(조합) 백준 #1010 다리 놓기 문제는 수학 중 확통의 경우의 수에 어느정도 개념이 있어야 풀 수 있는 문제입니다. 강을 사이로 왼쪽에는 N 개의 지역, 오른쪽에는 M 개의 지역이 있습니다. 이 N개의 지역에 하나씩 다리를 놓아서 오른쪽에 있는 M개의 지역을 연결하고자 하는데, 다리가 서로 엇갈리지 않도록 하는 경우의 수를 물어보고 있습니다. 경우의 수를 따지는 데에는 순열과 조합이 있는데, 이와 같이 엇갈리지 않게, 즉, 항상 정해진 순서대로(또는 증가하는 순서, 감소하는 순서 등) 나열해야한다면, 이것은 조합을 선택해야 합니다. 결국 이 문제는 M개 중에서 N개를 선택하는 문제가 되겠죠. 실제 백준 문제는 다음 링크를 봐주세요.https://www.acmicpc.net/problem/1010 101.. 2019. 12. 21. 이전 1 ··· 50 51 52 53 54 55 56 ··· 76 다음 728x90
