코딩생존기

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

최대 범위인 100,000으로 벡터를 초기화해주고 BFS를 통해 탐색을 해주면서 제일 먼저 동생의 위치에 도달하면 그 값을 반환해준다. 이때 현재값에서 -1 +1 *2를  해줘야하기 때문에 이 값을 내부 반복문에 넣고 이를 순회하면서 탐색하도록 해주었다.

정답코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int MAX = 100001;

vector<int> v(MAX, 0);

int BFS(int start, int end)
{
	queue<int> q;

	q.push(start);
	v[start] = 1;

	while (!q.empty())
	{
		int curx = q.front();
		q.pop();

		if (curx == end) return v[end] - 1;

		for (int nextx : {curx - 1, curx + 1, 2 * curx})
		{
			//범위검사
			if (nextx >= 0 && nextx < MAX && v[nextx] == 0)
			{
				v[nextx] = v[curx] + 1;
				q.push(nextx);
			}
		}
	}

	return -1;
}


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


	cout << BFS(n, k) << "\n";

	return 0;
	
}

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

이 문제는 체스판의 크기를 입력받고 벡터를 초기화 시킨다음 나이트가 갈 수 있는 규칙을 BFS로 탐색하면서 최단거리를 찾을 수 있다면 그 최단거리를 반환해주고 아니라면 0을 반환해준다.

정답코드 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int bfs(int l, int startX, int startY, int endX, int endY)
{
	vector<vector<int>> visited(l, vector<int>(l, 0));
	queue<pair<int, int>> q;
	q.push({ startX, startY });
	visited[startX][startY] = 1;


	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == endX && y == endY) return visited[endX][endY] - 1;


		for (int i = 0; i < 8; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx >= 0 && ny >= 0 && nx < l && ny < l && !visited[nx][ny]) {
				visited[nx][ny] = visited[x][y] + 1;
				q.push({ nx, ny });
			}
		}
	}

	return 0;
}


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

	for (int i = 0; i < n; i++)
	{
		int l;
		cin >> l;
		int startX, startY, endX, endY;
		cin >> startX >> startY >> endX >> endY;

		cout << bfs(l, startX, startY, endX, endY) << "\n";
	}
}

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

우선 트리에 대한 정보를 입력받고 

DFS를 루트노드 1에서 제일 먼 노드를 찾고 그 노드에서 제일 먼 거리를 찾아서 그 거리를 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <cstring> 

using namespace std;

const int MAX = 100001; // 최대 노드 수
vector<pair<int, int>> tree[MAX]; // 트리를 저장할 인접 리스트 (노드 번호, 거리)
bool visited[MAX]; // 방문 여부를 저장
int maxDistance; // 트리의 지름
int farthestNode; // 가장 먼 노드


void dfs(int node, int distance) {
	visited[node] = true;

	// 최대 거리 갱신
	if (distance > maxDistance) {
		maxDistance = distance;
		farthestNode = node;
	}

	// 연결된 노드 방문
	for (auto next : tree[node]) {
		int nextNode = next.first;
		int nextDistance = next.second;

		if (!visited[nextNode]) {
			dfs(nextNode, distance + nextDistance);
		}
	}
}
int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int node;
		cin >> node;
		while (true)
		{
			int Node, distance;
			cin >> Node;
			if (Node == -1) break;

			cin >> distance;
			tree[node].push_back({ Node,distance });
		}
	}

	memset(visited, false, sizeof(visited));
	maxDistance = 0;
	dfs(1, 0); // 임의의 노드(1번)에서 시작

	// 두 번째 DFS 실행
	memset(visited, false, sizeof(visited));
	maxDistance = 0;
	dfs(farthestNode, 0); // 첫 번째 DFS에서 가장 먼 노드를 시작점으로 설정

	// 트리의 지름 출력
	cout << maxDistance << endl;

	return 0;
}

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

이진 트리에 대한 정보를 unordered_map을 통해 저장하고 이를 재귀함수를 통해 전위,중위,후위함수를 통해 순회하면서 출력해주면 된다.

정답코드

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<char, pair<char, char>> tree;

//전위 순회
void preorder(char node)
{
	if (node == '.')return;
	cout << node;
	preorder(tree[node].first);
	preorder(tree[node].second);
}
//중위순회
void inorder(char node)
{
	if (node == '.')return;
	inorder(tree[node].first);
	cout << node;
	inorder(tree[node].second);
}
//후위순회
void postorder(char node)
{
	if (node == '.')return;
	postorder(tree[node].first);
	postorder(tree[node].second);
	cout << node;
}

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

	for (int i = 0; i < n; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;
		tree[parent] = { left, right }; // 부모와 자식 관계 저장
	}

	preorder('A');
	cout << "\n";
	inorder('A');
	cout << "\n";
	postorder('A');
	cout << "\n";

	return 0;
}

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

각 노드에 대한 정보를 벡터로 입력받고 이를  BFS로 순회하면서 부모를 지정해주면 된다. 

만약 1에 6과 4가 연결되어 있다면 1은 루트노드이기 때문에 6와 4의 부모는 1이되는것이다.

정답코드

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

	vector<vector<int>> tree(n + 1);
	vector<int>parent(n + 1, 0);

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}


	//BFS
	queue<int> q;
	q.push(1);
	parent[1] = -1;			//루트노드는 부모x

	while (!q.empty())
	{
		int current = q.front();
		q.pop();

		for (int next : tree[current]) {
			if (parent[next] == 0) { // 아직 방문하지 않은 노드
				parent[next] = current; // 부모 기록
				q.push(next);           // 큐에 추가
			}
		}
	}

	// 결과 출력 (2번 노드부터 N번 노드까지의 부모 출력)
	for (int i = 2; i <= n; i++) {
		cout << parent[i] << '\n';
	}

	return 0;
}

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;
}