반응형 Project Euler42 #79 암호 알아내기(Topology Sort) 이번문제는 난이도 5%로 아주 쉬운 문제로 분류되어 있습니다. 아마 단순무식(Brute Force) 방법으로도 풀리는 문제로 분류되어서인 듯 합니다. 숫자가 많지 않기 때문에 단순하게 조건에 맞도록 배열하는 것이 가능합니다. 예를 들어서 317 236 이 있다면, 총 숫자는 5가지 숫자가 쓰였으므로 5가지 숫자를 적절하게 배열한 다음에 조건에 맞는 수열을 고르는 것입니다. 일단 문제를 살펴본다면 다음과 같습니다. 주어진 숫자가 있습니다. 예를 들어서 531278이란 숫자가 있다면요. 이 숫자를 가지고 있음을 확인하면서, 네트웍 전송상에서 원래의 숫자를 알아내기 힘들게 하기 위해서 첫번째, 세번째, 다섯번째 숫자를 보내길 요구할 수 있습니다. 그러면 517을 전송하게 됩니다. 그런데 이러한 전송이 많아지면.. 2020. 2. 8. #78 코인 나누기(Dynamic Programming) 코인 나누기는 유명한 문제 중 하나입니다. 동적 프로그래밍을 이용해서 구할 수 있는데, 그것을 하기 위해서는 수학적 기반 지식이 있어야 합니다. 코인 나누기라는 것은 N개의 코인을 가지고 코인 갯수를 나누는 방법의 수를 구하는 것입니다. 또는 무한정의 1$, 2$, 3$, .., N$ 코인으로 N$를 만드는 방법의 수라고 할 수도 있습니다. 예를 들어서 코인이 5개 있다면, 아래의 그림과 같이 7가지 방법으로 나눌 수 있습니다. 문제에서 요구하는 것은 이 경우의 수가 1,000,000으로 나누어 떨어지는 가장 적은 수를 구하라는 문제입니다. 단순하게 N에 대해서 경우의 수를 구하는 문제였다면 크게 어렵지 않았을겁니다. 난이도가 30%로 설정된 이유도 아마 비슷할 것이라고 봅니다. 수학적으로 본다면 다음과.. 2020. 1. 27. #77 소수들의 합(Dynamic Programming, Back tracking) 이번 문제는 난이도 25%로 설정되어 있지만, 워낙 작은 숫자들로 이루어져 있기 때문에 어렵지 않게 풀 수 있습니다. 10을 소수들의 합으로 표현한다면, 다음과 같이 총 5가지로 표현할 수 있습니다. 동일한 소수를 여러번 쓰는 것이 가능하고, 순서없는 조합으로 표현했을 때입니다. 아래와 같이 큰 소수부터 차례대로 나열할 수도 있고, 소수의 빈도만 따져도 됩니다. 이러한 경우의 수가 5,000이 넘는 가장 가장 작은 수를 찾으라는 것이 문제입니다. 사실 어떤 수가 주어졌을 때, 경우의 수를 따지는 것은 크게 어렵지 않습니다. 백트랙킹 방법을 이용해서 풀 수도 있고, 동적 프로그래밍을 이용해서 풀 수도 있습니다. 하지만 경우의 수가 특정수를 넘는 가장 작은 수를 찾는 것은 동적 프로그래밍으로는 조금 한계가 .. 2020. 1. 24. #76 합의 경우의 수(Dynamic Programming) 이번 문제는 경우의 수를 계산하는 것입니다. 보통 분할(partition) 문제는 중복조합, 조합, 순열 등의 기법이 사용될 수 있지만, 이 문제와 같은 경우에는 분할이 쉽지 않습니다. 문제는 짧은 편입니다. N이란 숫자가 주어지면, 1부터 N-1 까지의 숫자중 2개 이상을 선택해서 그 합이 N이 되도록 하는 경우의 수를 찾는 것입니다. 예를 들어서 N=5라고 한다면, \( 5 = 1 + 1 + 1 + 1 + 1 \) \( 5 = 1 + 1 + 1 + 2 \) \( 5 = 1 + 1 + 3 \) \( 5 = 1 + 4 \) \( 5 = 1 + 2 +2 \) \( 5 = 2+ 3 \) 위와 같이 총 6가지가 나옵니다. 이 문제에서는 N=100일 때의 경우의 수가 얼마인지 계산하라는 문제입니다. 문제의 원본.. 2020. 1. 15. #75 단일길이 정수 직각 삼각형 이번 문제는 피타고라스 삼각형을 만들고, 그것을 에라스토테네스의 체처럼 사용하는 문제입니다. 난이도 25% 문제입니다. 하지만, 피타고라스 삼각형을 만드는 공식만 알면 크게 어려움 없이 풀 수 있는 문제입니다. 이 프로그램을 작성할 때만 해도 STL을 거의 사용하지 않았을 때인지라 무식하게 배열을 사용했지만, STL의 map 자료형을 사용하면 더 쉽게 풀 수 있을거라고 보입니다. 문제를 간단하게 요약하자면 다음과 같습니다. 변의 길이가 정수인 직각삼각형이 있습니다. 둘레 길이가 주어졌을 때, 어떤 정수 직각 삼각형은 여러개가 나올 수 있습니다. L < 1,500,000 인 둘레길이를 가지면서, 해당 둘레에서 그러한 정수 직각삼각형이 오직 한개인 개수를 구하세요. 문제의 원본은 다음과 같습니다. https.. 2020. 1. 14. #74 자릿수 팩토리얼 연결 고리 10진수의 수를 각각의 자릿수를 분해해서 재조합하다보면 재미있는 수를 얻을 수 있습니다. 예를 들어서 145라는 수를 분해해서 팩토리얼을 취한후 합해보면, \(145 \to 1! + 4! + 5! = 1+24+120=145\)라는 결과를 얻게 됩니다. 이와 같이 같은 수가 나올 수 있지만, 어떤 수는 위의 작업을 반복하다보면, 자신의 수가 되기도 하고 중간에 나왔던 수가 되어 싸이클을 반복할 수도 있습니다. 이 문제는 이러한 수들의 연결고리가 반복되기 전까지 얼마나 오래 가는가에 대한 문제입니다. 난이도 15% 정도로 구현에 어려움이 없는 문제입니다. 문제의 링크입니다. https://projecteuler.net/problem=74 Problem 74 - Project Euler The number 1.. 2019. 12. 27. 이전 1 2 3 4 ··· 7 다음 728x90
