본문 바로가기
반응형

Programming/Project Euler89

22. 프로젝트 오일러 #22 : 이름 점수 구하기 이번 문제는 이름 점수를 구해서 정렬한 순서값을 곱하는 비교적 간단한 알고리즘입니다. 정렬이야 원래 C/C++ 에 들어가 있는 qsort()를 써도 되고, 아주 간단한 알고리즘을 적용해도 그다지 큰 문제가 없습니다. 저는 힙정렬을 만들어서 짜보았습니다. 힙정렬이 베스트라고는 할 수는 없지만, 처음에는 파일로 읽어서 사용할 예정이었기 때문에, 힙정렬이나 삽입정렬이 그런면에서는 유리한 점이 있습니다. 다른 정렬은 모두 배열에 일단 넣고, 그 다음 정렬을 하게 되지만, 힙정렬이나 삽입정렬은 삽입을 비교적 다른 정렬 방법에 비해서 손쉽게 할 수 있는 장점이 있습니다. 정렬 과정에서 삽입과정이 일어나니까요. 주어진 데이터 파일을 보니, 파싱보다는 그냥 소스에 붙여넣기 또는 #include "names.txt"를 .. 2015. 1. 25.
[C/C++] 프로젝트 오일러 #21 10,000 이하의 친화수 찾기. 이번 문제는 밀레니엄 문제급은 아니지만, 홀수 완전수가 존재하지 않는다의 증명과 같이 오랫동안 풀리지 않는 문제의 영역입니다. 완전수에 대해서 아시는 분들은 많을거라고 생각합니다. 완전수는 자신을 제외한 약수의 합이 자신이 되는 수를 뜻합니다. 대표적으로는 6, 28 과 같이 짝수만 존재합니다. 완전수의 갯수가 무한한가라는 것도 사실 밝혀진 바가 없습니다. 짝수 완전수의 경우에는 반드시 이 형태여야 된다는 것은 이미 증명되었고, 그 증명과정이 어렵지는 않습니다. 완전수와 비슷하게 친화수도 자기 자신을 제외한 약수의 합을 통해서 나타냅니다. 그 약수들의 합이 다른 수가 되고, 그 다른 수의 약수들의 합이 자신이 되면, 두 사이 관계는 친화수라고 합니다. 친화수가 수학에서 큰 비중을 가지는 수는 아닙니다. .. 2015. 1. 18.
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.
728x90

티스토리툴바