코딩생존기

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

그래프를 입력받고 BFS를 통해 모든 노드에서 탐색을 시작하여 모든 노드를 순회하며 하나의 컴퓨터가 몇개의 컴퓨터와 신뢰적인 관계인지 횟수를 더해주면 된다. 그리고 최대 관계 수를 구한 다음 그에 맞는 노드를 출력해주면 된다.

정답코드

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

using namespace std;

void BFS(int node);
vector<vector<int>> computers;
vector<bool> visited;
vector<int> answers;
int main()
{
	int n, m;

	cin >> n >> m;

	computers.resize(n + 1);
	answers.resize(n + 1);
	//그래프 입력
	for (int i = 0; i < m; i++)
	{
		int s, e;
		cin >> s >> e;
		computers[s].push_back(e);
	}

	visited.resize(n + 1);

	//BFS
	for (int i = 1; i <= n; i++)
	{
		fill(visited.begin(), visited.end(), false);
		BFS(i);
	}

	//최대값 찾기
	int max_val = 0;
	for (int i = 1; i <= n; i++)
	{
		max_val = max(max_val, answers[i]);
	}

	//검사
	for (int i = 1; i <= n; i++)
	{
		if (answers[i] == max_val)
		{
			cout << i << " ";
		}
	}
	

	return 0;
}

void BFS(int node)
{
	queue<int> q;
	q.push(node);
	visited[node] = true;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i : computers[cur])
		{
			if (visited[i] == false)
			{
				visited[i] = true;
				//몇개의 컴퓨터랑 관계되어 있는지
				answers[i]++;
				q.push(i);
			}
		}
	}
}

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

그래프를 입력받고 BFS를 통해 X부터 경로를 탐색하면서 각 도시 까지의 거리를 기록한다.

BFS를 통한 순회가 끝나면 x로 부터 k거리에 있는 도시를 오름차순으로 출력해주면 된다.

정답코드

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

using namespace std;

void BFS(int node);

vector<vector<int>> cities;
vector<int> visitied;
vector<int> answer;
int main()
{
	int n, m, k, x;

	cin >> n >> m >> k >> x;

	cities.resize(n + 1);

	//그래프 입력받기
	for (int i = 0; i < m; i++)
	{
		int s, e;
		cin >> s >> e;
		cities[s].push_back(e);
	}

	visitied.resize(n + 1);

	//초기값 세팅
	for (int i = 0; i <= n; i++)
	{
		visitied[i] = -1;
	}

	BFS(x);

	for (int i = 0; i <= n; i++)
	{
		if (visitied[i] == k) answer.push_back(i);
	}

	if (answer.empty()) cout << "-1" << "\n";
	else
	{
		sort(answer.begin(), answer.end());
		for (int tmp : answer)
		{
			cout << tmp << "\n";
		}
	}
}


void BFS(int node)
{
	queue<int> q;
	q.push(node);
	visitied[node]++;

	while (!q.empty())
	{
		int cur = q.front();
		q.pop();
		for (int i : cities[cur])
		{
			if (visitied[i] == -1)
			{
				visitied[i] = visitied[cur] + 1;
				q.push(i);
			}
		}
	}
}

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

이 문제는 규칙을 찾아서 점화식으로 만들고 매번 n번째까지 계산을 하면 시간 초과가 뜨기 때문에 미리 100개를 계산해두고 필요한 부분만 꺼내 쓰게 구현하면 된다. 

이때 규칙은 그림을 보면 n-2번째하고 n-3번째 삼각형의 한변의 길이를 더하면 n번째 삼각형의 한변의 길이가 되는 것을 볼 수 있다. 이때 100번째 까지 가다보면 값이 커질 수 있기 때문에 long배열을 사용하자

정답코드

#include <iostream>

using namespace std;

int main()
{
    int t;

    cin >> t;

    long p[101] = { 0 };

    p[1] = p[2] = p[3] = 1;

    // 배열 미리 계산 
    for (int i = 4; i <= 100; i++) {
        p[i] = p[i - 2] + p[i - 3];
    }

    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << p[n] << endl;
    }

    return 0;
}

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

시간제한이 0.75초 라서 점화식을 찾고 이를 동적 계획법으로 풀어서 시간 복잡도를 줄여야한다. 

일단 쓸 수 있는 타일은 00 또는 1 이다.

1번째일때, 1개

2번째일때, 2개이다. 

이후를 생각해보자면 

1을 붙이는 경우는  n-1길이의 숫자 뒤에 붙이면 된다.

00을 붙이는 경우는 n-2길이의 숫자 뒤에 붙이면 된다. 

이를 통해 점화식 dp[n] = dp[n-1] + dp[n-2] 

즉 n-1에 1을 붙이는 경우와 n-2에 00을 붙이는 경우를 더 해주면 되는 것이다.

정답코드

#include <iostream>

using namespace std;

//dp활용 : 점화식을 구해야한다.
int main()
{
	int n;

	cin >> n;

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

	int p1 = 1;			//p[n-2]
	int p2 = 2;			//p[n-1]
	int p_n = 0;

	//dp계산
	for (int i = 3; i <= n; i++)
	{
		p_n = (p1 + p2) % 15746;
		p1 = p2;
		p2 = p_n;
	}

	cout << p2 << endl;

	return 0;
}

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

문제에서 주어진 의사코드를 3차원배열을 선언해주고 조건에 해당하는 값이라면 재귀함수를 통해 이 3차원배열을 초기화해주고 만약 이미 있는 값이라면 그 값을 반환해주는 방식으로 DP를 활용하는 방식이다.

정답코드

#include <iostream>

using namespace std;

int dp[51][51][51];

int w(int a, int b, int c) 
{
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;

	if (a > 20 || b > 20 || c > 20) 
		return w(20, 20, 20);

	// 이미 저장된 값이 있다면 재활용 : DP
	if (dp[a][b][c] != 0) {
		return dp[a][b][c];
	}

	if (a < b && b < c)
	{
		dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	else
	{
		dp[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
	}

	return dp[a][b][c];
}

int main()
{
	int a, b, c;



	while (true)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;

		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
	}

	return 0;
}

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

의사코드를 보고 피보나치 수를 구하는 2가지 함수를 만들고 코드1 코드2번 자리에 횟수를 기록하는 부분을 추가해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int cnt1 = 0; // 재귀 호출 횟수 카운트

// 재귀 방식 피보나치 함수
long fib(int n) {
    if (n == 1 || n == 2) {
        cnt1++;
        return 1;
    }
    else {
        return (fib(n - 1) + fib(n - 2));
    }
}

// 동적 프로그래밍 방식 피보나치 함수
int fib2(int n) {
    vector<int> f(n + 1); // 배열 크기를 n + 1로 선언
    f[1] = f[2] = 1;
    int cnt2 = 0;

    // 피보나치 수열 계산 및 코드2 실행 횟수 카운트
    for (int i = 3; i <= n; i++) {
        f[i] = f[i - 1] + f[i - 2];
        cnt2++;
    }

    return cnt2; // 코드2 실행 횟수 반환
}

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

    fib(n); // 재귀 피보나치 계산
    int cnt2 = fib2(n); // 동적 프로그래밍 피보나치 계산

    cout << cnt1 << " " << cnt2 << endl;

    return 0;
}

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

조합을 통해 풀 수 있는 문제이다. mCn을 통해 다리를 지을 수 있는 경우의 수를 출력해주면 된다.

정답코드

#include <iostream>

using namespace std;

int combination(int n, int k) {
	if (k > n - k) k = n - k;  // 계산량을 줄이기 위해 k를 더 작은 값으로 설정
	long long result = 1;
	for (int i = 0; i < k; i++) {
		result *= (n - i);
		result /= (i + 1);
	}
	return result;
}

int main()
{
	int t;

	cin >> t;

	for (int i = 0; i < t; i++)
	{
		int n, m;
		cin >> n >> m;
		cout << combination(m, n) << endl;
	}
}

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

조합의 경우의 수를 구하는 코드를 만들어주면 된다. n을 k번 1씩 줄이면서 곱해준 값과 k를 k번 1씩 줄이면서 곱해준 값을 나눠주면 된다.

정답코드

#include <iostream>

using namespace std;

int main()
{
	int n, k;

	cin >> n >> k;

	if (k > n - k) {
		k = n - k;  // nCk == nC(n-k), 계산량 줄이기 위해 k를 더 작은 값으로 설정
	}

	int a = 1, b = 1;

	for (int i = 0; i < k; i++)
	{
		a *= (n - i);
		b *= (k - i);
	}

	cout << a / b << endl;
}

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

팩토리얼을 구현하면 되는 문제이다. 나는 재귀함수를 사용하여 구현해주었다. 1보다 작다면 1을 반환해주고 아니라면

n* fac(n-1)을 통해 n~ 1까지의 팩토리얼 값을 계산하도록 했다.

이때 팩토리얼 결과값이 클 수 있어서 long값을 반환하도록 해주었다. 

정답코드

#include <iostream>

using namespace std;

long fac(int n)
{
	if (n <= 1)return 1;
	else return n * fac(n-1);
}

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


	cout << fac(n) << endl;
}

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

간단하게 생각해봤을 때, 한층이 올라갈때마다 모든 경로는 피라미드 구조상 각 블록마다 두 가지 선택지를 갖게되기 때문에 전체 경우의 수는 2^n이라고 볼 수 있을 것 같아서 이렇게 계산하고 출력해주었다.

정답코드

#include <iostream>
#include <cmath>

using namespace std;

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

	cout << pow(2, n) << endl;
}