언제나 처음처럼

[문제 링크]

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

간단한 그래프 탐색 문제였다.

리프노드를 찾는 탐색은 부모노드에서 자식노드 방향으로의 탐색만 필요하기 때문에 단방향 그래프로 구성하였고,
트리 구조로 구성된 그래프 특성 상 간선의 수가 많지 않다는 특징이 있기 때문에 인접리스트로 그래프를 표현하여 공간복잡도를 최적화하였다.

한가지 예외사항으로 루트노드가 제거될 경우 트리 자체가 제거되기 때문에 루트노드와 제거한 노드를 비교하는 로직을 추가하였다.

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

int getLeafNodeCount(const vector<vector<int>>& tree, int rootNode)
{
	int LeafNodeCnt = 0;

	//DFS
	vector<bool> visited(tree.size());

	stack<int> stk;
	stk.push(rootNode);
	visited[rootNode] = true;

	while (!stk.empty())
	{
		int here = stk.top();
		stk.pop();

		if (tree[here].empty())
			LeafNodeCnt++;
		else
		{
			for (const int child : tree[here])
			{
				if (!visited[child])
				{
					stk.push(child);
					visited[child] = true;
				}
			}
		}
	}

	return LeafNodeCnt;
}

int main(void)
{
	int N;
	cin >> N;

	vector<vector<int>> tree(N);
	int rootNode = -1;

	for (int i = 0; i < N; i++)
	{
		int parent;
		cin >> parent;

		if (parent != -1)
		{
			tree[parent].push_back(i);
		}
		else
		{
			rootNode = i;
		}
	}

	int removeNode;
	cin >> removeNode;

	for (auto& parentTree : tree)
	{
		bool isRemoved = false;
		for (vector<int>::iterator iter = parentTree.begin(); iter != parentTree.end(); iter++)
		{
			if (*iter == removeNode)
			{
				parentTree.erase(iter);
				isRemoved = true;
				break;
			}
		}
		if (isRemoved)
			break;
	}

	if (rootNode == -1 || rootNode == removeNode)
		cout << 0;
	else
		cout << getLeafNodeCount(tree, rootNode);

	return 0;
}

[문제 링크]

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

재귀 호출을 이해하고 있는지 물어보는 문제였다.

(100+1+) 패턴 동작 요약

1. 먼저 "100" 이 정확히 나오는지 확인한다.
2. 그 뒤의 0들을 모두 소비한다. → 100+
3. 그 다음에는 반드시 1이 하나 이상 나와야 한다.
4. 1+ 구간에서는
   • 1을 하나씩 소비할 때마다, 그 시점(idx)부터 나머지 문자열이 다시 (100+1+ | 01)+ 를 만족하는지 재귀적으로 검사한다.
   • 어느 위치에서든 재귀 함수가 true 를 반환하면 전체도 true
5. 1들을 다 소비한 뒤
   • 문자열이 딱 끝났으면 → 성공
   • 그 뒤에 문자가 더 있으면 → 그 위치부터 다시 isContact 를 호출해 이어지는 패턴인지 검사

(01) 패턴 동작 요약

1. "01"이 정확히 나오는지 확인한다.
2. "01"을 소비한 뒤
   
   • 문자열이 끝났을 경우 → 성공
   • 그 뒤에 문자가 더 있으면 → 그 위치부터 다시 isContact 를 호출해 이어지는 패턴인지 검사

4. 종료 조건과 결과

• 재귀 호출이 문자열 끝까지 도달하면서 모든 구간이
  100+1+ 또는 01 패턴으로만 나누어지면 → "YES"
• 중간에 어느 위치에서든 패턴이 깨지면 → "NO"

5. 시간 복잡도

• 문자열 길이가 최대 200이고, 각 인덱스가 유효하게 검사되는 횟수는 제한적이라 최악의 경우 O(N^2) 수준에서 충분히 통과 가능하다.

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

bool isContact(const string& str, int curIdx);

bool isContactFirst(const string& str, int curIdx)
{
	int idx = curIdx;

	if (idx + 3 >= str.size())
		return false;

	if (str[idx++] == '1' && str[idx++] == '0' && str[idx++] == '0')
	{

		while (idx < str.size() && str[idx] == '0')
		{
			idx++;
		}

		if (idx >= str.size())
			return false;

		while (idx < str.size() && str[idx] == '1')
		{
			idx++;

			if (idx >= str.size() || isContact(str, idx))
				return true;
		}
	}

	return false;
}

bool isContactSecond(const string& str, int curIdx)
{
	int idx = curIdx;

	if (idx + 1 >= str.size())
		return false;

	if (str[idx++] == '0' && str[idx++] == '1')
	{
		if (idx >= str.size())
			return true;
		else
			return isContact(str, idx);
	}

	return false;
}

bool isContact(const string& str, int curIdx)
{
	return isContactFirst(str, curIdx) || isContactSecond(str, curIdx);
}

int main(void)
{
	int T;
	cin >> T;

	while (T--)
	{
		string str;
		cin >> str;

		if (isContact(str, 0))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

[문제 링크]

2차원 DP 문제였지만 3차원 DP로 풀어서 코드가 복잡해졌다.

N번째 집의 경우 1번째 집의 색깔과 겹치면 안되기 때문에 이 조건을 처리하기 위해 1차원 더 추가해서 첫번째 집에 어떤 색깔을 칠했는지 캐싱했는데, 2차원 배열로 선언한 뒤 첫번째 집을 R, G, B 각각 칠했을 경우에 대해 각각 DP 로직을 수행해서 그중 가장 비용이 작은 값을 구해도 된다. 2차원 배열로 선언하는 방식이 캐싱하는데 필요한 메모리를 절약할 수 있다.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define INF 987654321
int memo[1000][3][3];

void bottomup(vector<vector<int>>& costs, int N)
{
    int R = 0;
    int G = 1;
    int B = 2;
    
    memo[0][R][R] = costs[0][R];
    memo[0][G][G] = costs[0][G];
    memo[0][B][B] = costs[0][B];
    
    for(int i=1; i<N; i++)
    {
        if(i + 1 == N)
        {
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];

            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
        }
        else 
        {
            memo[i][R][R] = min(memo[i-1][R][G], memo[i-1][R][B]) + costs[i][R];
            memo[i][R][G] = min(memo[i-1][R][R], memo[i-1][R][B]) + costs[i][G];
            memo[i][R][B] = min(memo[i-1][R][R], memo[i-1][R][G]) + costs[i][B];

            memo[i][G][R] = min(memo[i-1][G][G], memo[i-1][G][B]) + costs[i][R];
            memo[i][G][G] = min(memo[i-1][G][R], memo[i-1][G][B]) + costs[i][G];
            memo[i][G][B] = min(memo[i-1][G][R], memo[i-1][G][G]) + costs[i][B];
            
            memo[i][B][R] = min(memo[i-1][B][G], memo[i-1][B][B]) + costs[i][R];
            memo[i][B][G] = min(memo[i-1][B][R], memo[i-1][B][B]) + costs[i][G];
            memo[i][B][B] = min(memo[i-1][B][R], memo[i-1][B][G]) + costs[i][B];
        }
    }
    
    int result = INF;
    for(int first = R; first<=B; ++first)
    {
        for(int here = R; here<=B; ++here)
        {
            if(here==first) continue;
            result = min(result, memo[N-1][first][here]);
        }
    }
    
    cout << result;
}

int main(void)
{
    fill_n(memo[0][0], 1000*3*3, INF);
    
    int N;
    cin >> N;
    
    vector<vector<int>> costs(N, vector<int>(3));
    
    for(int i=0; i<N; ++i)
    {
        for(int j=0; j<3; ++j)
        {
            cin >> costs[i][j];
        }
    }
    
    bottomup(costs, N);
    
    return 0;
}

[문제 링크]

간단한 DP 문제였다.

자신의 차례에서 1개나 3개를 가져갔을 때 상대방이 승리하는지 여부는 가져간 개수에서 상대방이 1개나 3개를 가져갔을 때 자신이 승리하는지 여부에 결정된다. 그리고 이것을 계속 반복하다가 결국 기저사례 (N=1, N=2, N=3)에 도달하게 되면 최종적으로 승리와 패배가 결정되게 된다. 점화식은 다음과 같다.

Dp(N) = !(DP(N-1) || DP(N-3))

참고로 이 문제는 베스킨라빈스31 게임처럼 규칙 상 무조건 승리하는 필승법이 있다. 짝수개가 남도록 가져가면 결국 상대방이 패배한다. 즉 N이 홀수면 상근이가 이기고, 짝수면 창영이 이기게 된다.

#include <iostream>
using namespace std;

bool memo[1001] = {false,};
bool visited[1001] = {false,};

bool Topdown(int remain)
{
    if(remain == 1 || remain == 3)
    {
        return true;
    }   
    else if(remain == 2)
    {
        return false;
    }
    
    if(visited[remain]) 
    {
        return memo[remain];        
    }
    
    visited[remain] = true;
    
    return memo[remain] = !(Topdown(remain-1) || Topdown(remain-3));
}

bool Bottomup(int remain)
{
    memo[1] = true;
    memo[2] = false;
    memo[3] = true;
    
    for(int i = 4; i<=remain; ++i)
    {
        memo[i] = !(memo[i-1] || memo[i-3]);
    }
    
    return memo[remain];
}

int main(void)
{
    int N;
    cin >> N;
    
    if(Topdown(N))
    {
        cout << "SK";
    }   
    else 
    {
        cout << "CY";
    }
    
    return 0;
}

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

간단한 BFS 문제였다.

물높이가 0에서부터 지역 중 최고 높은 지역의 높이까지 경우에서 안전 영역의 개수를 계산하여 가장 많은 안전 영역의 개수를 출력해주면 된다.

안전 영역의 개수는 물높이보다 높은 지역을 시작으로 인접한 칸에 물높이보다 높은 지역이 있는지 탐색하는 BFS를 수행하면서 방문체크를 하고, 모든 좌표를 탐색했을 때 수행한 BFS 탐색의 수가 곧 안전 영역의 개수가 된다.

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

int getMaxSafeAreaCount(const vector<vector<int>>& cityArr, int RainHeight)
{
	int N = cityArr.size();
	vector<vector<bool>> visited(N, vector<bool>(N, false));

	int safeAreaCount = 0;

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

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			if (visited[y][x] || cityArr[y][x] <= RainHeight)
				continue;

			safeAreaCount++;

			queue<pair<int, int>> q;
			q.push({ y,x });
			visited[y][x] = true;

			while (!q.empty())
			{
				int hereY = q.front().first;
				int hereX = q.front().second;
				q.pop();

				for (int i = 0; i < 4; i++)
				{
					int nextY = hereY + dy[i];
					int nextX = hereX + dx[i];

					if (nextY >= 0 && nextY < N && nextX >= 0 && nextX < N)
					{
						if (!visited[nextY][nextX] && cityArr[nextY][nextX] > RainHeight)
						{
							q.push({ nextY, nextX });
							visited[nextY][nextX] = true;
						}
					}
				}

			}
		}

	return safeAreaCount;
}

int main(void)
{
	int N;
	cin >> N;

	vector<vector<int>> cityArr(N, vector<int>(N));

	int maxHeight = 0;

	for(int y=0; y<N; y++)
		for (int x = 0; x < N; x++)
		{
			cin >> cityArr[y][x];
			maxHeight = max(maxHeight, cityArr[y][x]);
		}

	int maxSafeAreaCount = 0;

	for (int i = 0; i < maxHeight; i++)
	{
		maxSafeAreaCount = max(maxSafeAreaCount, getMaxSafeAreaCount(cityArr, i));
	}

	cout << maxSafeAreaCount;

	return 0;
}

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

간단한 구현 문제였다.

최종 인원이 1명이 될 때 까지 라운드를 반복하다가

매치 트리에서 왼쪽에 있는 참가자 번호와 오른쪽에 있는 참가자 번호가 지민, 한수 번호와 일치한다면 해당 라운드 값을 출력해주면 된다.

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

int main(void)
{
	int jiminNum;
	int hansuNum;
	int maxNum;

	cin >> maxNum;
	cin >> jiminNum;
	cin >> hansuNum;

	int round = 0;
	bool isMatching = false;

	while (maxNum > 1 && !isMatching)
	{
		round++;

		int matchNum = 0;

		for (int i = 1; i <= maxNum; i += 2)
		{
			matchNum++;

			int leftNum = i;
			int rightNum = i + 1;

			if (leftNum == jiminNum || rightNum == jiminNum)
			{
				jiminNum = matchNum;

				if (rightNum == hansuNum || leftNum == hansuNum)
				{
					isMatching = true;
					break;
				}
			}
			else if (leftNum == hansuNum || rightNum == hansuNum)
			{
				hansuNum = matchNum;
			}
		}

		maxNum = matchNum * 2 < maxNum ? matchNum + 1 : matchNum;
	}

	if (isMatching)
		cout << round;
	else
		cout << -1;

	return 0;
}

[문제 링크]

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

문자열을 이용하는간단한 구현 문제였다.

등급에 따른 과목평점을 Map 컨테이너에 담아서 간단하게 매칭시켰다.

#include <iostream>
#include <string>
#include <map>
using namespace std;

void gradeMapping(map<string, float>& gradeScoreMap) {
	gradeScoreMap["A+"] = 4.5f;
	gradeScoreMap["A0"] = 4.0f;
	gradeScoreMap["B+"] = 3.5f;
	gradeScoreMap["B0"] = 3.0f;
	gradeScoreMap["C+"] = 2.5f;
	gradeScoreMap["C0"] = 2.0f;
	gradeScoreMap["D+"] = 1.5f;
	gradeScoreMap["D0"] = 1.0f;
	gradeScoreMap["F"] = 0.0f;
}

int main(void) {
	map<string, float> gradeScoreMap;
	gradeMapping(gradeScoreMap);

	float credit = 0;
	float totalCredit = 0;

	for (int i = 0; i < 20; i++) {
		string subjectStr, creditStr, gradeStr;
		cin >> subjectStr >> creditStr >> gradeStr;
		if (gradeStr == "P")
			continue;
		else {
			float nowCredit = stof(creditStr);
			float nowGrade = gradeScoreMap[gradeStr];
			credit += nowCredit;
			totalCredit += nowCredit * nowGrade;
		}
	}

	cout << totalCredit / credit << endl;

	return 0;
}

[문제 링크]

https://onlytrying.tistory.com/229    

예전에 풀었던 토마토 문제와 동일한 문제였다.

차이점은 상자의 상태가 3차원 배열이라는 점이다.

따라서, 기존의 구현 코드에서 상자를 3차원 배열로 변경하고 Z 좌표가 바뀌는 경우를 추가해주었다.

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

struct boxPos {
	int z, y, x;
};

int M, N, H;
int box[101][101][101];
queue<boxPos> ripeTomatoPosQ;
int dz[6] = { 0,0,0,0,1,-1 };
int dy[6] = { 0,0,1,-1,0,0 };
int dx[6] = { 1,-1,0,0,0,0 };

int getDay(int unripeTomato) {
	int day = 0;

	while (unripeTomato > 0) {
		day++;

		int newRipeTomatoCnt = ripeTomatoPosQ.size();
		// 안익은 토마토가 남아있는 상태에서 새롭게 익은 토마토가 없다면 토마토를 모두 익히는건 불가능하다.
		if (newRipeTomatoCnt == 0)
			return -1;

		for (int i = 0; i < newRipeTomatoCnt; i++) {
			int hereZ = ripeTomatoPosQ.front().z;
			int hereY = ripeTomatoPosQ.front().y;
			int hereX = ripeTomatoPosQ.front().x;
			ripeTomatoPosQ.pop();

			// 주변의 토마토를 익힌다.
			for (int i = 0; i < 6; i++) {
				int nearZ = hereZ + dz[i];
				int nearY = hereY + dy[i];
				int nearX = hereX + dx[i];

				if (nearZ >= 0 && nearZ < H && nearY >= 0 && nearY < N && nearX >= 0 && nearX < M)
					if (box[nearZ][nearY][nearX] == 0) {
						// 안익은 토마토를 익은 토마토로 바꾸고 안익은 토마토의 갯수를 1 감소시킨다.
						box[nearZ][nearY][nearX] = 1;
						unripeTomato--;

						// 새롭게 익은 토마토의 좌표를 큐에 담는다.
						ripeTomatoPosQ.push({ nearZ, nearY, nearX });
					}
			}
		}
	}

	return day;
}

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

	cin >> M >> N >> H;

	int unripeTomato = 0;
	for (int z = 0; z < H; z++) {
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < M; x++) {
				int state;
				cin >> state;
				box[z][y][x] = state;
				if (state == 0)
					unripeTomato++;
				else if (state == 1)
					ripeTomatoPosQ.push({ z,y,x });
			}
		}
	}

	cout << getDay(unripeTomato) << endl;

	return 0;
}