본문 바로가기
반응형

알고리즘63

백준 #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.
백준 #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.
프로젝트 오일러 #71 순서가 있는 분수 어려움 정도는 10%로 크게 어려움 없이 풀 수 있는 문제입니다. 분수문제가 연속으로 3문제가 나와있는데, 기약분수를 만드는 것만 잘 이해하면 풀 수 있는 문제들입니다. 아래는 이 문제의 원문이 있는 곳입니다. https://projecteuler.net/problem=71 Problem 71 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 분수를 표현하는 방법은 여러가지가 있을 수 있습니다. 그 중 유일한 표현법을 얻기 위해서 기약분수를 사용합니다. 기약분수로 표현을 할 때, 우리는 분수의 크기를 비교할 수 있죠. 그런데, 분모의 상한을 주게되면, 자연수를 나열하듯이 .. 2019. 11. 18.
728x90

티스토리툴바