cyphen156

이번에 배울 내용은 유클리드 알고리듬과 유사한 스테인의 알고리듬이다. 전에 컴퓨터의 연산은 뺄셈이던지 곱셈이던지 혹은 나눗셈이던지 항상 이진 덧셈으로 이루어진다고 했다. 그런데 곱셈 연산과 나눗셈 연산의 경우 덧셈이 아닌 방식으로 동작시키는 것이 가능하다. 바로 비트시프트를 이용하는 것이다. 여기 1byte크기의 메모리에 데이터가 저장되어있다고 하자. 이 정수의 4배를 구하려면 같은 수를 덧셈 연산을 4번 해야 한다. 반면 비트시프트 연산의 경우 단순히 저장된 데이터중 일부 비트정보를 뒤집으면 되기에 이론적으로 횟수로는 2번의 횟수가 되어 덧셈 연산보다 더욱 빠를 수 있다. 나눗셈의 경우도 곱셈과 연산 방향만 바뀔 뿐 연산 수행 횟수는 동일하다. 이러한 비트시프트라는 것과 짝수에 반드시 2라는 약수가 있..

25304번: 영수증 (acmicpc.net) 25304번: 영수증 준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 준원이는 영수증을 보면서 정확하게 계산된 것 www.acmicpc.net input들의 합이 올바른지 확인하는 프로그램 제약사항 0 > a >> b; X -= a * b; } if (X == 0) { cout

흔히 유클리드 호제법(Euclidean algorithm)으로 알려진 두 양의 정수의 최대공약수와 최소공배수를 빠르게 찾아내는 문제해결방법이다. 수식이 조금 난잡해서 보기 불편한데 함수 수식으로 변환하면 f(x) = ax + b가 성립한다면 gcd(a, b) = gcd(r, b)이다 GDC(greatest common divisor/최대공약수) 최대공약수를 구하는 일반적인 방법은 다음과 같다. 두 수를 소인수 분해하여 서로 공통되는 약수들을 찾아 모두 곱한다. A = 100, B = 12일 때 두 수의 약수들은 각각 (1, 2, 4, 5, 10, 20, 25, 50, 100), (1, 2, 3, 4, 6, 12)로 1 * 2 * 4 = 8이다. 코드로 약수를 찾아가는 과정은 다음과 같다 아래의 코드는 한..

구조체, 리스트를 사용한 자료구조 만들어보기 첫번째 스택 다 만드는데 대충 2시간쯤 걸렷나? 싶다 간만에 하니까 기억이 가물가물하네 기본적으로 스택은 리스트의 한 유형에 해당한다. LIFO(Last In Frist Out/후입 선출)이라는 구조를 가지고 있는데, 가장 마지막에 입력된 자료가 맨 처음 수행되는 하노이의 탑쌓기라고 생각하면 된다. 스택이 중요한건 컴퓨터가 메모리 상에서도 스택이라는 구조를 사용하기도 하지만, 운영체제 입장에서도 다른것은 신경쓸 필요 없이 최상위 데이터만 신경쓰면 되기에 처리 속도면에서 효율적인 자료구조라고 볼 수 있다. 스택이 비었을 경우의 동작 스택에 자료를 입력한 이후의 동작 /** * 스택자료구조 구현하기 * //리스트 * using struct * */ #define ..

8393번: 합 (acmicpc.net) 8393번: 합 n이 주어졌을 때, 1부터 n까지 합을 구하는 프로그램을 작성하시오. www.acmicpc.net 1부터 입력받은 수 까지의 합을 출력한다. 제약사항 0 > A >> B; cout

10950번: A+B - 3 (acmicpc.net) 10950번: A+B - 3 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 입력받은 두 정수의 합을 출력한다. 제약사항 Test == t; 0 < A, B < 10 C 풀이 A+B - 3_10950.c #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int t, A, B; scanf("%d", &t); for (int i = 0; i < t; ++i) { scanf("%d%d", &A, &B); printf("%d\n", A + B); } return 0; } C++ 풀이 A+B - 3_10950.cpp #include using name..

2739번: 구구단 (acmicpc.net) 2739번: 구구단 N을 입력받은 뒤, 구구단 N단을 출력하는 프로그램을 작성하시오. 출력 형식에 맞춰서 출력하면 된다. www.acmicpc.net 입력받은 정수에 해당하는 곱셈식 (N * 1~9)을 출력하는 문제이다. 제약사항 1 N; for (int i = 1; i < 10; ++i) { cout

2480번: 주사위 세개 (acmicpc.net) 2480번: 주사위 세개 1에서부터 6까지의 눈을 가진 3개의 주사위를 던져서 다음과 같은 규칙에 따라 상금을 받는 게임이 있다. 같은 눈이 3개가 나오면 10,000원+(같은 눈)×1,000원의 상금을 받게 된다. 같은 눈이 2개 www.acmicpc.net 입력받은 두 정수를 시간을 기준(24시, 60분)기준으로 변환하여 45분을 감산하여 출력하면 되는 문제이다. 문제 출력 알고리즘 A == B == C : 10,000 + A * 1000 A == B || B == C || C == A : 1000 + (A or B or C) * 100 A != B != C : Max()*100 제약사항 주사위의 눈은 1~6까지 이다. C 풀이 알람 시계_2884 ...