기초수학

나머지 연산의 성질 - 피보나치

7~14번 테스트 케이스에서 "실패" OR "signal: illegal instruction (core dumped)" 🔎 이렇게 푸셨나요? % 1234567를 딱 한 번만 하셨나요? 오버플로우가 난 게 아닌가 의심돼요! 🚨이런 문제가 있어요 n이 매우 큰 경우 n번째 피보나치 수는 언어가 표현할 수 있는 자료형의 범위를 넘어가, 오버플로우가 납니다. 예를 들어 47번째 피보나치 수는 2,971,215,073이고, 이 수는 32비트 정수(ex. int) 범위를 넘어 오버플로우가 발생합니다. 100,000번째 피보나치 수는 자릿수가 20,000을 넘어가며, 이는 64비트 정수(ex. long) 범위를 넘어 오버플로우가 발생합니다. 💡그럼 코드를 어떻게 바꾸면 좋나요? 모든 단계에서 % 연산을 사용하여, ..

길이가 같은 두 배열의 요소끼리 곱하고 더할 때의 최솟값

길이가 같은 배열 A, B 두개가 있다. 각 배열은 자연수로 이루어져 있다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱한다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더한다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없다.) 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면 A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더한다. (누적된 값 : 0 + 5(1x5) = 5) A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더한다. (누적된 값 : 5 + 16(4x4) = 21) A에서 세번째 숫자인 2, B에..

최대 공약수와 유클리드 호제법 그리고 최소공배수

개념 최대공약수(Greatest Common Divisor, GCD) 공약수(common divisor)란 두 수 이상의 여러 수의 공통된 약수를 의미한다. 최대공약수(GCD)란 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다. 소인수분해를 이용한 방법 나눗셈을 이용한 방법 유클리드 호제법 개념 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r(a%b)의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r’를 구하고, 다시 ..