굳건하게

안녕하세요, 여행벌입니다.

C언어로 쉽게 풀어 쓴 자료구조 1장 - 자료구조와 알고리즘 연습문제 풀이입니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

안녕하세요, 여행벌입니다.

이산수학 Express(2011) 2장 - 논리와 명제 연습문제 풀이입니다.

틀린 부분은 같이 댓글로 얘기해보면 좋을 것 같습니다!

안녕하세요, 트레블비입니다.

오늘은 빠르게 어떤 수의 N 제곱 구하기에 대해서 포스팅하겠습니다.

[O(N) 으로 구하기]

예를 들어, 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

2를 계속 100번 곱하면 간단하게 답을 얻을 수 있겠죠? 

int answer = 1;
for(int i = 0; i < 100; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다. 

그렇다면, 2의 100,000,000,000(1000억) 제곱을 구한다고 한다면 2를 계속 곱해가는 방법으로 빠르게 풀 수 있을까요??

int answer 1;
for(int i = 0; i < 100000000000; i++)
	answer = answer * 2;
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

당연히 1000억 번의 연산이 필요하므로 시간이 엄청 오래 걸립니다.

어떤 수 A의 N제곱을 구해야 되는데 N이 굉장히 크다면,  위의 방법은 시간 복잡도가 O(N)으로 사용할 수 없습니다.

[O(logN) 으로 구하기]

똑같이 2의 100 제곱을 구한다고 해봅시다. ( Int 형 범위는 고려하지 않겠습니다. )

100은 64 + 32 + 4 로 표현할 수 있습니다. 즉, 100 = 1100100(2) 입니다.

당연히, 모든 수는 2진수로 표현이 가능합니다!

이 사실을 이용해 훨씬 더 빠르게 2의 100 제곱을 구해보겠습니다.

int answer = 1, A = 2, N = 100;
while(N){
  if (N & 1)
  	answer = answer * A;
  N = N / 2;
  A = A * A;
}
//주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

A = 2, N은 100 = 1100100(2) 이고 마찬가지로 2^100인 A^N을 구하는 코드입니다.

먼저, 코드를 살펴보겠습니다.

N = 100 = 1100100(2) 이고, A는 2, Answer = 1로 시작합니다.

N & 1 은 N의 마지막 비트와 1을 And연산을 취하는 것으로, N & 1 은 False입니다.

따라서 answer는 그대로 1이고, N = N / 2 이므로 N = 50 = 110010(2)로 마지막 비트가 사라지고,

A = A * A ; 로 2^2인 4가 됩니다.

이 과정을 반복하면 아래 표와 같이 작동합니다.

#주의 : 위의 코드는 Int 형 범위를 넘어가므로 제대로 작동하지 않습니다! 예시일 뿐입니다.

100번의 연산이 아니라, 각 단계마다 3번의 연산으로 무려 7단계 만에 답을 구할 수 있습니다.

N이 커지면 커질수록 처음의 알고리즘보다 훨씬 더 빠르게 작동하겠죠?

잘 익혀두시면 정말 유용하게 사용하는 알고리즘입니다!

함수로 표현하면 다음과 같습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x;
		y = y / 2;
		x = x * x;
	}
	return tmp;
}

당연히, A^N이 Int 나 long long 형 범위를 넘어가는 문제들은 A^N 을 어떤 수로 나눈 나머지를 구해달라 합니다!

아래와 같이 함수로 표현할 수 있습니다.

long long math_pow(long long x, long long y)
{
	long long tmp = 1;
	while (y)
	{
		if (y & 1)
			tmp = tmp * x % m;
		y = y / 2;
		x = x * x % m;
	}
	return tmp;
}

오늘의 포스팅은 여기서 마치겠습니다.

[추천문제]
https://www.acmicpc.net/problem/1629

안녕하세요, 여행벌입니다.

오늘은 간단하게 배열의 구간의 합을 쉽게 구하는 방법에 대해서 포스팅하겠습니다.

배열의 값들이 바뀐다면, 세그먼트 트리를 이용해야 하지만

배열의 값이 바뀌지 않는다면, DP를 이용해 쉽게 구간의 합을 구할 수 있습니다.

[배열의 합 구하기]

A[ N ] : 원소들이 N개 들어있는 배열

이때, A[ i ] ~ A[ j ]까지의 합을 여러 번 구해야 된다고 가정합시다.

먼저, 새로운 배열을 하나 정의하겠습니다.

S [ N ] : A배열의 첫번 째 원소부터 K번째 원소까지의 합을 저장한 배열. ( S[ k ] = A [0] + A [1] + ⋯ + A [k] )

그러면, A [ i ] ~ A[ j ] 까지의 합 = S[ j ] - S[ i - 1]이 성립합니다.

또, S[ K ] = S[ K - 1 ] + A[ K ]와 같은 점화식이 성립합니다.

이 두 가지 사실을 이용해 S 배열을 빠르게 채우고, S 배열의 값을 이용해 구간의 합을 구한다면,

굉장히 빠르게 구할 수 있습니다.

실습을 해보겠습니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int A[10], S[10];
	cout << "A배열의 원소를 10개 입력하시오.\n";
	for (int i = 0; i < 10; i++)
		cin >> A[i];
	S[0] = A[0];
	for (int i = 1; i < 10; i++)
		S[i] = S[i - 1] + A[i];
	cout << "완성된 S배열입니다.\n";
	for (int i = 0; i < 10; i++)
		cout << S[i] << ' ';
	cout << '\n';
}

Input
1 2 3 4 5 6 7 8 9 10

위의 코드에 Input으로 다음과 같이 입력하면, S배열은 어떻게 출력될까요?

완성된 S배열입니다.
1 3 6 10 15 21 28 36 45 55

다음과 같겠죠?

O(n) 만에 우리가 원하는 S 배열을 만들 수 있습니다!

만약, A 배열의 구간의 합을 M번 구해야 되는 문제가 있다면, 2중 포문을 이용해 구해준다면 O(N * M)이 될 것입니다.

하지만 S 배열을 만들어주고, S배열 값을 이용해 M번 A배열의 구간의 합을 구해준다면 O(N + M)으로

훨씬 효율적인 프로그램을 만들 수 있습니다.

추천 문제
https://www.acmicpc.net/problem/2003
https://www.acmicpc.net/problem/11441
https://www.acmicpc.net/problem/11659