베주의 항등식 - 최대공약수로 만들 수 있는 정수

1. 문제 25333번: 개구리 (acmicpc.net) 25333번: 개구리 Albert는 개구리 장난감을 이용한 놀이를 즐겨한다. 이 장난감은 우측으로 $A$cm 혹은 좌측으로 $B$cm 점프할 수 있다. 예를 들어 현재 개구리 장난감의 위치가 $0$이고 $A = 4$, $B = 2$ 라 하자. 아래 그 www.acmicpc.net 2. 풀이 예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데 조금 수학적으로 생각해보면 A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데 오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는 Ax+By형태와 같다. 이는 베주의 항등식 형태와 같으며, "정수 x,y에 대하여..

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

피보나치 수열 심화과정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