본문 바로가기

전체 글

리스트의 각 원소를 복제하기 원문 : https://www.hackerrank.com/challenges/fp-list-replication/problem 이번 문제는 리스트 복제와 관련된 문제이다. replicate를 이용해서 특정한 타입의 값을 N회 반복하는 리스트로 만드는 것을 응용한다. 문제에서는 아래와 같은 스텁이 주어진다. main :: IO () main = getContents >>= mapM_ print . (\(n:arr) -> f n arr) . map read . words f n arr = -- implement this function 접근 일단 문제에 집중하자. 문제는 일련의 숫자가 (한 줄에 하나씩) 주어졌을 때, 맨 첫 숫자만큼 각 숫자를 반복한 리스트를 만드는 것이다. 편의상 한 칸에 하나의 숫자를 .. 더보기
헬로월드 X N 이번 문제는 hello world를 N번 찍는 문제이다. "간단한" 반복문 문제인데, 함수형 언어에서 반복문이라는게 있던가? 재귀적인 접근 함수형 언어에서는 반복문 대신에 함수의 재귀호출로 이를 대신한다. 따라서 다음과 같이 재귀호출을 이용한 함수를 생각해볼 수 있다. 이러한 패턴은 함수형 언어에서 반복문을 대체하는 가장 기본적인 패턴이다. sayHello :: Int -> IO () sayHello 0 = return () sayHello n = do putStrLn "Hello World" sayHello (n-1) 아래와 같이 확인해볼 수 있다. main :: IO () main = do n m a -> m [a]이다. Applicative 속성의 타입 a를 N번 반복해서 리스트로 만들어준다는 것인.. 더보기
입력된 두 정수의 합을 출력 출처 : https://www.hackerrank.com/challenges/fp-solve-me-first/problem 두 정수를 입력받아서 그 합을 출력하세요.A, B는 1~1000 사이의 정수 입력: 2 3출력: 5 입력받기 getLine을 사용하면 키보드로부터 한 줄의 텍스트를 입력받을 수 있다. 이렇게 입력받은 텍스트는 IO 모나드로 싸여진 IO [Char] 타입이 된다. 이를 read 함수로 읽어서 IO Int로 만든다음, do 블럭 내에서 바인딩하여 더한 후 출력한다. main = do val1 A 함수를 쓰는데 모나드에 싸여있는 내부에 사상해야 해서 fmap 함수를 이용했다. fmap은 연산자로는 로 대체하여 쓸 수 있다. readLn 함수 한 줄을 읽어들여서 라인의 값을 read 하는 .. 더보기
특별한 규칙을 갖는 0-9 팬디지털 숫자찾기 2 이전 글 에서 언급된 문제와 유사한 문제가 오일러 프로젝트에 있어서 같은 방법으로 풀어보고자 한다. 숫자 1406357289는 0-9팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다. d1을 첫째자리수, d2를 둘째자리수...라고 했을 때 다음과 같은 재미있는 사실을 발견할 수 있습니다. d2d3d4 = 406 : 2로 나눠짐 d3d4d5 = 063 : 3으로 나눠짐 d4d5d6 = 635 : 5로 나눠짐 d5d6d7 = 357 : 7로 나눠짐 d6d7d8 = 572 : 11로 나눠짐 d7d8d9 = 728 : 13으로 나눠짐 d8d9d10 = 289 : 17로 나눠짐 위와 같은 성질을 갖는 0~9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?(출처 : 오일러프로젝트 43 - http:.. 더보기
0부터 9까지의 수를 사용해 규칙에 맞는 수를 만들기 0부터 9까지 10개의 숫자를 모두 사용해서 규칙에 맞는 수를 만드는 문제이다. 규칙은 단순하다. 원문: http://blog.naver.com/PostView.nhn?blogId=kyaryunha&logNo=220923287298 첫번째 숫자까지 1로 나눠진다. 두번째 숫자까지 2로 나눠진다. ... n번째 숫자까지 n으로 나눠진다. 그리고 이 숫자는 0-9 팬디지털 숫자이므로 같은 숫자를 두 번 쓸 일은 없다. 원문에서는 C로 코드를 작성한 거 같던데 5분 내외에 답을 구하고 있다. 여기서는 파이썬으로 풀이해본다. 팬디지털 숫자이므로 1,023,456,789~9,876,543,210까지의 범위를 루프로 돌기보다는 각자리에 사용될 숫자를 추출해서 돌아본다. 여기서 사용된 숫자를 피해서 추출하는 로직을 .. 더보기
소인수분해하기 소인수분해와 약수의 개수 어떤 자연수 n을 소인수 분해하였을 때 나오는 소인수의 모든 지수에 1을 더하고, 그 값들을 모두 곱하면 n의 약수의 개수가 된다. 이는 n의 모든 약수는 각각의 소수인 인수 a, b, c.... 들을 0번에서 각 지수번까지 사용한 조합을 만드는 것과 동일하기 때문이다. 따라서 어떤 자연수 n을 소인수 분해 할 수 있다면 그 약수의 개수를 빠르게 계산할 수 있을 것이다. 문제 오일러 프로젝트 12번 문제는 약수의 개수를 빠르게 구하는 것에 중점을 두는 문제이다. 1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라 합니다. 예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 입니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다. 1, 3.. 더보기
(파이썬) 소수 판별하기 소수판별하기 소수(Prime number)는 1과 자기자신만을 약수로 가지는 양의 정수를 말한다. 2, 3, 5, 7, 11, 13... 등의 수이다. 어떤 수가 소수인지 판단하는 방법에 대해 알아보자. 가장 간단하게 소수의 정의로부터, 어떤 자연수 N이 소수인지를 살펴보려면 N 이 1 이면 소수가 아니다. 2 부터 N-1 까지의 자연수들로 순서대로 N을 나눠서 나누어 떨어지는 수가 하나도 없으면 N은 소수이다. 라는 간단한 검사 규칙을 얻을 수 있다. 기본적으로 이 규칙을 그대로 적용하여 코드로 옮겨보면 생각보다 매우 간단한 함수가 만들어진다. def is_prime_bad(n: int) -> bool: if n < 2: return False for i in range(2, n): if n % i i.. 더보기
완전수와 초과수 (약수의 합 구하기) 완전수와 초과수 어떤 자연수 N의 자기 자신보다 작은 양의 약수들의 합이 자기 자신과 같다면 그 수를 완전수라하고, 만약 약수의 합이 N보다 크다면 초과수라고 한다. 6은 가장 작은 완전수로, 6의 약수는 1, 2, 3, 6이며, 이중 6 자신을 제외한 세 수의 합은 6으로 원래의 값과 일치한다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 12를 제외한 약수의 합은 16으로 12는 초과수이다. 약수의 합을 구하는 방법은 크게 두 가지가 있다. 무식하게 1부터 N까지의 수로 N을 나눠서, 나눠지는 수가 약수이므로 이들을 모두 합산한다. N을 소인수분해하여, 각 인수의 누적 거듭제곱의 합들을 구하고, 다시 이들의 누적 곱을 구한다. (수학 시간에 약수의 합을 구하는 공식이라고 배웠다.) 컴퓨터를 이.. 더보기

티스토리툴바