본문 바로가기

Programming456

[C/C++] 프로젝트 오일러 #25 : 1000자리 피보나치 수열항 구하기 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다.  피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요.  꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다.  기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. \[ F_{n+2} = F_n + F_{n+1} \] 점화식을 보면 아주 간단한 형태입니다.  전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서  첫번째 항과 두번째 항이 초기값으로 주어져야 합니다.  첫번째 항은 1, 두번째 항은 1입니다.  자연수 범위.. 2015. 2. 17.
area : 사각형 넓이 구하기 Dovelet 사이트는 프로젝트 오일러 사이트와 달리 프로그램을 작성해서 해당 프로그램을 올리면, 실제 컴파일하고, 테스트 케이스를 이용해서 프로그램이 올바른지 검사를 합니다. 그래서 제한 시간도 존재를 하고, 여러가지 테스트 케이스를 시험해보기 때문에, 프로젝트 오일러 사이트에서는 해당 문제 답만 알면 되는데 비해서 Dovelet 사이트는 그것이 불가능합니다. 입력과 출력이라는 부분이 있는데, 단순하게 숫자만 입력 받고, 출력 결과값만 출력해야 합니다. 사각형 넓이 구하기 문제는 워낙 간단한 것이지만, 처음 접해보시는 분이라면 한번 이것을 풀어보는 것이 좋겠죠. (사실 제가 처음 푼 문제는 이것은 아니었습니다.) #include int main() { int a, b; scanf("%d%d", &a, .. 2015. 2. 14.
[C/C++] 슬라이딩 퍼즐 풀기 - 기본편 어렸을 때, 한번쯤은 다들 해보았을 법한 퍼즐입니다.  일반적으로 4x4 퍼즐이라고도 하고, 그림 퍼즐이라고도 합니다.  하지만 퍼즐이란 말은 무언가 풀어볼 수 있는 형태의 게임을 다 지칭하는 것이라서요.  슬라이딩 퍼즐이라고 한정지어서 이야기하는 것이 맞을 듯 합니다.   4x4 슬라이딩 퍼즐 보통 많이 있는 퍼즐은 4x4 퍼즐로 위와 같이 숫자가 1부터 15까지 써 있는 형태이거나 그림이 있는 경우입니다. 4x4 그림 퍼즐 퍼즐 자체가 어렵지 않기 때문에, 하다보면 퍼즐을 맞출 수가 있습니다.  보통은 빈칸이 있는 곳과 가장 먼 줄부터 맞추어 나가는 것이죠.  맨 마지막 두줄은 돌리면서 회전하는 것을 생각해서 위치를 맞추면 됩니다. 그런데 최적의 해를 구할려면 어떻게 될까요?슬라이딩 퍼즐은 모든 경우.. 2015. 2. 13.
[C/C++] 프로젝트 오일러 #24 : 백만번째 순열 수 구하기 프로젝트 오일러 #24 백만번째 순열 수 구하기 문제는 0부터 9까지의 숫자로 이루어진 모든 순열(permutation)을 사전 순서(lexicographic order)로 정렬했을 때, 백만 번째 순열을 구하라는 것입니다. 우리가 진법을 계산할 때, 과연 어떻게 할까요?예를 들어서 723 을 8진법으로 계산한다면요?이 계산을 위해서 우리는 나누기 연산을 계속 하게 됩니다.  중학교 수학을 들추어 보면 보통 다음과 같이 계산을 합니다.으로 723은 8진수로 \(1323_8\)으로 표시가 됩니다. 이것을 수식으로 표현하면 다음과 같이 표현할 수 있습니다.\[ 723 = 1 \cdot 8^3 + 3 \cdot 8^2 + 2 \cdot 8^1 + 3 \cdot 8^0 \]이야기는 우리는 8의 3승부터 차례로 .. 2015. 1. 27.
[C/C++] 프로젝트 오일러 #23 : 초과수의 합으로 표현 안되는 자연수들의 합 Project Euler #23 - Non-Abundant Sums 문제는 다음을 요구합니다.자연수는 “부족수(Deficient number)”, “완전수(Perfect number)”, 또는 “과잉수(Abundant number)” 중 하나로 분류됩니다. 특정 숫자의 진약수들의 합이 해당 숫자보다 작은 경우, 그 숫자는 부족수입니다. 합이 정확히 같은 경우에는 완전수라고 하고, 더 큰 경우에는 과잉수라고 합니다. 예를 들어, 숫자 12의 진약수는 1, 2, 3, 4, 6이고, 이들의 합은 16이므로 12는 과잉수입니다.문제는 다음 두 가지를 해결하라고 요청합니다:1. 두 개의 과잉수의 합으로 나타낼 수 없는 모든 양의 정수를 “비과잉합(non-abundant sums)“이라고 정의합니다. 이러한 모든 .. 2015. 1. 26.
[C/C++] 프로젝트 오일러 #22 : 이름 점수 구하기 이 문제에서는 주어진 텍스트 파일에 포함된 이름들의 점수 합계를 계산하는 것을 요구합니다. 문제를 해결하기 위한 단계는 다음과 같습니다:1. 입력 파일 읽기: 파일에서 각각의 이름이 큰따옴표로 묶여 있는 쉼표로 구분된 단일 행 데이터를 읽습니다.2. 이름을 알파벳 순으로 정렬: 이름 리스트를 알파벳 오름차순으로 정렬합니다.3. 이름 점수 계산:• 각 이름의 점수를 계산합니다. 이름의 점수는 이름을 구성하는 각 글자의 알파벳 값을 더하여 구합니다 (A=1, B=2, …, Z=26).• 해당 이름 점수에 정렬된 순서(1부터 시작하는 인덱스)를 곱합니다.4. 전체 점수 계산: 모든 이름 점수를 합산하여 최종 결과를 구합니다.예를 들어, 파일에 "COLIN", "ALEX", "BOB"가 포함되어 있다면, 정렬된.. 2015. 1. 25.
728x90