C++ 알고리즘 기초18 - 반복문 심화2(10의 자리와 1의 자리 구하는 방법 복기)-

1. 조건문 안에 for문 사용 두 개의 정수a, b를 입력받아 큰 수부터 작은 수까지 차례대로 출력하는 프로그램을 작성해보세요. a,b를 입력 받은 다음에, a >= b이면, a부터 b까지 for문으로 1을 감소시키면서 출력하고 a > a >> b; if (a >= b){ for(int i = a; i >= b; i--){ cout

• format_list_bulleted C++ 기초
• · 2023. 6. 6.
• textsms

필승 전략 게임 - 베스킨라빈스 31 게임에서 반드시 이길 수 있을까?

1. 베스킨라빈스 31 술게임에서 많이 하는 게임이다. 규칙은 다음과 같다. 두 사람이 게임을 하는데 1부터 시작해서 3개까지 숫자를 부를 수 있고 31을 먼저 부르면 지는 게임이다. 예를 들어 A가 1,2,3을 부르면 B는 4,5를 부르고 A는 다시 6,7을 부르고.... 상대방이 나한테 선공을 양보했다. 술을 못마시는 나는 최대로 집중해서 이 게임에서 반드시 이기고 싶다. 어떻게 해야 내가 이 게임에서 반드시 이길 수 있을까? 2. 게임의 필승 전략1 결국 내가 게임을 이길려면 마지막에 30을 불러야 게임에서 이길 수 있게 된다. 그 전에 내가 불러야 하는 숫자는 얼마일까? 상대방이 27, 28, 29중 하나로 끝을 내야 내가 마지막에 30을 부를 수 있다 상대방이 27, 28, 29중 하나로 끝을 ..

• format_list_bulleted 게임이론
• · 2023. 6. 5.
• 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

C++ 알고리즘 기초9 -사칙연산 배우기-

1. 사칙연산 C++에서 사용되는 사칙연산 덧셈, 뺄셈, 곱셈, 나눗셈은 각각 +,-,*,/으로 구할 수 있다. #include using namespace std; int main() { int a = 9, b = 4; cout

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

숫자를 안만들고 나머지를 구하는 방법, 문자열 연산 없이 두 수를 붙이는 방법

1. 문제 27965번: N결수 (acmicpc.net) 27965번: N결수 $10$진법 상에서 양의 정수 $1$, $2$, $3$, $\cdots$, $N$을 이어 붙여 만든 수 $\overline{123\cdots N}$을 $N$결수라고 한다. 예를 들어 $12345$는 $5$결수이고, $12345678910111213$은 $13$결수이다. $N$과 정수 $K$가 주어 www.acmicpc.net 2. 풀이1 쉽다는데... 솔직히 까다로운 문제같다 n이 10의 7제곱까지라 n결수를 만들면 당연히 시간초과일거고 (애초에 만들어지지도 않음) 그 전에 근본적으로 나눗셈 연산을 어떻게 하는지 생각을 해보면.. 1234를 5로 나누는 것은 어떻게 할까? 1을 5로 나눠보고.. 몫이 0이고 나머지가 1이니까 ..

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

정수 n을 2의 거듭제곱으로 나눈 나머지를 효율적으로 구하는 방법

나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가? %연산은 계산 비용이 높아서 비효율적으로 알려져있다. n = 98 print(n % 2) #0 print(n % 4) #2 print(n % 8) #2 print(n % 16) #2 print(n % 32) #2 계산비용을 줄이고 싶다면 % 연산자를 사용하지 않고 나머지를 구해야한다. 예를 들어 4로 나눈 나머지를 어떻게 구할 수 있을까? 컴퓨터는 모든 수를 2진수로 인식하기 때문에.. 가장 쉬운 접근은 정수 n을 2진수로 나타내보는 것이다. 위 그림을 보면 어떤 수를 4로 나눈 나머지는 0,1,2,3중 하나인데... n을 2진수로 나타냈을때 4로 나눈 나머지는... n의 2진수 표현에서 오른쪽 끝의 2비트만 가져오는 것임을..

• format_list_bulleted 비트마스킹
• · 2023. 5. 3.
• textsms