언제나 처음처럼

[문제 링크]

알고리즘은 다음과 같다.

먼저, tri[Y][X] 좌표에서 시작했을 때 최대값을 memo[Y][X]배열에 메모라이징하는 함수를 수행한다.

그 다음 최대 경로의 개수를 카운팅하는 함수를 수행한다. memo[Y][X]에는 좌표가 가지는 최대값이 저장되므로 memo[0][0]을 시작으로 갈 수 있는 좌표인 memo[Y+1][X] 와 memo[Y+1][X+1] 을 비교하여

값이 같을 경우 두 개의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수의 합을 cntmemo[Y][X]에 저장하고,

값이 다를 경우 더 큰 쪽의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수를  cntmemo[Y][X]에 저장한다.

기저사례로 Y == n-1 일 때, 즉 맨 아래에 도달했을 때 1을 리턴하여 최대 경로 개수를 카운팅해주면 원하는 결과를 얻을 수 있다.

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

int n, tri[101][101], memo[101][101], cntmemo[101][101];

inline int max(const int a, const int b) { return a > b ? a : b; }

int Solution(int startY, int startX)
{
	if (startY == n) return 0;

	int& ret = memo[startY][startX];
	if (ret != -1) return ret;
	
	int val = tri[startY][startX];
	return ret = max(val + Solution(startY + 1, startX), val + Solution(startY + 1, startX + 1));
}

int CountPath(int startY, int startX)
{
	if (startY == n-1) return 1;

	int& ret = cntmemo[startY][startX];
	if (ret != -1) return ret;

	ret = 0;
	if (memo[startY + 1][startX] > memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX);
	else if (memo[startY + 1][startX] < memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX + 1);
	else
		return ret += CountPath(startY + 1, startX) + CountPath(startY + 1, startX + 1);
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		memset(cntmemo, -1, sizeof(cntmemo));
		cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < i + 1; j++)
				cin >> tri[i][j];

		Solution(0,0);
		cout << CountPath(0, 0) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 55 day

[문제 링크]

비교 연산자가 많고 복잡해서 잔실수들을 고치느라 시간이 오래걸린 문제였다.

세 자리에서 다섯 자리까지로 끊어서 읽기 때문에 나올 수 있는 경우의 수는 한정되어 있다.

세 자리부터 다섯 자리까지 끊어서 읽을 수 있는 모든 경우의 수에 대하여 나올 수 있는 난이도의 합이 최소가 되는 값을 찾아주면 된다.

마지막에 남는 자리수가 2개 이하라면 잘못 끊어서 읽은 것이기 때문에 불가능(INF)값을 리턴한다.

추가로 PI[start]가 가질 수 있는 최소 난이도는 항상 같으므로 메모이제이션을 적용하면 제한시간 안에 문제를 풀 수 있다.

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

const int INF = 987654321;
int memo[10001], digit;
string PI;

inline int min(const int a, const int b) { return a < b ? a : b; }

int Solution(int start)
{
	if (start == digit) return 0;

	int& ret = memo[start];
	if (ret != -1) return ret;

	ret = INF;

	if (start + 2 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';

		if (a == b && b == c)
			ret = min(ret, Solution(start + 3) + 1);

		else if ( (b == a + 1 && c == b + 1) || 
				  (b == a - 1 && c == b - 1) )
			ret = min(ret, Solution(start + 3) + 2);

		else if (a == c && a != b)
			ret = min(ret, Solution(start + 3) + 4);

		else if (a - b == b - c)
			ret = min(ret, Solution(start + 3) + 5);

		else
			ret = min(ret, Solution(start + 3) + 10);
	}

	if (start + 3 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';

		if (a == b && b == c && c == d)
			ret = min(ret, Solution(start + 4) + 1);

		else if ( (b == a + 1 && c == b + 1 && d == c + 1) || 
				  (b == a - 1 && c == b - 1 && d == c - 1) )
			ret = min(ret, Solution(start + 4) + 2);

		else if (a == c && b == d)
			ret = min(ret, Solution(start + 4) + 4);

		else if (a - b == b - c && b - c == c - d)
			ret = min(ret, Solution(start + 4) + 5);

		else
			ret = min(ret, Solution(start + 4) + 10);
	}

	if (start + 4 < digit)
	{
		int a = PI[start] - '0';
		int b = PI[start + 1] - '0';
		int c = PI[start + 2] - '0';
		int d = PI[start + 3] - '0';
		int e = PI[start + 4] - '0';

		if (a == b && b == c && c == d && d == e)
			ret = min(ret, Solution(start + 5) + 1);

		else if ((b == a + 1 && c == b + 1 && d == c + 1 && e == d + 1) || 
				 (b == a - 1 && c == b - 1 && d == c - 1 && e == d - 1))
			ret = min(ret, Solution(start + 5) + 2);

		else if (a == c && a == e && b == d)
			ret = min(ret, Solution(start + 5) + 4);

		else if (a - b == b - c && b - c == c - d && c - d == d - e)
			ret = min(ret, Solution(start + 5) + 5);

		else
			ret = min(ret, Solution(start + 5) + 10);
	}

	return ret;
}
int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> PI;
		digit = PI.size();

		cout << Solution(0) << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 53 day

[문제 링크]

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

핵심은 두 개의 배열 A, B에서 현재 숫자보다 더 큰 수를 고르는 경우를 모두 해보면서 startA, startB를 초기값으로 시작할 때 가질 수 있는 최대 길이는 일정하기 때문에 이를 메모라이징하여 중복 탐색을 최소화 하는 것이라 생각한다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <limits>
using namespace std;

int n, m, A[101], B[101], memo[101][101];
const long long MIN = numeric_limits<long long>::min();

int Solution(int startA, int startB)
{
	int& ret = memo[startA + 1][startB + 1];
	if (ret != -1) return ret;

	ret = 2;
	long long a = (startA == -1 ? MIN : A[startA]);
	long long b = (startB == -1 ? MIN : B[startB]);
	long long maxValue = max(a, b);

	for (int i = startA + 1; i < n; i++)
		if (maxValue < A[i])
			ret = max(ret, Solution(i, startB) + 1);
	for (int i = startB + 1; i < m; i++)
		if (maxValue < B[i])
			ret = max(ret, Solution(startA, i) + 1);

	return ret;
}
int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n >> m;
		for (int i = 0; i < n; i++)
			cin >> A[i];
		for (int i = 0; i < m; i++)
			cin >> B[i];

		cout << Solution(-1, -1) - 2 << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 52 day

[문제 링크]

알고리즘 문제해결전략  책에 나와있는 알고리즘과 동일하게 구현하였다.

핵심은 아래에서 위로 탐색하면서 최대가 되는 값을 선택하는 것이라고 생각한다.

(y,x) 위치에서 아래칸을 선택할 수 있는 경우는 (y+1, x), (y+1, x+1) 두 가지 경우밖에 존재하지 않기 때문에 두 가지 경우 중 가질 수 있는 최대값이 더 큰 쪽을 선택해야 한다.

아래칸이 가질 수 있는 최대값을 알아야 하기 때문에, 맨 아래에서 위로 탐색하는 것이다.

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

int n, triangle[101][101], memo[101][101];

inline int max(const int a, const int b) { return a > b ? a : b; }

int Solution(int y, int x)
{
	if (y == n - 1) return triangle[y][x];

	int& ret = memo[y][x];
	if (ret != -1) return ret;

	return ret = max(Solution(y + 1, x), Solution(y + 1, x + 1)) + triangle[y][x];
}

int main(void)
{
	int testcase;
	cin >> testcase;
	while (testcase--)
	{
		memset(memo, -1, sizeof(memo));
		cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j <= i; j++)
				cin >> triangle[i][j];

		cout << Solution(0, 0) << endl;
	}
}

알고리즘 200일 프로젝트 - 51 day

[문제 링크]

알고리즘 문제해결전략 책에 나와있는 알고리즘과 동일하게 구현하였다.

문제에 결과를 ASCII코드 순서로 출력하라는 조건이 있기 때문에 vector 배열에 조건을 만족하는 파일명을 저장한 다음, 오름차순 정렬 후 출력해주었다.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int memo[101][101];
string wild, file;

bool Solution(int w, int f)
{
	int& ret = memo[w][f];

	if (ret != -1) return ret;

	while (w < wild.size() && f < file.size() && (wild[w] == '?' || wild[w] == file[f]))
	{
		w++, f++;
	}
	if (w == wild.size() && f == file.size())
		return ret = 1;

	if (wild[w] == '*')
		if (Solution(w + 1, f) || (f < file.size() && Solution(w, f + 1)))
			return ret = 1;

	return ret = 0;
}
int main(void)
{
	int testcase;
	cin >> testcase;

	while (testcase--)
	{
		int num;
		cin >> wild >> num;

		vector<string> result;
		for (int i = 0; i < num; i++)
		{
			cin >> file;
			memset(memo, -1, sizeof(memo));

			if(Solution(0, 0))
				result.push_back(file);
		}
		sort(result.begin(), result.end());

		for (int i = 0; i < result.size(); i++)
			cout << result[i] << endl;
		
		result.clear();
	}
	return 0;
}

알고리즘 200일 프로젝트 - 50 day

[문제 링크]

책보고 정석으로 공부하면서 스스로 풀게된 첫번째 동적계획법 유형의 문제이다.

Solution(y, x)는 입력이 같을 경우 항상 같은 값을 반환하는 참조적 투명 함수이기 때문에, 메모이제이션 기법을 적용할 수 있다.

최대 크기가 100X100인 2차원 배열 memo[100][100] 를 선언하고 -1로 초기화하여, memo[y][x]가 -1이라면 처음 방문하는 지점이므로 성공 여부를 탐색하고, 성공 여부를 저장한다. -1이 아니라면 이미 탐색했던 지점이므로 memo[y][x]값을 바로 리턴해준다.

기저사례로 배열의 범위를 벗어날 경우 false, 현재 좌표가 (N-1, N-1) 이라면 끝에 도달한 것이므로 true를 반환해주도록 구현하였다.

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

int N, board[100][100], memo[100][100];

bool Solution(int startY,int startX)
{
	if (startY >= N || startX >= N) return false; // 기저사례. 범위 벗어나면 false

	if (startY == N - 1 && startX == N - 1) return true; // 기저사례. 끝에 도달했다면 true

	int& ret = memo[startY][startX];

	if (ret != -1) return ret; // 메모이제이션. 이미 해당 좌표에 대해 경로탐색을 해봤다면 저장한 성공여부 반환

	return ret = Solution(startY + board[startY][startX], startX) || Solution(startY, startX + board[startY][startX]);
}

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

	while (testcase--)
	{
		cin >> N;
		memset(memo, -1, sizeof(board));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				cin >> board[i][j];

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

	return 0;
}

알고리즘 200일 프로젝트 - 48 day

[문제 링크]

분할정복은 문제를 부분 문제로 뚝 자르고 잘라져서 나온 조각에 대해 똑같이 처음 했던 것처럼 뚝 자르기를 반복하여 정답을 찾아내는 방식인거같다.

다만 완전탐색과 조금 다른점이 있다면 문제마다 구현해야할 기저사례, 점화식을 깊게 생각해봐야하고, 이를 구현하는 것이 까다롭다는 것이다. 대강 원리는 이해했으니 문제를 많이 풀어보면서 문제 유형에 익숙해지고 구현력을 키워야겠다.

알고리즘 200일 프로젝트 - 35day

[문제 링크]

분할정복 알고리즘 부분은 교재에 나와있는 소스코드와 동일하다.

다만 책에서 설명이 안되어있는데, 매개변수로 반복자를 참조하기 위해서는 비 const 반복자를 전달해야한다.

tree.begin() 이 반환하는 반복자는 const 반복자이므로 따로 비 const 반복자를 선언하고 tree.begin()으로 초기화해줘야 한다는 점만 주의하면 될 것 같다.

알고리즘 200일 프로젝트 - 34day