언제나 처음처럼

[문제 링크]

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

간단한 백트래킹 문제였다.

기저사례는 시작 인덱스가 수열의 끝에 도달하는 경우로 설정하였고,

기저사례에 도달할 경우 현재까지 계산된 값으로 최소값과 최대값을 갱신하도록 구현하였다.

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

int minVal = 1987654321;
int maxVal = -1987654321;

enum class Operator
{
	Plus,
	Minus,
	Multiple,
	Division
};

void backtracking(vector<int>& arr, vector<int>& operatorArr, int start, int value)
{
	if (start == arr.size())
	{
		minVal = min(minVal, value);
		maxVal = max(maxVal, value);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (operatorArr[i] == 0) continue;
		
		int nextValue = value;

		switch (i)
		{
		case (int)Operator::Plus:
			nextValue += arr[start];
			break;

		case (int)Operator::Minus:
			nextValue -= arr[start];
			break;

		case (int)Operator::Multiple:
			nextValue *= arr[start];
			break;
			
		case (int)Operator::Division:
			nextValue /= arr[start];
			break;
		}

		operatorArr[i]--;
		backtracking(arr, operatorArr, start + 1, nextValue);
		operatorArr[i]++;
	}
}

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

	vector<int> arr(N);

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

	vector<int> operatorArr(4, 0);
	cin >> operatorArr[0] >> operatorArr[1] >> operatorArr[2] >> operatorArr[3];

	backtracking(arr, operatorArr, 1, arr[0]);

	cout << maxVal << '\n' << minVal;

	return 0;
}

[문제 링크]

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

간단한 백트래킹 문제였다.

이전에 담은 숫자를 중복으로 담지 않기 위해 vector<bool>에 담은 숫자를 마킹하는 방식을 사용하였다.

기저사례는 vector<int> 크기가 M과 같아지는 경우로 설정하였고,

기저사례에 도달할 경우 재귀를 수행하지 않고 vector에 담긴 원소를 출력하는 방식으로 구현하였다.

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

int N, M;

void backtracking(vector<int>& backpack, vector<bool>& picked)
{
	if (backpack.size() == M)
	{
		for (auto a : backpack)
		{
			cout << a << ' ';
		}
		cout << '\n';

		return;
	}
	
	for (int i = 1; i <= N; i++)
	{
		if (picked[i]) continue;

		backpack.push_back(i);
		picked[i] = true;
		backtracking(backpack, picked);
		backpack.pop_back();
		picked[i] = false;
	}
}

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

	vector<int> backpack;
	vector<bool> picked(N+1, false);
	backtracking(backpack, picked);

	return 0;
}

[문제 링크]

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 를 호출해 이어지는 패턴인지 검사

종료 조건과 결과

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

시간 복잡도

• 문자열 길이가 최대 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;
}