개발공부기록

1. 문제

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

2. 적용할 알고리즘

처음에는 단순히 BFS로 하다가

결국에는 알고리즘 분류를 보고 "벨만포드"를 처음으로 알게 되었다.

벨만포드 알고리즘은 그래프에서 간선의 값이 음수일 때 사용하여

한 노드에서 다른 노드까지의 최소 거리를 알아낼 수 있다.

다익스트라 알고리즘과 비슷하나 그리디한 접근 방식을 사용하지 않고

각각의 반복마다 모든 간선을 확인하여 O(VE)가 되서 다익스트라에 비해

시간이 더 오래 걸린다.

하지만 간선의 값이 음수일 때 사용할 수 있다는게 장점이다.

3. 풀이

이 문제에서 원하는 것은 한 노드에서 출발하여 같은

노드로 시간이 0보다 적게 걸려 도착할 수 있냐는 것이다.

이 말은 그 노드에서 출발하여 되돌아올 수 있는 음수 사이클이 존재하여

그 사이클이 돌 때마다 시간을 줄일 수 있냐는 말이 된다.

위 그림처럼 음수 사이클이 만들어지게 된다면

노드 1에서 다른 노드까지 걸리는 시간은 값이 -4인 간선 때문에

계속해서 작아져 음수가 될 것이고

그 노드까지 걸리는 시간이 음수가 된다면

원래 위치로 돌아 왔을 때 시간이 되돌아간 경우가 된다.

따라서, "음수 사이클이 존재한다면 시간이 되돌아간 경우가 있다"

음수 사이클 존재의 확인을 벨만포드 알고리즘을 통해 알 수 있다.

노드의 개수가 n일 때, n - 1번 동안

각 간선을 거쳐 해당 노드로 가는 비용을 계산하여

최단 거리 테이블을 갱신하고 난 후 한 번 더 계산을 수행한다.

만약 갱신이 또 일어난다면 그것은 음수 사이클이 존재한다는 의미이다.

아무 갱신이 일어나지 않고 최단 거리 테이블이 완성됐다면 음수 사이클이 없다는 의미이다.

4. 코드

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

typedef long long ll;

const int INF = 1000'0000;

vector<pair<int, int>> adj[505];

int n, m, w;

int d[505];

bool bf()
{
    fill(d, d + 505, INF);
    
    d[1] = 0;

//n - 1번 동안 모든 간선을 확인해가며 최소 비용을 계산한다.
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (auto nxt : adj[j])
            {
                d[nxt.first] = min(d[nxt.first], d[j] + nxt.second);
            }
        }
    }

//음수 사이클이 존재하는지 확인한다.
    for (int j = 1; j <= n; j++)
    {
        for (auto nxt : adj[j])
        {
            if (d[j] + nxt.second < d[nxt.first]) return true;
        }
    }

    return false;
}

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

    int t;
    cin >> t;

    while (t--)
    {
        cin >> n >> m >> w;

        for (int i = 1; i <= n; i++) adj[i].clear();

        for (int i = 0; i < m; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({ e, t });
            adj[e].push_back({ s, t });
        }

        for (int i = 0; i < w; i++)
        {
            int s, e, t;
            cin >> s >> e >> t;

            adj[s].push_back({ e, -t });
        }
        cout << (bf() ? "YES" : "NO") << '\n';
    }


}

5. 느낀 점

그래프 문제에서 다익스트라, 벨만포드, 플로이드 알고리즘은

가끔 나오긴 하지만 유용하게 쓰일 때가 있으니 이에 대한

배경지식을 잘 쌓아놓도록 하자...

1. 문제

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

2. 적용할 알고리즘

큐에 명령을 사용한 순서를 string으로 저장하고 bfs를 돌리면 될 것 같다

3. 풀이

큐에서 숫자를 뽑아내 다음 숫자를 선택하는 연산을 그 때 마다 수행하니 시간 초과가 났다.

따라서 res[i][j] 이차원 배열에 숫자 i에서 연산을 하여 나오는 숫자를 j(0, 1, 2, 3)에 미리 저장해놓고

테스트케이스마다 저장해놓은 정보를 가져다 쓰기만 하면 시간을 줄일 수 있다.

시간 제한이 좀 애매하긴 했다. 고작 1/4 줄인다고 해결될 것 같지 않아서 이 방식을 생각하지 않은 것 같다.

테스트 케이스가 여러 개 주어지는 문제에서 미리 필요한 정보를 계산해놓고 정보를 가져다 쓰는 방식을 사용하여 시간을 줄일 수 있다는 걸 기억하자.

4, 코드

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>

using namespace std;

typedef long long ll;

string vis[10005];

int FuncD(int num)
{
    return num * 2 % 10000;
}

int FuncS(int num)
{
    if (num == 0) num = 9999;
    else num--;

    return num;
}

int FuncL(int num)
{
    return (num % 1000) * 10 + num / 1000;
}

int FuncR(int num)
{
    return (num % 10) * 1000 + num / 10;
}

int res[10005][4];

char c[4] = { 'D', 'S', 'L', 'R' };

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

    int t;
    cin >> t;

    for (int i = 0; i <= 9999; i++)
    {
        res[i][0] = FuncD(i);
        res[i][1] = FuncS(i);
        res[i][2] = FuncL(i);
        res[i][3] = FuncR(i);
    }

    while (t--)
    {
        vector<bool> vis(10005);

        int a, b;
        cin >> a >> b;

        string s;

        queue<pair<int, string>> Q;
        Q.push({ a, "" });
        vis[a] = 1;

        while (!Q.empty())
        {
            int cn;
            string cs;
            tie(cn, cs) = Q.front(); Q.pop();

            if (cn == b)
            {
                cout << cs << '\n';
                break;
            }

            for (int i = 0; i < 4; i++)
            {
                int nn = res[cn][i];
                string ns = cs;

                if (vis[nn]) continue;

                ns.push_back(c[i]);
                Q.push({ nn, ns });
                vis[nn] = 1;
                
            }
        }
    }
}

1. 문제

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

2. 적용할 알고리즘

문자열...?

3. 풀이

처음에는 c++ string의 find를 이용해 풀려고 했지만 n과 m이 100만으로 아주 크기 때문에

새로운 방법을 생각해야 한다.

문제에서 원하는 건 IOI, IOIOI, IOIOIOI.... 가 입력받은 문자열에 몇 번 들어가는지를 알아내는 것이다.

여기서 눈에 띄는 건 P(n)이 항상 IOI를 포함하고 있다는 것이고 n은 IOI가 몇 번 포함되었는지를 나타낸다.

따라서 IOI가 연속으로 몇 번 나왔는지를 체크하면 된다.

예를 들어, n이 3일 때 IOI가 연속으로 3번나왔다면 IOIOIOI가 문자열에 포함되었다는 뜻이 된다.

이를 구현한 코드는 다음과 같다.

4. 코드

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

using namespace std;

typedef long long ll;

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

    int n, m;
    string s;

    cin >> n;
    cin >> m;
    cin >> s;

    int ans = 0;

    for (int i = 0; i < s.size(); i++)
    {
        int k = 0;

        if (s[i] == 'I')
        {
            while (s[i + 1] == 'O' && s[i + 2] == 'I')
            {
                k++;
                if (n == k)
                {
                    ans++;
                    k--;
                }
                i += 2;
            }
        }
    }

    cout << ans;
}

1. 문제

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

2. 문제의 요구

체스에서 대각선으로 공격할 수 있는 "비숍"을 서로 공격하지 못하도록

체스판에 배치할 수 있는 최대 개수를 구하여라.

3. 풀이

#적용할 알고리즘 : 백트래킹

일단은 단순하게 모든 칸에 대해 각 비숍을 배치할 때 마다

그 대각선 방향에 전에 배치했던 비숍의 유무를 확인하고 없다면

그 자리에 배치하는 방식의 알고리즘을 생각할 수 있다.

하지만 이런 방식은 시간초과가 났다.

여기서 새로운 발상이 필요한데 그것은 바로

#새로운 발상 : 비숍을 놓을 때 체스판의 검은 부분과 흰 부분은 서로 관련이 없다.

비숍을 흰 부분에 놓으면 그 비숍이 공격할 수 있는 곳은 흰 부분 뿐이다.

따라서 체스판의 흰 부분과 검은 부분을 분리하여 따로 백트래킹한다.

이렇게 하면 (10 * 10) = 100 에서 ((5 * 5) * 2) = 50 이 되기 때문에 확실한 이득을 볼 수 있다.

4. 코드

#include<iostream>
#include<string>
#include<stack>
#include<tuple>
#include<queue>
#include<algorithm>
#include<bitset>

using namespace std;

#define endl (cout << '\n')

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

int n;

int board[12][12];
bool isUsed[12][12];

vector<pair<int, int>> white;
vector<pair<int, int>> black;

int mx = 0;

//대각선 라인에 다른 비숍이 있는지 확인
//있으면 => 되돌아감
//없으면 => 계속
bool Check(int x, int y)
{
    for (int dir = 0; dir < 4; dir++)
    {
        for (int i = 0; true; i++)
        {
            if (x + i * dx[dir] < 0 || x + i * dx[dir] >= n || y + i * dy[dir] < 0 || y + i * dy[dir] >= n) break;
            //cout << x << ' ' << y << '\n';
            //cout << i << ' ' << dx[dir] << ' ' << dy[dir] << ' ' << x + i * dx[dir] << ' ' << y + i * dy[dir] << '\n';
            if (isUsed[x + i * dx[dir]][y + i * dy[dir]])
            {
                return false;
            }
        }
    }
    return true;
}

//백트래킹
void solve(int cur, vector<pair<int, int>>& color, int start)
{
    mx = max(mx, cur);

    if (cur == color.size()) return;

    for (int i = start; i < color.size(); i++)
    {
        int cx, cy;
        tie(cx, cy) = color[i];

        if (isUsed[cx][cy]) continue;

        if (Check(cx, cy))
        {
            isUsed[cx][cy] = 1;
            solve(cur + 1, color, i + 1);
            isUsed[cx][cy] = 0;
        }
    }
}

bool isWhite[12][12];

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

    cin >> n;

    for (int i = 0; i < n; i += 2) isWhite[0][i] = 1;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            isWhite[i][j] = (isWhite[i - 1][j] ? false : true);
        }
    }

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 1)
            {
            ///화이트 칸과 블랙 칸을 나눠서 벡터에 저장
                if (isWhite[i][j]) white.push_back({i, j});
                else black.push_back({ i, j });
            }
        }
    }

    int ans = 0;

	//화이트 칸과 블랙칸이
	//서로 연관이 없기 때문에 가능하다
	//화이트 칸에서 비숍 배치
    solve(0, white, 0);
    ans += mx;
    mx = 0;
    //블랙 칸에서 비숍 배치
    solve(0, black, 0);
    ans += mx;

    cout << ans;

}

5. 느낀 점

시간을 줄일 방법이 생각이 안나서 결국 답을 찾아봤다.

이런 발상을 좀 더 쉽게 할 수 있도록 계속 생각해야한다.

1. 문제

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

2. 문제의 요구

빈칸을 채워 스도쿠를 완성하라!

3. 적용할 알고리즘

백트래킹이 가능하다.

처음에는 빈칸이 10개인 경우 9의 10승으로 시간초과가 날 거라 예상했지만

빈칸을 채울 때마다 조건 확인을 해주면 그 다음 재귀로 넘어가는 경우의 수는 많이 줄어든다.

4. 설명

빈칸에 1~9까지 수를 대입해보고

스도쿠 조건에 만족하지 않는다면 그 경우는 패스하고,

만족한다면 다음 빈칸으로 넘어간다.

만약 만족하는 수가 없다면 이전 선택이 잘못된 것이므로

이전의 빈칸으로 돌아간다.

빈칸이 모두 채워졌다면 종료한다.

5. 코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<tuple>

using namespace std;

const int INF = 0x7f7f7f7f;

typedef long long ll;

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

int board[10][10];

vector<pair<int,int>> zero;

bool Check(int x, int y, int num)
{
	for (int i = 0; i < 9; i++)
	{
		if (board[i][y] == num) return false;
		if (board[x][i] == num) return false;
	}

//주변 9개 칸 중 같은 것이 있는지 확인
//*주의* C언어에서 x / 3 * 3 != x 이다. 
// '/'연산은 나머지를 날려버리기 때문이다.
	for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++)
	{
		for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++)
		{
			if (board[i][j] == num) return false;
		}
	}

	return true;
}

int ans[10][10];

void solve(int cur)
{
//빈 칸을 다 채웠을 시 종료
	if (cur == zero.size())
	{
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++) ans[i][j] = board[i][j];
		return;
	}

	int cx, cy;
	tie(cx, cy) = zero[cur];

//적절한 수인지 확인 후 다음 빈칸으로 넘어간다
	for (int i = 1; i <= 9; i++)
	{
		if (Check(cx, cy, i))
		{
			board[cx][cy] = i;
			solve(cur + 1);
			board[cx][cy] = 0;
		}
	}
}

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

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			cin >> board[i][j];
			if (board[i][j] == 0) zero.push_back({ i, j });
		}
	}

	solve(0);

	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++) cout << ans[i][j] << ' ';
		cout << '\n';
	}
}

6. 느낀 점

그냥 대충 순열, 조합 등으로 계산하고 백트래킹 불가로 생각하지 말고

어떠한 조치를 취하면 백트래킹의 시간복잡도가 대폭 줄어들어

완전탐색이 가능하다는 걸 기억하자

1. 문제

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

2. 문제에서 원하는 것

A와 B의 좌표가 주어지고 A와 C, B와 C 사이의 거리가

주어질 때 C가 있을 수 있는 위치의 개수는?

3. 적용할 알고리즘

기하, 두 원의 교점

4. 설명

C와의 거리를 이용하면 C가 있을 수 있는 곳을 원으로 표현 가능 하다.

따라서 두 점으로 부터의 거리를 모두 만족하는

두 원의 교점이 C가 있을 수 있는 점이된다.

그리고 두 점 사이의 거리 dis, r1 + r2와 r1 - r2(r1 > r2일 때)의 값을 이용해

교점이 몇 개 생기는지 알 수 있다.

1) dis > r1 + r2

교점이 생기지 않는다.

2) dis == r1 + r2

교점이 하나 생긴다(외접)

3) dis < r1 + r2

의 경우는 r1 - r2에 따라 또 세 가지로 나뉜다.

3-1) dis > r1 - r2

교점이 두개 생긴다

3-2) dis == r1 - r2

교점이 하나 생긴다(내접)

3-3) dis < r1 - r2

큰 원 안에 작은 원이 있다, 교점이 없다

예외) x1 == x2 && y1 == y2 && r1 == r2

두 원이 완전히 겹친다 => 교점이 무한하다.

5. 코드

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<tuple>

using namespace std;

const int INF = 0x7f7f7f7f;

typedef long long ll;

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

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

	int t;
	cin >> t;
	while (t--)
	{
		int x1, y1, r1, x2, y2, r2;
		cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;

		int dis = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
		int bigger, smaller;
		if (r1 < r2)
		{
			bigger = r2;
			smaller = r1;
		}
		else
		{
			bigger = r1;
			smaller = r2;
		}

		int sum = bigger + smaller; sum *= sum;
		int sub = bigger - smaller; sub *= sub;

		int ans = 0;

		if (dis > sum)//접하지 않음
			ans = 0;
		else if (dis == sum) //외접한다
			ans = 1;
		else
		{
			if (dis > sub) // 두 점에서 만난다
				ans = 2;
			else if (dis == sub) // 내접한다
				ans = 1;
			else //큰 원 안에 작은 원이 있다
				ans = 0;
		}

		if (r1 == r2 && x1 == x2 && y1 == y2) //똑같다 == 교점이 무한
			ans = -1;

		cout << ans << '\n';
	}
}

6. 느낀 점

이러한 기초적인 수학, 기하학적 논리는 기억해두도록 하자...

1. 문제 :https://www.acmicpc.net/problem/16987

2. 문제에서 원하는 것

계란을 왼쪽에서 오른쪽으로 한 칸씩 움직이며 맨 오른쪽 끝에 있는 계란 까지 손에 들고

다른 임의의 계란을 들어서 부딪혔을 때 계란을 최대 몇 개 깰 수 있는가?

3. 적용할 알고리즘

총 계란의 개수가 8개이므로 계란을 들고 어떤 계란과 부딪힐지 모든 경우의 수를

조사하면 총 연산 횟수는 대략 최대 7의 8승(5,764,801)이 되어서

백트래킹을 이용한 완전 탐색이 가능하다.

4. 수학적 사고, 새로운 발상

필요 없음, 그냥 단순한 백트래킹

5. 코드

#include<iostream>
#include<string>
#include<stack>
#include<tuple>
#include<queue>
#include<algorithm>
#include<bitset>

using namespace std;

int n;

pair<int, int> egg[10];

int ans = 0;

void solve(int cur)
{
    if (cur == n)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            //cout << egg[i].first << ' ';
            if (egg[i].first <= 0) cnt++;
        }
        ans = max(ans, cnt);
        return;
    }

    if (egg[cur].first <= 0)
    {
        solve(cur + 1);
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (cur == i) continue;
        if (egg[i].first <= 0) continue;

        egg[cur].first -= egg[i].second;
        egg[i].first -= egg[cur].second;
        solve(cur + 1);
        egg[cur].first += egg[i].second;
        egg[i].first += egg[cur].second;
    }

    if (cur == n - 1) solve(cur + 1);
}

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

    cin >> n;
    
    for (int i = 0; i < n; i++) cin >> egg[i].first >> egg[i].second;

    solve(0);

    cout << ans;
}

6. 느낀 점

쉬운 문제인데 문제 잘못읽어서 1시간 동안 뻘짓했다ㅋㅋ

앞으로는 문제를 잘 읽고 풀이가 확실히 떠오를 때 구현을 시작하자...