코딩생존기

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

수열을 입력받고 정렬한 다음에 제일 작은 쪽의 인덱스를 가리키는 수 하나와 제일 큰 쪽의 인덱스를 가리키는 수를 통해 문제를 해결하면 된다. 만약 목표로 하는 수보다 크다면 큰 쪽의 인덱스를 줄여주고 목표로 하는 수보다 작다면 작은 쪽의 인덱스를 증가시켜주고 만약 같다면 작은 쪽은 증가시켜주고 큰 쪽은 감소시키고 횟수 카운트를 증가시켜주면 된다.

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n; // 수열 크기
    vector<int> v(n);

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

    sort(v.begin(), v.end()); // 수열 정렬

    int target, cnt = 0;
    cin >> target; // 목표 합

    int p = 0, q = n - 1; // 투 포인터 초기화

    while (p < q) {
        int sum = v[p] + v[q];
        if (sum == target) { // 목표 합과 같으면
            cnt++;
            p++;    
            q--;    
        }
        else if (sum < target) {
            p++;    // 합이 작으면 작은 값을 증가
        }
        else {
            q--;    // 합이 크면 큰 값을 감소
        }
    }

    cout << cnt << endl; // 쌍의 개수 출력

    return 0;
}

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

n개 만큼의 좌표를 입력받고 이를 정렬한 다음, 이분 탐색을 활용하여 해결한다. 

1. 공유기 사이의 거리(간격)를 기준으로 최소 거리 low와 최대 거리 high를 설정한다.

2. mid 값을 기준으로 mid 이상인 위치에 공유기를 배치해보고, 설치 가능한 공유기의 개수보다 많다면 거리를 늘려보고, 그렇지 않으면 줄인다.

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    vector<int> house(n);
    for (int i = 0; i < n; i++) {
        cin >> house[i];
    }

    // 집 좌표 정렬
    sort(house.begin(), house.end());

    int low = 1; // 최소 거리
    int high = house[n - 1] - house[0]; // 최대 거리
    int result = 0;

    while (low <= high) {
        int mid = (low + high) / 2; // 현재 거리
        int prev = house[0]; // 첫 번째 집에 공유기를 설치
        int count = 1; // 설치된 공유기 개수

        // 공유기 설치
        for (int i = 1; i < n; i++) {
            //현재거리보다 멀리떨어진 집에 공유기 설치
            if (house[i] - prev >= mid) {
                count++;
                prev = house[i];
            }
        }

        // 공유기 개수가 많으면 거리 증가
        if (count >= c) {
            result = mid; // 현재 거리 저장
            low = mid + 1;
        }

        // 공유기 개수가 부족하면 거리 감소
        else {
            high = mid - 1;
        }
    }

    cout << result << endl;

    return 0;
}

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

백트래킹을 사용하여 퀸의 위치를 탐색해야하는 문제이다. 한 행에서 열마다 퀸을 배치해보면서 현재 위치에 퀸을 놓을 수 있는지 검사하고 퀸을 놓고 놓을 수 없다면 skip하는 방식으로 진행한다 이 과정에서 만약 끝 행에 도달했다면 경우의 수를 하나 추가해준다. 

정답코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int result = 0;
vector<int> board;

bool isSafe(int row, int col)
{
	//한행씩 탐색
	for (int i = 0; i < row; i++)
	{
		//같은열 | 대각선
		if (board[i] == col || abs(board[i] - col) == row - i)
			return false;
	}

	return true;
}

void solve(int row) {
    if (row == n) {     //만약 끝에 도달했다면
        result++;       //경우의 수 추가
        return;
    }

    for (int col = 0; col < n; col++) {
        if (isSafe(row, col)) { // 현재 위치에 퀸을 놓을 수 있다면
            board[row] = col;  // 퀸을 놓음
			solve(row + 1); // 다음 행으로 진행
        }
    }
}

int main()
{
	cin >> n;
	board.resize(n);
	solve(0);

	cout << result << "\n";

	return 0;
}

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

priority_queue를 사용해서 입력받는 수에 따라 push와 pop을 진행해주면 된다. 

정답코드

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

int main()
{

	ios::sync_with_stdio(false);  // C와 C++의 I/O 동기화 비활성화
	cin.tie(NULL);  // 입출력 독립 처리

	int n;
	cin >> n;
	priority_queue<int> pq;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		if (x > 0)
		{
			pq.push(x);
		}
		else
		{
			if (!pq.empty())
			{
				cout << pq.top() << "\n";
				pq.pop();
			}
			else
			{
				cout << 0 << "\n";
			}
		}
	}

	return 0;
}

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

m,n,h값을 통해 3차원 벡터를 초기화 해주고 1인 부분을 queue에 저장하고 이를 BFS방식으로 순회하면서 1인 부분을 추가하고 이 추가한 값을 다시 queue에 넣어서 날마다 반복해주면 된다. 전체 개수와 익은 개수를 비교하기 위해 빈것도 포함해서 개수를 추가해줬다. 

정답코드

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

using namespace std;

// 6방향 이동 (위, 아래, 좌, 우, 앞, 뒤)
int dx[6] = { 0, 0, 0, 0, -1, 1 };
int dy[6] = { 0, 0, -1, 1, 0, 0 };
int dz[6] = { -1, 1, 0, 0, 0, 0 };

int main() {
    int m, n, h;
    cin >> m >> n >> h;

    vector<vector<vector<int>>> tomato(h, vector<vector<int>>(n, vector<int>(m)));
    queue<pair<int, pair<int, int>>> q;  // 큐에 (z, x, y) 좌표 저장

    int empty_count = 0;  // 비어 있는 칸 개수

    // 입력 받기
    for (int z = 0; z < h; z++) {
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < m; y++) {
                cin >> tomato[z][x][y];
                if (tomato[z][x][y] == 1) {
                    q.push({ z, {x, y} });  // 익은 토마토 위치 큐에 삽입
                }
                else if (tomato[z][x][y] == -1) {
                    empty_count++;  // 비어 있는 칸 카운트
                }
            }
        }
    }

    int total_cells = n * m * h - empty_count;  // 전체 칸에서 비어 있는 칸 제외
    int ripe_count = q.size();  // 초기 익은 토마토 개수
    int days = -1;

    // 이미 모든 토마토가 익어 있는 경우
    if (ripe_count == total_cells) {
        cout << 0 << '\n';
        return 0;
    }

    // BFS 수행
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int z = q.front().first;
            int x = q.front().second.first;
            int y = q.front().second.second;
            q.pop();

            for (int d = 0; d < 6; d++) {
                int nz = z + dz[d];
                int nx = x + dx[d];
                int ny = y + dy[d];

                // 배열 범위 체크 및 익지 않은 토마토 찾아서 익히기
                if (nz >= 0 && nz < h && nx >= 0 && nx < n && ny >= 0 && ny < m && tomato[nz][nx][ny] == 0) {
                    tomato[nz][nx][ny] = 1;  // 익은 토마토로 상태 변경
                    q.push({ nz, {nx, ny} });  // 큐에 추가
                    ripe_count++;  // 익은 토마토 수 증가
                }
            }
        }
        days++;  // 하루가 지나면
    }

    // 모든 칸이 익었는지 확인
    if (ripe_count == total_cells) {
        cout << days << '\n';  // 모든 토마토가 익었으면 소요된 일수 출력
    }
    else {
        cout << -1 << '\n';  // 익지 않은 토마토가 남았으면 -1 출력
    }

    return 0;
}

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

2차원 벡터를 통해 토마토가 있는 곳을 입력받고 출발점이 되는 1을 모두 큐에 저장하고 이 q를 BFS로 순회하면서 토마토가 있는 곳을 익게하고 이 익은 토마토가 다시 출발점이 되어서 이 큐가 빌때까지 계속하면 된다. 

전체가 다 익었는지 확인하기 위하여 비어있는 토마토의 개수도 같이 세어준다. 

정답코드

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

using namespace std;


int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

int main()
{
	int m, n;
	cin >> m >> n;
	vector<vector<int>> tomato(n, vector<int>(m));
	queue<pair<int, int>> q;		//출발점 큐
	int empty_count = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) {
				q.push({ i, j }); // 익은 토마토의 위치 저장
			}
			else if (tomato[i][j] == -1) {
				empty_count++; // 비어있는 칸 개수 카운트
			}
		}
	}

	int days = -1;
	int total_cells = n * m;
	int ripe_count = q.size() + empty_count; // 초기 익은 토마토와 비어있는 칸
	

	while (!q.empty())
	{
		int size = q.size();
		for (int i = 0; i < size; i++)
		{
			int x = q.front().first;
			int y = q.front().second;
			q.pop();

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

				if (nx >= 0 && nx < n && ny >= 0 && ny < m && tomato[nx][ny] == 0)
				{
					tomato[nx][ny] = 1;
					q.push({ nx,ny });
					ripe_count++;
				}
			}
		}
		days++;
	}

	// 모든 칸이 익었는지 확인
	if (ripe_count == total_cells) {
		cout << days << '\n';
	}
	else {
		cout << -1 << '\n';
	} return 0;

	return 0;
}

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