언제나 처음처럼

[문제 링크]

함정이 있는 이분 탐색 문제였다.

나무를 자르는 높이가 낮을수록 얻어가는 나무는 증가한다. 즉 나무를 자르는 높이(N)과 얻어가는 나무의 양은 반비례한다.

따라서, 어떤 높이(mid)를 기준으로 나무를 잘랐을 때 얻어가는 나무의 양이 필요한 양(M)보다 작다면 mid보다 높이 자르는 경우는 고려하지 않아도 되며, 이 사실을 바탕으로 이분 탐색을 사용하는 조건을 만족하게 된다.

알고리즘은 다음과 같다.

먼저 나무들의 높이를 vector에 입력받은 다음 오름차순으로 정렬하자.

그 다음 가장 낮은 높이(lower)를 0으로 하고, 가장 높은 높이(upper)를 벡터의 마지막 원소로 하여

(lower + upper) / 2 를 mid 로 이분 탐색을 시작한다.

vector의 모든 원소에 대하여 v[i] - mid가 0보다 클 경우 sum 변수에 값을 누적 시킨다.

만약 sum이  M보다 작을 경우 mid 높이보다 같거나 높은 경우는 버려도 무방하므로 upper 값을 mid - 1로 바꿔준다.

sum이 M보다 같거나 클 경우 조건을 만족하므로 result 변수에 mid를 저장하고, 최대 높이를 찾기 위해 lower 값을 mid + 1로 바꿔준다.

(ps. 여기서 함정이 있는데 적어도 M개를 가져가야 하므로, sum이 M보다 크거나 같은 경우에 result 변수를 갱신해야한다. 작거나 같은 경우에 result 변수를 갱신하게 되면 오답이 출력된다.)

끝으로, lower이 upper보다 커질 때가지 위 작업을 반복하게 되면 result 변수에는 적어도 M미터의 나무를 얻기 위한 최대의 높이가 저장된다.

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

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

	int N, M;
	cin >> N >> M;
	vector<int> tree(N);

	for (int i = 0; i < N; i++)
		cin >> tree[i];

	sort(tree.begin(), tree.end());
	
	int lower = 0, upper = tree[N-1], result;
	while (lower <= upper)
	{
		int mid = (lower + upper) / 2;
		long long sum = 0;
		for (int i = 0; i < N; i++)
		{
			if (tree[i] < mid) continue;
			sum += tree[i] - mid;
		}
		if (sum >= M)
		{
			result = mid;
			lower = mid + 1;
		}
		else
		{
			upper = mid - 1;
		}
	}
	cout << result << endl;
	return 0;
}

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

[문제 링크]

간단한 이분탐색 문제였다.

입력받은 숫자들을 vector에 저장하고, 정렬한 다음 binary_search() 함수를 통해 찾고자 하는 숫자의 존재 여부를 파악하고 반환되는 bool 값을 출력해주면 원하는 결과를 얻을 수 있다.

이 문제처럼 입출력이 많이 발생하는 문제를 풀 때는 ios_base::sync_with_stdio(0); 과 cin.tie(NULL); 을 꼭 추가해주는 것이 좋다.

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

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

	vector<long long> arr;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());
	
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		cout << binary_search(arr.begin(), arr.end(), num) << '\n';
	}

	return 0;
}

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

[문제 링크]

맞추고도 머리가 띵했던 문제였다. 왜냐하면 설마 이게 맞겠어? 하고 제출한 코드가 정답 처리를 받았기 때문이다.

알고리즘(?)은 다음과 같다

낮에 올라가는 높이 = A, 밤에 떨어지는 높이 = B, 총 올라가야 하는 높이 = V 라고 할 때,

정상에만 올라가면 떨어질 일이 없기 때문에 (V-A) 높이 이상으로만 올라간다면 올라가는데 걸린 DAY에 추가로 하루가 더 걸리게 된다.

따라서 최소로 올라가야할 높이 (V-A)를 먼저 구해주고, 구한 높이를 (A-B)로 나눈 몫과 나머지를 구한다.

이 때 구한 몫이 DAY가 되고, 나머지가 0이라면 최소 높이에 도달했으므로 DAY+1을 출력, 나머지가 0이 아니라면 최소 높이에 도달하지 못한 것이므로 하루가 더 걸리게 되어 DAY+2를 출력해주면 원하는 결과를 얻을 수 있다.

#include <iostream>
using namespace std;

int main(void)
{
	int A, B, V;
	cin >> A >> B >> V;

	int end = V - A, up = A - B;
	int day = end / up, check = end % up;
	if (check == 0) 
		cout << ++day << endl;
	else
	{
		day += 2;
		cout << day << endl;
	}
	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/50

10815번: 숫자 카드 문제의 업그레이드 버전 문제이다.

이 문제는 존재 유무뿐만이 아니라 존재하는 갯수까지 세야한다.

필자는 간단히 multiset으로 원소의 중복을 허용하고 count() 멤버함수를 사용하여 구현하려했으나 시간초과가 발생하였다.

연관 컨테이너(map,set 등)는 삽입, 삭제 연산 시 상당히 많은 작업이 필요할 수 있기 때문에 전부 다 입력받고 정렬하는 편이 훨씬 더 빠르다는 것을 간과하고 있었다.

따라서 vector에 정수를 저장한 다음 정렬한 후, 정렬된 범위에서 동작하는 알고리즘인 equal_range() 를 사용하여 upper_bound 반복자와 lower_bound 반복자의 차이가 원소의 갯수인 것을 이용해 문제를 해결하였다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		pair<vector<int>::iterator, vector<int>::iterator> range = equal_range(card.begin(), card.end(), num);
		if (range.first != range.second) cout << range.second - range.first << ' ';
		else cout << "0 ";
	}
	return 0;
}

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

[문제 링크]

간단한 이분탐색 문제였다. 입력받은 숫자들을 오름차순으로 정렬하고, 그 다음으로 입력받는 정수들을 이분 탐색을 통해 검색해 존재할 경우 1, 존재하지 않을 경우 0을 출력해주면 원하는 결과를 얻을 수 있다.

ps. 입력과 출력의 횟수가 크기때문에 ios_base::sync_with_stdio(0); 과 cin.tie(NULL); 을 추가해주는 것이 좋다.

(대부분의 시간초과는 입출력 부분에서 잡아먹는 시간때문에 발생한다.)

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

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	vector<int> card;
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.push_back(num);
	}
	sort(card.begin(), card.end());
	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		bool state = false;
		int start = 0, end = card.size()-1;
		while (start <= end)
		{
			int mid = (start + end) / 2;
			if (num < card[mid])
				end = mid-1;
			else if (num > card[mid])
				start = mid+1;
			else
			{
				cout << "1 ";
				state = true;
				break;
			}
		}
		if (!state) cout << "0 ";
	}

	return 0;
}

또한 c++의 set 컨테이너에 정수를 담고 set의 멤버함수인 find() 를 사용하면 매우 간단하게 구현할 수 있다.

#include <iostream>
#include <set>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	set<int> card;
	int N; 
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int num;
		cin >> num;
		card.insert(num);
	}
	int M; 
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int num;
		cin >> num;
		if (card.find(num) != card.end()) cout << "1 ";
		else cout << "0 ";
	}
	return 0;
}

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

[문제 링크]

c++ stl 컨테이너인 map을 사용하면 쉽게 풀 수 있는 문제라 생각한다.

map 컨테이너는 [ ] 로  key값을 이용해 간단하게 value값을 찾을 수 있으며, O(logN) 시간복잡도를 보장한다.

필자는 key값이 string인 map과 int인 map을 두개 만들어서 입력되는 문제가 string일 경우와 int일 경우 if문을 통해 각각 다른 map컨테이너를 검색하도록 구현하였다.

참고로 시간초과로 고생 하시는 분들께서는 ios_bass::sync_with_stdio(0); cin.tie(NULL); 을 추가하고 cout과 cin을 사용해보는 것을 추천합니다.

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

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

	map<string, int> poketStr;
	map<int, string> poketNum;
	int N, M, num=1;
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		poketStr.insert(make_pair(str, num));
		poketNum.insert(make_pair(num++, str));
	}

	for (int i = 0; i < M; i++)
	{
		char question[21];
		cin >> question;
		if (question[0] < 'A')
		{
			int qNum = atoi(question);
			cout << poketNum[qNum] << '\n';
		}
		else
		{
			cout << poketStr[question] << '\n';
		}
	}
	return 0;
}

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

[문제 링크]

분할정복과 이분탐색이 섞인 문제인거같다. 이분탐색 풀이법이 생각나지 않아 다른사람들의 풀이법을 참고하였다. 3일 후에 다시한번 풀어봐야 겠다.

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

vector<int> dayMoney;
int N, M, sum;

bool Solution(int money)
{
	int temp = money, withdraw = 1;
	for (int i = 0; i < N; i++)
	{
		if (dayMoney[i] > money)
			return false;
		if (temp - dayMoney[i] < 0)
		{
			temp = money;
			withdraw++;
		}
		temp -= dayMoney[i];
	}
	return M >= withdraw;
}
int main(void)
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		dayMoney.push_back(n);
		sum += n;
	}

	// binary_search //
	int start = 1, end = sum; // sum은 M이 1인 모든 금액을 더한 값
	int result;
	while (start <= end)
	{
		int mid = (start + end) / 2;
		if (Solution(mid))	// 인출횟수가 M보다 작거나 같음 -> 인출금을 줄여보자
		{
			result = mid;
			end = mid -1;
		}
		else
			start = mid + 1;
	}
	cout << result << endl;
	return 0;
}

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

[문제 링크]

https://onlytrying.tistory.com/46

쿼드트리 문제와 동일하다. 다른점은 보드 크기가 3^N X 3^N 인 것과 보드를 쪼갤 때 4조각이 아닌 9조각으로 쪼갠다는 것이다.

쿼드트리 문제와 마찬가지로 (startY, startX)좌표를 시작으로 3^N X 3^N 크기 만큼의 보드를 검사한다.

숫자가 모두 같다면 더이상 쪼개질 수 없으므로 보드의 숫자를 카운팅 해준다.

필자는 0으로 초기화한 크기가 3인 배열을 하나 만들고 Array[보드의 숫자 + 1]++ 으로 숫자를 카운팅하였다.

#include <iostream>
using namespace std;

int board[2188][2188];
int numberCnt[3]; // MINUS ONE = 0, ZERO = 1, ONE = 2

void Solution(int N, int startY, int startX)
{
	if (N == 1) // 없어도 무방한 기저사례지만 코드 직관성과 효율성을 위해 추가
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	bool check = true;
	for (int i = startY; i < startY + N; i++)
	{
		for (int j = startX; j < startX + N; j++)
		{
			if (board[startY][startX] != board[i][j])
			{
				check = false;
				break;
			}
		}
		if (!check) break;
	}
	if (check)
	{
		++numberCnt[board[startY][startX] + 1];
		return;
	}

	int nextN = N / 3;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			Solution(nextN, startY + (nextN*i), startX + (nextN*j));
}
int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> board[i][j];

	Solution(N, 0, 0);

	for (int i = 0; i < 3; i++)
		cout << numberCnt[i] << endl;
	
	return 0;
}

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