언제나 처음처럼

[문제 링크]

알고리즘은 다음과 같다.

먼저, 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

[문제 링크]

https://jaimemin.tistory.com/988 꾸준함 님의 블로그를 참고해서 겨우 이해한 문제였다. 아직도 조금 헷갈리긴 한다.

arr[i][j] 에 해당하는 숫자는 i * j 이므로, i행은 i의 배수로 이루어져 있다. (ex. i * 1, i * 2, i * 3 .... i * N)

이를 바탕으로 어떤 임의의 숫자 M을 i가 1부터 N까지인 경우에 대해 M / i 한 몫을 cnt 변수에 누적시키면 M은 cnt+1 번째 수라는 사실을 알 수 있다.

이 때 주의해야 할 것이 만약 M / i 한 몫이 N보다 클 경우 배열의 최대 범위보다 큰 값을 누적하게 되므로 오답이 출력되기 때문에 M / i 한 몫을 누적하는 것이 아닌 배열의 최대 길이인 N을 누적시킨다.

전부 누적시켰다면 입력받은 K와 비교를 하여 만약 cnt가 K보다 작을 경우 더 큰 mid값을 탐색하기 위해 start = mid + 1 로 바꿔준다.

반대로 cnt가 K보다 크거나 같을 경우 result에 mid 값을 저장하고, 최적의 해를 찾기 위해 end = mid - 1 로 바꿔서 재탐색한다.

start가 end보다 커질 때까지 위 과정을 반복하면 result에는 N X N 배열에서 K번째 수에 해당하는 정수가 저장되게 된다.

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

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

	int start = 1, end = K, result;
	while (start <= end)
	{
		int mid = (start + end) / 2, cnt = 0;
		for (int i = 1; i <= N; i++)
			cnt += min(mid / i, N);
		if (cnt >= K)
		{
			result = mid;
			end = mid - 1;
		}
		else
			start = mid + 1;
	}
	cout << result;

	return 0;
}

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

[문제 링크]

이분 탐색의 조건을 어떻게 만족하는지 이해하느라 고생했던 문제였다.

가장 인접한 두 공유기 사이의 거리가 멀어질수록 설치하는 공유기의 개수는 작아진다. 즉, 반비례한다.

알고리즘은 다음과 같다.

집의 좌표를 vector에 입력받고, 오름차순 정렬한다.

start를 1로, 가장 작은 좌표와 가장 큰 좌표 사이의 거리를 end로 정하고 이분 탐색을 시작한다.

가장 인접한 두 공유기 사이의 거리가 최소 mid 이상이라고 했을 때, 설치할 수 있는 공유기의 개수가 만약 설치하고자 하는 개수(C)보다 많거나 같다면  조건을 만족하는 것이기 때문에 이 때의 가장 인접한 두 공유기 사이의 거리 (mid로 갱신하는 것이 아님!!) 을 결과값으로 갱신하고, 더 멀리했을때도 조건을 만족하는지 알아보기 위해 start를 mid+1로 바꿔준다.

(더 많이 설치된 경우도 조건을 만족하는 이유는 공유기를 갯수에 맞게 제거해도 가장 인접한 거리는 변함이 없기 때문)

반대로 설치하고자 하는 개수(C)보다 적다면 조건을 만족하지 않기 때문에 mid 이상의 거리는 무조건 조건을 만족하지 않는다는 사실을 알 수 있다. 따라서 결과값을 갱신하지 않고, mid를 줄이기 위해 end를 mid-1로 바꿔준다.

start가 end보다 커질 때까지 위 작업을 반복하게 되면 결과값에는 가장 인접한 두 공유기 사이의 거리가 최대인 경우가 저장된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
const int MAX = 987654321;

int main(void)
{
	int N, C;
	cin >> N >> C;
	
	vector<int> router(N);
	for (int i = 0; i < N; i++)
		cin >> router[i];
	
	sort(router.begin(), router.end());

	int start = 1, end = router[N - 1] - router[0], result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		int here = 0, cnt = 1, minDist = MAX;
		for (int i = 1; i < N; i++)
		{
			int dist = router[i] - router[here];
			if (dist < mid) continue;
			minDist = min(minDist, dist);
			here = i;
			cnt++;
		}

		if (cnt >= C)
		{
			result = minDist;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}

	cout << result << endl;

	return 0;
}

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