피보나치 수열 심화과정5 -피보나치 수열의 합을 가장 빠르게 구하는 방법-

1. 피보나치 수열 $F_{0} = 0, F_{1} = 1, F_{n} = F_{n-1}+F_{n-2}, n \geq 2$로 정의되는 수열 $F_{n}$ 2. 홀수번째 항의 합 1항부터 $2n-1$번째 항까지의 합은 다음과 같이 $2n$번째 항과 동일하다. $$\sum_{k = 1}^{n} F_{2k-1} = F_{2n}$$ 증명) $F_{n+2} = F_{n+1} + F_{n}$에서 n = 2n - 2를 대입하면, $F_{2n} = F_{2n-1} + F_{2n-2}$ 그러면, $F_{2n-1} = F_{2n} - F_{2n-2}$이므로, $$\sum_{k=1}^{n} F_{2k-1} = F_{1} + \sum_{k=2}^{n} (F_{2k} - F_{2k-2})$$ 이 식을 풀어서 써보면, 망원급수임..

• format_list_bulleted 정수론
• · 2023. 5. 27.
• textsms

피보나치 수열 심화과정4 -피보나치 수의 최대공약수 놀라운 성질-

1. 피보나치 수의 최대공약수 다음과 같이 정의되는 피보나치 수열 $F_{0} = 0, F_{1} = 1$이고 $F_{n+2} = F_{n+1} + F_{n}, n \geq 0$ 에 대하여, n번째 피보나치 수 $F_{n}$와 m번째 피보나치 수 $F_{m}$의 최대공약수 $gcd(F_{n}, F_{m})$은 n,m의 최대공약수 gcd(n,m)번째 피보나치 수와 같다. $$gcd(F_{n}, F_{m}) = F_{gcd(n,m)}$$ 2. 보조정리1 임의의 정수 k에 대하여, $gcd(a,b) = gcd(a+kb, b)$ 증명) x가 a,b의 공약수라면, a는 x로 나누어 떨어지고 ($x | a$로 표시) b도 x로 나누어 떨어진다. 그러므로, 임의의 정수 k에 대하여 kb도 x로 나누어 떨어진다. a도..

• format_list_bulleted 정수론
• · 2023. 5. 26.
• textsms

필승 전략 게임 - 돌 줍기 게임에서 반드시 이기는 방법

1. 돌 줍기 게임 1) A부터 시작하여, A와 B가 번갈아가며 쌓여 있는 돌 무더기에서 돌을 1개 이상 집어온다. 2) 자기 차례가 되어 돌을 집어 올때는, 반드시 상대방이 조금 전에 집어간 돌의 개수의 2배 이하로 집어와야 한다. 예를 들어, A가 2개를 집고 차례를 넘겼다면, B는 1개~4개까지 범위에서 돌을 집어와야한다. 이제 B가 3개를 집고 넘겨준다면, A는 다시 1개~6개 범위에서 마음대로 돌을 집어갈 수 있다. 3) 마지막 돌을 집어간 사람이 게임에서 승리한다. 4) 맨 처음 시작하는 사람이 돌을 다 집어갈 수는 없다 2. 반드시 이길 수는 없나? A,B가 최선의 전략으로 게임할때, 누가 이기는지 예측할 수 있을까? 1) 돌멩이가 1개 있을때, 게임 자체가 성립하지 않는다. 맨 처음 시작하..

• format_list_bulleted 게임이론
• · 2023. 5. 23.
• textsms

코딩테스트 복기 - 최단거리를 가장 빠르게 구할 수 있는 0-1 BFS 알고리즘

1. 문제 그래프 G가 V개의 정점과 E개의 간선으로 이루어지며 간선의 가중치가 0 또는 1이다. 이때 두 정점 사이의 최단 경로를 찾는 효율적인 코드를 작성해야한다면? 2. 다익스트라 알고리즘이 항상 정답인가? 많은 경우에 다익스트라 알고리즘을 선택하지만, O(E+VlogV)가 최상의 구현이지만, 최악의 경우 효과적이지 않다. 많은 사람들이 이 문제를 보면 다익스트라 알고리즘을 선택하고, 효율적이지 않을때, 최적화할려고 노력하지만, 다익스트라 알고리즘이 최상이라고 생각한다면.. 매우 간단하면서 BFS를 이용한 아주 아름다운 0-1 BFS라는 기법을 알 필요가 있다 보조정리(Lemma) : "BFS 수행중에 정점을 포함하는 큐는, BFS 트리의 최대 2개의 연속한 레벨의 원소만을 포함할 수 있다" Lem..

• format_list_bulleted 최단거리 알고리즘
• · 2023. 5. 22.
• textsms

C++ 알고리즘 기초14 -조건문 심화-

1. else if 필요하다면 else if는 여러번 사용가능하다. else if 당 상단 if와 모든 else if에 걸리지 않으면서 해당 else if 조건에 해당하는 경우에만 특정 코드를 수행하게 만들 수 있다. if (조건1) { 코드1 } else if (조건2) { 코드2 } else if (조건3) { 코드3 } else { 코드4 } 코드5 조건1, 조건2가 모두 거짓이고 조건 3이 참이라면, 코드 3, 코드 5만 수행된다 A반의 출석번호 1번은 John, 2번은 Tom, 3번은 Paul입니다. 번호를 입력하면 해당하는 학생의 이름을 출력하는 프로그램을 작성하세요. 만약, 해당 출석 번호에 해당하는 학생이 없다면 Vacancy라고 출력하세요. #include using namespace s..

• format_list_bulleted C++ 기초
• · 2023. 5. 21.
• textsms

C++ 알고리즘 기초11 -조건문 배우기2(삼항연산, if-else if-else)

1. 삼항연산자 if - else로만 이루어져 있는 다음과 같은 구문은 if (조건) { a = v1; } else { a = v2; } 삼항연산자를 이용해서 한 줄에 표현 가능하다. a = (조건) ? v1 : v2; 조건이 참이면, a는 v1을 가지고, 조건이 거짓이면, v2를 가진다는 의미다. #include using namespace std; int main() { int a,n; n = 8; // a = 2 + 6 + n > a = 6 a = 2 + 6 + (n a >> b; int m = a > b ? a : b; cout > a; char b = a == 1 ? 't':'f'; cout > a; if (a >= 10) { cout

• format_list_bulleted C++ 기초
• · 2023. 5. 16.
• textsms