언제나 처음처럼

[문제 링크]

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

핵심은 두 개의 배열 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

[문제 링크]

https://onlytrying.tistory.com/55

1654번: 랜선 자르기, 2805번: 나무 자르기 유형의 문제와 같은 알고리즘을 사용한다.

분배하는 예산이 커질 수록 총 필요한 예산도 커진다. 즉, 분배하는 예산과 총 필요한 예산은 서로 비례한다.

금액 N으로 예산을 분배했을 때 만약 총 필요한 예산이 입력받은 국가 예산보다 크다면 N 이상의 금액을 고려하지 않아도 되기 때문에 이분 탐색을 진행할 수 있다.

먼저, 지방 예산을 vector 배열에 저장하면서, 변수 sum에 누적한다.

만약 입력받은 국가 예산이 sum보다 크다면 정답은 가장 큰 지방 예산이 되기 때문에 탐색을 하지 않아도 된다.

이 경우가 아니라면 start를 1, end를 가장 큰 지방 예산으로 이분 탐색을 진행하여 가능한 최대 예산을 구해주면 된다.

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

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> money(N);
	int total = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> money[i];
		total += money[i];
	}

	sort(money.begin(), money.end());

	int maxMoney;
	cin >> maxMoney;

	if (total <= maxMoney)
		cout << money[N - 1];
	else
	{
		int start = 1, end = money[N - 1], result;
		
		while (start <= end)
		{
			int mid = (start + end) / 2, sum = 0;
			for (int i = 0; i < N; i++)
			{
				if (money[i] <= mid)
					sum += money[i];
				else
					sum += mid;
			}
			
			if (sum <= maxMoney)
			{
				result = mid;
				start = mid + 1;
			}
			else
				end = mid - 1;
		}

		cout << result << endl;
	}

	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/54

나무 자르기 문제와 비슷한 유형의 문제였다.

랜선을 자르는 길이가 길어질수록 만들어지는 랜선의 갯수는 무조건 작아지기 때문에 자르는 길이와 만들어지는 랜선의 갯수는 서로 반비례한다는 것을 알 수 있다.

알고리즘은 나무 자르기 문제와 동일하다.

차이점으로는 0cm 길이의 랜선을 가져갈 수는 없기 때문에 start의 초기값을 0이 아닌 1로 해야 하고, 입력되는 정수의 최댓값이 크므로 unsigned int나 long long 자료형을 사용해야 한다.

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

int main(void)
{
	int K, N;
	cin >> K >> N;
	
	vector<int> utp(K);
	for (int i = 0; i < K; i++)
		cin >> utp[i];
	
	sort(utp.begin(), utp.end());
	
	long long start = 1, end = utp[K - 1];
	int result;

	while (start <= end)
	{
		long long mid = (start + end) / 2;
		int sum = 0;

		for (int i = 0; i < K; i++)
			sum += utp[i] / mid;

		if (sum >= N)
		{
			result = mid;
			start = mid + 1;
		}
		else
			end = mid - 1;
	}
	cout << result << endl;
	
	return 0;
}

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