코딩생존기

https://www.acmicpc.net/problem/11660

2차원 배열에서 구간합을 구해야한다. 이를 위해 누적합을 계산해줘야한다. 이때 문제의 규칙에 맞게

sum[i][j]=arr[i][j]+sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]

이렇게 더해주면 되는데 이때 

• arr[i][j]
  현재 위치 (i, j)의 값이다. 즉, 현재 칸의 값을 더해야 한다.
• sum[i-1][j]
  (1, 1)부터 (i-1, j)까지의 합이다. 즉, 현재 칸 위쪽에 있는 값들의 합을 포함한다.
• sum[i][j-1]
  (1, 1)부터 (i, j-1)까지의 합이다. 즉, 현재 칸 왼쪽에 있는 값들의 합을 포함한다.
• - sum[i-1][j-1]
  위쪽(sum[i-1][j])과 왼쪽(sum[i][j-1])에서 중복으로 더해진 영역을 빼준다. 중복된 부분은 (1, 1)부터 (i-1, j-1)까지의 합이다.

이렇게 누적합을 계산해주고 쿼리에 맞게 계산된 누적합을 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>>v(n + 1, vector<int>(n + 1, 0));
	vector<vector<int>>sum(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			cin >> v[i][j];
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			sum[i][j] = v[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
		}
	}

	for (int i = 0; i < m; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		int result = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
		cout << result << '\n';
	}

	return 0;
}

https://www.acmicpc.net/problem/16139

소문자 문자열에 대한 누적합 배열을 만들어주고 이를 통해 문자열에 해당하는 구간에 얼마나 나오는지 구해주면 된다.

처음에 map을 사용하여 풀어보았는데 50점이 나왔다.

이유를 찾아보니 map에서 키를 관리할 때 이진 탐색트리를 사용하기 때문에 매 쿼리마다 이진 탐색 트리 과정이 추가로 들어가기 때문에 vector를 통해 알파벳에 접근하는 것이 더 효율적이다.

정답코드(map사용 : 50점)

#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main()
{
	string s;
	cin >> s;

	int n = s.size();
	map<char, vector<int>> sum;

	// 누적 합 배열 초기화
	for (char c = 'a'; c <= 'z'; c++) {
		sum[c].resize(n + 1, 0);
	}

	// 누적 합 계산
	for (int i = 1; i <= n; i++) {
		for (char c = 'a'; c <= 'z'; c++) {
			sum[c][i] = sum[c][i - 1]; // 이전 값 복사
		}
		sum[s[i - 1]][i]++; // 현재 문자에 대한 값 증가
	}

	int q;
	cin >> q;

	for (int i = 0; i < q; i++)
	{
		char c;
		int l, r;
		cin >> c >> l >> r;

		int cnt = sum[c][r + 1] - sum[c][l];
		cout << cnt << "\n";
	}

	return 0;

}

정답코드(vector사용 : 100점)

#include <iostream>
#include <vector>

using namespace std;

int main() {


    string s;
    cin >> s;

    int n = s.size();

    // 알파벳 별 누적합 배열
    vector<vector<int>> sum(n + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 26; j++) {
            sum[i][j] = sum[i - 1][j]; // 이전 값을 복사
        }
        sum[i][s[i - 1] - 'a']++; // 현재 문자의 개수를 증가
    }

    int q;
    cin >> q;

    for(int i=0;i<q;i++) 
    {
        char c;
        int l, r;
        cin >> ch >> l >> r;

        int cnt = sum[r + 1][c - 'a'] - sum[l][c - 'a']; // 구간 계산
        cout << cnt << "\n";
    }

    return 0;
}

https://www.acmicpc.net/problem/2559

배열을 입력받고 슬라이딩 윈도우를 통해 k개 만큼의 합을 비교해가면서(i번째 위치의 합을 더해주고 제일 마지막 위치인 i-k번째의 합을 빼주면 된다) 최대합을 찾아내면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k; 

	vector<int> v(n, 0);

	// 배열 입력 
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}

	int sum = 0;
	for (int i = 0; i < k; i++)
	{
		sum += v[i];
	}

	int max_sum = sum;

	//슬라이딩 윈도우
	for (int i = k; i < n; i++)
	{
		sum += v[i] - v[i - k];
		max_sum = max(max_sum, sum);
	}

	cout << max_sum << "\n";

	return 0;
}

https://www.acmicpc.net/problem/11659

배열을 입력받고 누적합을 미리 계산해준 다음 이 계산해준 누적합 배열의 j번째와 i번째의 값을 빼준 값을 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<int> v(n+1, 0);
	vector<int> sum(n+1, 0);

	// 배열 입력 및 누적 합 계산
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		sum[i] = sum[i - 1] + v[i];
	}

	
	for (int q = 0; q < m; q++) {
		int i, j;
		cin >> i >> j;
		cout << sum[j] - sum[i - 1] << "\n";
	}
	
	return 0;
}

https://www.acmicpc.net/problem/11444

피보나치 수를 분할정복 방식으로 풀어야하는 문제이다. 

이때 행렬 분할 정복 방식을 사용해보자 

피보나치 수는 위와 같이 행렬의 곱셈을 통해 표현할 수 있다. 그렇게 때문에 피보나치의 기본 수 부터  n-1 번째 행렬의 거듭제곱을 계산해주면 n번째 피보나치 수를 빠르게 구할 수 있다. 

즉 n-1까지의 거듭제곱을 계산해주고 이 행렬의 0,0위치 의 값을 반환해주면 n번째 피보나치 수를 구할 수 있다.

정답코드

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

typedef vector<vector<long long>> Matrix;

//행렬 곱셈 함수
Matrix multiply(const Matrix& a, const Matrix& b)
{
	//곱셈 결과를 저장할 함수
	Matrix result(2, vector<long long>(2, 0));
	for (int i = 0; i < 2; i++)
	{
		for (int j = 0; j < 2; j++)
		{
			for (int k = 0; k < 2; k++)
			{
				result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;
			}
		}
	}

	return result;
}

//행렬 거듭제곱 함수
Matrix matrixPower(Matrix a, long long n) {
	Matrix result = { {1, 0}, {0, 1} }; // 단위 행렬
	while (n > 0) {
		if (n % 2 == 1) {
			result = multiply(result, a);
		}
		a = multiply(a, a);
		n /= 2;
	}
	return result;
}

int main()
{
	long long n;
	cin >> n;

	if (n == 0) {
		cout << 0 << endl;
		return 0;
	}

	// 피보나치 초기 행렬
	Matrix a = { {1, 1}, {1, 0} };

	//n번째까지의 피노나치 계산
	Matrix result = matrixPower(a, n - 1);
	
	cout << result[0][0] << "\n";

	return 0;
}

https://www.acmicpc.net/problem/10830

행렬의 거듭제곱을 계산하면 된다. 

기존 거듭제곱을 분할정복으로 했던 방법처럼 지수의 짝수일 때, 홀수 일때를 나눠서 계산해주면 된다.

정답코드

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000;

// 두 행렬을 곱하는 함수
vector<vector<int>> multiply(const vector<vector<int>>& A, const vector<vector<int>>& B, int N) {
    vector<vector<int>> result(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                result[i][j] = (result[i][j] + A[i][k] * B[k][j]) % MOD;
            }
        }
    }
    return result;
}

// 행렬을 거듭제곱하는 함수 (분할 정복)
vector<vector<int>> matrixPower(const vector<vector<int>>& A, long long B, int N) {
    if (B == 1) {
        return A; // A^1 = A
    }

    vector<vector<int>> halfPower = matrixPower(A, B / 2, N);
    vector<vector<int>> halfResult = multiply(halfPower, halfPower, N);

    if (B % 2 == 0) {
        return halfResult;
    }
    else {
        return multiply(halfResult, A, N);
    }
}

int main() {
    int N;
    long long B;
    cin >> N >> B;

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
            A[i][j] %= MOD; // 입력 시 1000으로 나눈 나머지로 저장
        }
    }

    vector<vector<int>> result = matrixPower(A, B, N);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << result[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

https://www.acmicpc.net/problem/1629

제한시간이 짧기 때문에 거듭제곱을 분할정복을 통해 풀어야한다. 이때 빠른 거듭제곱을 사용할 수 있다. 

빠른 거듭제곱은 지수가 짝수일때와 홀수일때를 나눠서 분할하여 계산해주는 방법이다.

이러한 방식을 재귀적으로 적용하면, 지수를 절반으로 줄여가며 ABmod  CA^B \mod CABmodC를 계산할 수 있다. 이를 통해 시간 복잡도를 O(log⁡B)O(\log B)O(logB)로 줄일 수 있다.

정답코드

#include <iostream>
using namespace std;

// 분할 정복을 이용한 거듭제곱 함수
long long modExp(long long a, long long b, long long c) {
    if (b == 0) return 1;           // A^0 = 1
    if (b == 1) return a % c;        // A^1 = A % C

    long long half = modExp(a, b / 2, c); // A^(B/2) 계산

    if (b % 2 == 0) {
        // B가 짝수인 경우
        return (half * half) % c;
    }
    else {
        // B가 홀수인 경우
        return ((half * half) % c * a % c) % c;
    }
}

int main() {
    long long a, b, c;
    cin >> a >> b >> c;

    cout << modExp(a, b, c) << endl;

    return 0;
}

https://www.acmicpc.net/problem/2740

2차원 벡터로 각 행렬을 입력받은 다음 행렬 곱셉의 공식대로 3중 for을 통해 곱셉을 해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> a;
vector<vector<int>> b;
vector < vector<int>> result;

int main()
{
	int n, m, k;
	cin >> n >> m;
	a.resize(n, vector<int>(m));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
		}
	}

	cin >> m >> k;
	b.resize(m, vector<int>(k));

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < k; j++)
		{
			cin >> b[i][j];
		}
	}


	//행렬곱셈
	result.resize(n, vector<int>(k, 0));
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			for (int p = 0; p < m; p++) {
				result[i][j] += a[i][p] * b[p][j];
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k; j++) {
			cout << result[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;

}

https://www.acmicpc.net/problem/1780

분할정복으로 풀면되는 문제이다. 

우선 그래프를 입력받고 그래프의 0,0부터 시작해서 같은 숫자라면 그 숫자의 카운트를 증가시켜주고 아니라면 크기를

3등분하여 재귀 함수로 이 과정을 반복하게 만들어주면서 -1 0 1의 카운트를 증가시켜준다. 이 과정을 한칸로 순회할 떄 까지나 같은 숫자로만 구성되어 있을 때까지 반복해준다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
int minuscnt = 0;
int zerocnt = 0;
int onecnt = 0;

bool isSameNum(int x, int y, int size) {
	int num = graph[x][y]; // 첫 번째 칸의 수
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (graph[i][j] != num) {
				return false; // 다른 수가 섞여 있으면 false 반환
			}
		}
	}
	return true; // 모두 같다면 true
}

// 분할 정복 함수
void divideAndConquer(int x, int y, int size) {
	if (isSameNum(x, y, size)) {
		if (graph[x][y] == -1) {
			minuscnt++;
		}
		else if(graph[x][y] == 0){
			zerocnt++;
		}
		else
		{
			onecnt++;
		}
	}
	else {

		int newSize = size / 3;
		divideAndConquer(x, y, newSize); // 왼쪽 위
		divideAndConquer(x, y + newSize, newSize); // 가운데 위
		divideAndConquer(x, y + 2 * newSize, newSize); //오른쪽 위

		divideAndConquer(x + newSize, y, newSize); // 왼쪽 가운데
		divideAndConquer(x + newSize, y + newSize, newSize); // 가운데 가운데
		divideAndConquer(x + newSize, y + 2 * newSize, newSize); //오른쪽 가운데

		divideAndConquer(x + 2 * newSize, y, newSize); // 왼쪽 아래
		divideAndConquer(x + 2 * newSize, y + newSize, newSize); // 가운데 아래
		divideAndConquer(x + 2 * newSize, y + 2 * newSize, newSize); //오른쪽 아래
	}
}

int main()
{
	int n;
	cin >> n;
	graph.resize(n, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> graph[i][j];
		}
	}
	
	divideAndConquer(0, 0, n);

	cout << minuscnt << "\n" << zerocnt << "\n" << onecnt << "\n";

	return 0;
}

https://www.acmicpc.net/problem/1992

분할정복 알고리즘을 통해 풀 수 있는 문제이다. 

우선 그래프 입력을 받고 함수를 통해 같은 수로만 구성되어있다면 그 수를 출력해주고 아니라면 4등분해서 같은 수가 나올 때까지 나 한칸만 남을때까지 반복해준다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;

bool isSameNum(int x, int y, int size) {
	int num = graph[x][y]; // 첫 번째 칸의 수
	for (int i = x; i < x + size; i++) {
		for (int j = y; j < y + size; j++) {
			if (graph[i][j] != num) {
				return false; // 다른 수가 섞여 있으면 false 반환
			}
		}
	}
	return true; // 모두 같다면 true
}

// 분할 정복 함수
void divideAndConquer(int x, int y, int size) {
	if (isSameNum(x, y, size)) {
		cout << graph[x][y];
	}
	else {

		cout << "(";
		
		int newSize = size / 2;
		divideAndConquer(x, y, newSize); // 왼쪽 위
		divideAndConquer(x, y + newSize, newSize); // 오른쪽 위
		divideAndConquer(x + newSize, y, newSize); // 왼쪽 아래
		divideAndConquer(x + newSize, y + newSize, newSize); // 오른쪽 아래
		cout << ")";
	}
}


int main()
{
	int n;
	cin >> n;
	graph.resize(n, vector<int>(n));

	for(int i=0;i<n;i++)
	{
		for (int j = 0; j < n; j++)
		{
			char ch;
			cin >> ch;
			graph[i][j] = ch - '0';
		}
	}

	divideAndConquer(0, 0, n);

	return 0;

}