본문 바로가기
반응형

프로젝트 오일러69

20. 프로젝트 오일러 #20 : 100!의 모든 자릿수 합 구하기 알고리즘에서 가장 큰 알고리즘을 분류하는 것 중에, 기하급수보다 더 큰 것이 있다면, 모든 경우의 수를 조사하는 팩토리얼(factorial)일겁니다. 뭐 이것보다 더 큰 것도 있을 수 있는데요. 예를 들면, 연제곱승(제곱승에 제곱승이 이어나가는)이 있지만, 이런 알고리즘은 거의 보기 힘듭니다. 연제곱승과 반대되는 것으로는 연로그(로그 안에 로그가 있는 형태)이거나, 연로그가 일정한 값이 되는 로그의 갯수 등입니다. 정확한 용어는 제가 모르지만, 힙정렬에서 힙을 만드는 과정에 이런 개념이 나옵니다. 사실 정렬에서 우리는 일반적으로 이라고 알고 있지만요. 사실 더 본격적으로 들어가면, n개가 배열될 수 있는 경우의 수를 매번 2가지 경우로 나누어져서 찾아서 정렬하는 방법이기 때문에, 최적의 정렬 알고리즘의 .. 2015. 1. 17.
19. 프로젝트 오일러 #19 : 20세기의 매달 1일이 일요일인 수 계산하기 이 문제는 윤년을 올바르게 찾을 수 있는가를 찾아내는 문제라고 생각합니다. C/C++ 에서는 time.h 헤더 파일에 있는 mktime() 함수를 이용하면 손쉽게 풀 수 있는 문제이기도 하죠. 그러나 저는 조금 다르게 찾아볼려고 노력을 했습니다. (mktime() 함수를 이용하면 윤초 계산도 들어가는지, y년 m월 1일 0시 0분 0초의 요일이 다르게 나오네요. 1시로 옮기니 정확하게 나옵니다.) 사람들에게 1년 주기는 어떤 기준인가를 물어보면, 올바르게 아는 사람들은 적습니다. 아마 많은 분들은 지구가 태양 주위를 한바퀴 도는데 걸리는 시간이라고 생각할겁니다. 아, 아니었나요? 반문하시는 분들도 계실 것 같네요. 정확하게는 춘분점에서 다음번 춘분점까지 걸리는 시간이 1년입니다. 지구가 태양을 한바퀴 돌.. 2015. 1. 17.
18. 프로젝트 오일러 #18 : 삼각형 수들의 최대값 경로 구하기 이번 프로그램은 개인적으로도 재미있을 것 같았습니다. 가장 중요한 알고리즘은 바로 동적 프로그래밍(Dynamic Programming)입니다. 실제 경로 문제 중 최적값 찾기에는 동적 프로그래밍 기법을 자주 사용하게 되는데, 이 프로그램 역시 마찬가지입니다. 해당 사이트 문제에서도 그런 점을 언급하기는 했지만, 동적 프로그래밍을 사용하지 않는다면, 경로의 수가 많은 경우에는 매우 많은 연산을 하게 됩니다. 이번 문제는 경로의 수가 16,384가지가 나옵니다. 왜냐하면 각 층의 숫자마다 경로가 2가지씩 나오니까요. 총 15층이므로, 총 경로의 수는 가 됩니다. 그러나 동적 프로그래밍을 이용하면, 실제 경로의 수 계산은 총 숫자의 갯수인 120가지밖에 안 됩니다. #67 문제에 100층짜리 문제가 나온다고 .. 2015. 1. 14.
17. 프로젝트 오일러 #17 : 영어 단어의 글자수 세기. 이번 문제는 문제 자체의 난이도보다는, 영어 단어를 세는 것 자체가 너무 짜증났던 문제입니다. 그리고 우리가 보통 사용하지 않는 'and'까지 쳐서 해주어야 하니까요. 답을 썼는데 계속 틀리다고 나와서, 왜 그런가 했더니, 제가 글자수 하나를 더 쳤네요. 18 과 80 때문에 둘다 그랬네요. 단순하게 8(eight) + 'teen' 과 8(eight) + 'ty' 로 해서 5+4, 5+2 했던 것이 문제였네요. 그냥 #1 부터 계속 풀어보자 생각했던터라, 이 문제를 풀고 싶지는 않았지만, 그냥 풀어 보았습니다. #include int main() { int wc[20] = { 0, 3, 3, 5, 4, 4, 3, 5, 5, 4, 3, 6, 6, 8, 8, 7, 7, 9, 8, 8 }; int wct[20.. 2015. 1. 14.
16. 프로젝트 오일러 #16 : 2의 1000승의 모든 자릿수 합 구하기. 사실 이번 프로그램은 Big integer를 사용할 줄 아느냐 아니냐에 따라서 달라진다고 봅니다. 많은 언어가 기본으로 Big Integer를 지원하기 때문에, 언어에 따라서 구현 난이도도 차이가 많을겁니다. 예를 들어서 python을 이용하면, 가볍게 이 문제를 해결할 수 있습니다. >>> 2**1000 10715086071862673209484250490600018105614048117055336074437503883703510 51124936122493198378815695858127594672917553146825187145285692314043598 45775746985748039345677748242309854210746050623711418779541821530464749 8358194126.. 2015. 1. 13.
프로젝트 오일러 #15 격자 경로의 수 구하기 사실 이번 문제는 상당히 쉬운 편이라서 그다지 설명이 필요할 것도 없을 듯 합니다. 다른 프로그래머도 저랑 비슷한 접근을 했고요. 2014년 년 마지막 날을 이렇게 보내네요. 예를 들면 2x2 격자에서 오른쪽과 아래로만 갈 수 있는 경로의 수는, 오른쪽 이동을 R, 아래 이동을 D라 표현하면 다음과 같습니다. RRDD RDRD RDDR DRRD DRDR DDRR 위와 같이 총 6가지의 경우가 나옵니다. 이 중에 R만을 가지고 따진다면, 4개의 칸 중에 2개의 R을 배치하는 방법의 수입니다. 프로젝트 오일러의 문제 링크입니다. https://projecteuler.net/problem=15 Problem 15 - Project Euler Starting in the top left corner of a 2.. 2014. 12. 31.
728x90