#include <iostream>
#include <algorithm>

using namespace std;
int arr[100'002];

int BinarySearch(const int * arr, const int & size, const int & f)
{
	int s = 0, e = size - 1, m;

	while (s <= e)
	{
		m = (s + e) / 2;

		if (arr[m] == f) return 1;
		if (arr[m] < f) s = m + 1;
		else e = m - 1;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << BinarySearch(arr, N, F) << "\n";
	}

	return 0;
}

||사고 과정

단순 이분탐색을 사용하는 문제,

직접 구현하여 풀이했다.

||사용 기법

• Binary Search

||더 간단한 풀이

#include <iostream>

using namespace std;
int arr[100'002];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		arr[temp] = 1;
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << (arr[F] == 1 ? 1 : 0) << "\n";
	}

	return 0;
}

이런식으로 정렬 없이 할 수 있을것 같아서 생각해봤지만 들어오는 수의 범위가 int형이므로

int형의 범위만큼 배열을 정의할 수 없기에 비슷한 동작인 Set을 사용해볼것이고

그 중 항상 100% 안정성이 있지는 않지만 빠른 unordered_set을 사용해보았다.

#include <iostream>
#include <unordered_set>

using namespace std;
unordered_set<int> S;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	
	int N; cin >> N;
	int temp;
	for (int i = 0; i < N; ++i)
	{
		cin >> temp;
		S.insert(temp);
	}

	int M,F; cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> F;
		cout << ((S.find(F) == S.end()) ? 0 : 1) << "\n";
	}

	return 0;
}

여기서 놀라웠던건 시간인데

상수시간을 가지는 u_set보다 n log n의이분탐색이 더 빠르게 나왔다.

O(1)과 O(log N)에서 시간복잡도에 붙은 상수로 자주 뒤집어질수있다고 한다.

항상 상수를 떼고 계산하다보니까 그럴수도 있다는 생각을 하지 못했다.

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001][4] = {0,};
int arr[10'001] = {0,};

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

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

	//2. Set initial value
	dp[1][1] = dp[1][0] = 0;
	dp[1][2] = dp[1][3] = arr[1];

	for (int i = 2; i <= n; ++i)
	{
		dp[i][0] = max(dp[i - 1][2], dp[i - 1][3]);
		dp[i][1] = dp[i - 1][0];
		dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i];
		dp[i][3] = dp[i - 1][2] + arr[i];
	}

	//3. Print
	cout << max(max(dp[n][0], dp[n][1]), max(dp[n][2], dp[n][3]));
	return 0;
}

||사고 과정

비슷한 문제를 좀 풀어서 풀이방법은 어렵지 않게 생각 할 수 있었다.

다만 나는 이차원 테이블을 사용하여 좀 어렵게 풀었다.

이번에도 그냥 감으로 이차원 테이블로 사용했던것 같다.

그래서 dp[ i ][ j ]에서 [ j ]의 경우를 찾으려고 하니까 처음에는 3개가 나왔다.

1번 쉬는 경우, 1번째로 마시는 경우, 2번째로 마시는 경우

사실 2번 쉬는 경우가 포함되어야 하지만 나는 최대로 마실거니까 1번만 쉬어도 되지 않을까 라는 생각을 했다.ㅠ

그래서 처음에 틀렸다가 예외를 찾고 추가하여 정답을 맞췄다.

||사용 기법

• DP

||풀면서 느낀 것

• 테이블을 이차원으로 사용하는 것을 잘 생각해서 설정해야겠다.

요새 이차원으로 DP를 풀다보니 이것도 당연히 이차원일꺼라는 안일한 생각이 있었다ㅠㅠ

감으로 풀지말고 확실한 논리로 테이블을 세팅하자ㅠ

• 이런 문제는 뭔가 어차피 안해도 돼~ 라는 예외가 있는것 같다.

어떠한 경우는 생각해야하지 않을까? 하면 어차피 안해도 되는 예외같은게 많았다.

나는 이 문제에서 i번째 포도주를 안마시고 dp[i - 2]가 최대값일 수도 있지 않나? 라는 생각이 있었는데

필요 없는 예외였다.

다음에는 예외를 좀 더 논리적으로 제거해가야겠다.

||나아 진것

• 예외 생각

다른 사람것을 보지 않고 잘 생각했음

||더 나은 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int dp[10'001] = { 0, };
int arr[10'001] = { 0, };

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);

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

	//2. Set initial value
	dp[1] = arr[1];
	dp[2] = arr[2] + arr[1];

	for (int i = 3; i <= n; ++i)
	{
		dp[i] = max(dp[i - 3] + arr[i - 1], dp[i - 2]) + arr[i];
		dp[i] = max(dp[i - 1], dp[i]);
	}

	//3. Print
	cout << dp[n];
	return 0;
}

일차원 테이블로 풀이하는 방법이다.

dp[ i ]는 i번째 포도주에 왔을 때 최대로 마실 수 있는 양을 지닌다.

그 양의 경우의 수는 세가지인데

1) i번째를 두번째로 마시는 경우,

이는 i - 3의 최대 값과 arr[ i - 1 ]을 더해주면 arr[ i ]가 알아서 두번째로 마시는게 된다.

2)i번째를 첫번째로 마시는 경우,

이는 i - 1을 안마신경우이므로 dp[ i - 2 ]에서 현재 arr [ i ]을 더해주면 된다.

3)i번째를 안마시는 경우,

당연히 dp[i - 1] 이다.

dp[i - 2]라는 선택지도 있을것같지만 잘 생각해보면 dp[i - 2] <= dp[i - 1] 가 될 수 밖에 없다.

#include <iostream>
#include <algorithm>

#define MAX 100001
using namespace std;

int dp[MAX][3];
int arr[2][MAX];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int T; cin >> T;

	while (T--)
	{
		//1. Get input value
		int N; cin >> N;
		for (int i = 0; i < 2; ++i)
		{
			for (int j = 1; j <= N; ++j)
			{
				cin >> arr[i][j];
			}
		}
		
		//2. Set initial value
		dp[1][0] = arr[0][1];
		dp[1][1] = arr[1][1];
		dp[1][2] = 0;

		//3. Do fill DP table
		for (int i = 2; i <= N; ++i)
		{
			dp[i][0] = max(dp[i - 1][2], dp[i - 1][1]) + arr[0][i];
			dp[i][1] = max(dp[i - 1][2], dp[i - 1][0]) + arr[1][i];
			dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]);
		}

		//4. Print
		cout << max(dp[N][0], max(dp[N][1], dp[N][2])) << "\n";
	}
	return 0;
}

||사고 과정

생각하는데 한 40분정도 소모했던 문제였다.

처음에 뭔가 직감적으로 일차원 테이브로는  풀지못하여 이차원 테이블인것 같았지만

인덱스마다 의미하는 것을 찾는게 어려웠다.

DP[ i ] [ j ] 에서 i는 분명 데이터의 개수를 뜻하는 것이니 j의 의미를 찾고 있던 와중에

데이터에서 나올 수 있는 경우의 수를 좀 더 집중적으로 생각했다.

상하좌우로 인접한 스티커는 땔수 없으니

하나의 열(i)에서 위의 스티커를 떼는 경우, 아래의 스티커를 떼는 경우, 떼지 않는 경우를 생각했다.

이 떼지 않는 경우를 생각하기가 어려웠는데 처음 본다고 생각하면

많은 스티커를 떼는게 목표지만 떼지 않는 경우를 구한다 라는게 와닿지 않았던것 때문이였던것 같다.

아무튼 이렇게 세가지를 j에 대응시켜서 손코딩으로 값을 찾아가니 점화식도 나오고 풀게 되었던 문제다.

||사용 기법

• DP

||풀면서 느낀 것

• 이차원 배열 테이블의 느낌

DP[i][j]라면 i는 데이터의 개수이고, j는 데이터에서 나올 수 있는 경우의수 를 뜻하는게 많았던것 같다.

• 넓게 생각하자

처음에는 무조건 많이 떼는게 최대가 나온다고 생각했지만 아니였다.

테스트 케이스가 아니였다면 생각하지 못했을거다.

어떻게 보면 예외처리를 잘하자라는 말ㅋㅋㅠ

• 테이블의 의미를 찾는게 이번에는 도움이 되었다.

경험상 의미를 찾으면 점화식도 금방 나오는것 같기에

다음에는 좀 더 집중해서 찾아봐야겠다.

#include <iostream>
#define MOD 10007
#define ALL 10
using namespace std;
//일차원의 10번째 인덱스는 총합을 의미한다.
long long dp[1001][11] = { 0, };

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 0; i < 10; ++i)
	{
		dp[1][i] = 1;
		dp[1][ALL] += dp[1][i];
	}
	
	for (int i = 2; i <= N; ++i)
	{
		dp[i][ALL] = dp[i][0] = (dp[i - 1][ALL]) % MOD;
		for (int j = 1; j < 10; ++j)
		{
			dp[i][j] = (dp[i][j - 1] - dp[i - 1][j - 1] + MOD) % MOD;
			dp[i][ALL] = (dp[i][ALL] + dp[i][j]) % MOD;
		}
	}
	
	cout << dp[N][ALL]<< endl;

	return 0;
}

||사고 과정

처음에 2까지 경우의 수를 작성해보고

0부터 시작하는 경우의수, 1부터 시작하는 경우의 수 이렇게 나누어 생각을 했던것같다.

그렇게 나누어 보다보니까

두자리에서 0으로 시작하는 경우의 수는 한자리의  0 ~ 9로 시작하는 수,

두자리에서 1으로 시작하는 경우의 수는 한자리의  1 ~ 9로 시작하는 수,

...

두자리에서 9으로 시작하는 경우의 수는 한자리의  9로 시작하는 수,

가 나왔다.

그래서 자리수를 i, 시작하는 수를 j로 dp[i][j]형태의 이차원 배열로 테이블을 설정했다.

그 후 점화식을 세워보았고

dp[i][0]은 어쩔 수 없이 dp[i - 1][0] + ...  + dp[i - 1][9] 까지 더해주어야했고

dp[i][1]부터는 dp[i][j] = dp[i][j - 1] - dp[i - 1][j - 1] 이라는 식을 쉽게 세울수 있었다.

||사용 기법

• DP

||풀면서 느낀 것

• 테이블설정 후 점화식 작성

역시 DP는 이렇게 푸니까 많이 수월하다.

||새로 알게 된것

• MOD 관련

코드부터 예외까지 15분정도로 모두 끝냈지만 MOD 연산 때문에 시간이 많이 소요 됐다. 

MOD연산은 오버프로우(음수)를 막기위해 사용되는 것으로 음수가 나와서는 안되는데

중간에 A = ( A - B ) % MOD 이런 연산이 있는데 A - B에서 이미 음수가 나와 MOD를 해도 의미가 없는 경우가 있었다.

그래서 찾은 방법이 MOD를 더해주는것,

A = ( A - B + MOD ) % MOD

||나아 진것

• 깔끔한 풀이 사고 였다.

내가 작성했던 코드

#include <iostream>
#include <string>

using namespace std;

string str;
string f_str;

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	getline(std::cin, str);
	getline(std::cin, f_str);

	int d_length = str.length();
	int f_length = f_str.length();

	int cnt = 0;
	int result;
	while ((result = str.find(f_str)) != string::npos)
	{
		++cnt;
		str = str.substr(result + f_length, d_length);
	}
	cout << cnt;
	return 0;
}

다른 분이 작성한 더 나이스한 방법(하단)

int a;
int main() 
{
	string s, y;
	getline(cin, s); getline(cin, y); 
	auto pos = s.find(y); 
	
	while (pos != string::npos)
	{
		a++;
		pos = s.find(y, pos + y.size());
	}
	cout << a; 
}

||사고 과정

단어 검색이 중복없이 최대로 나오게 하려면 맨앞부터 차근차근 검색해가면 되니까 어려운건 없었고

검색하는 함수를 찾아보는데에 시간이 더 걸렸다.

||풀면서 느낀 것

• 문자열 문제도 항상 하나이상은 풀어야겠다.

문자열 문제는 가끔 풀게 되는데 할때마다 까먹는거 같아서 하루에 한번은 풀어야겠다.

#include <iostream>
#define MOD 9901
using namespace std;

unsigned long long int dp[100'001][2];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N; cin >> N;

	dp[1][0] = 1;
	dp[1][1] = 1;

	for (int i = 2; i <= N; ++i)
	{
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % MOD;
		dp[i][0] = (dp[i][1] + dp[i - 1][1]) % MOD;
	}

	cout << ((dp[N][1] * 2) + dp[N][0]) % MOD;
	return 0;
}

||사고 과정

일단 경우의 수를 i가 3일때 까지 그려보았다.

DP로 해결하려 했으니 dp[i - 1]에 추가를 하려고 했던것같다.

그러던 중 추가될 수 있는 마지막이 O X, X O, X X 이렇게 3가지인걸 확인 후

테이블을 2차원 배열로 하려고 생각을 했었다.

이렇게 생각하고 나니까 각 추가될 수 있는 개수가 규칙적으로 나오길래 예외 테스트를 하고 작성하여 풀이했다.

dp[i - 1]에 어떠한 걸 덧 붙일 때 크게 나오는 경우의 수를 찾아서 풀이 하는게 종종 보여서

이런 방법을 잘 기억해두고 있어야겠다.

||사용 기법

• DP

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

int dp[100'001];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	int n; cin >> n;

	dp[1] = 1;	dp[2] = 2;	dp[3] = 3;	dp[4] = 1;

	for (int i = 5; i <= n; ++i)
	{
		dp[i] = i;
		for (int j = 0; j *j <= i; ++j)
		{
			dp[i] = min(dp[i], dp[i - (j * j)] + 1);
		}
	}

	cout << dp[n];
	return 0;
}

||사고 과정

다른 사람의 풀이를 보고서야 해결했던 문제다

나는 처음에 어떠한 규칙이 있을거라고 생각했고 약간 많은 노가다와 억지로 규칙을 이끌었는데

예외가 있었다..

내가 잘못했던건 첫번째로 어떻게 해야 최소 개수를 구할 수 있는지 충분히 생각하지 않았다는 점,

물론 나올 수 있는 최대 제곱수를 이용 하긴 했지만 거기서 더 나아가지 못했다.

두번째로는 예외를 더 생각해보지 않았던 것

이거는 내가 항상 더 많이 주의해야겠다.

||사용 기법

• DP

||풀면서 느낀 것

• 응용

이 문제는 아주 유명한 문제인 최소개수로 동전 거슬러주기 와 비슷한데 동전은 잘 생각했으면서

이건 풀지 못한게 넘 속상하다

• 예외 생각

예외를 생각하기 넘 힘들어서 조금만 해보고 마는 경우가 있는데 앞으로는 일정 시간동안 생각해봐야겠다.

#include <iostream>
#include <queue>

#define MAX 1001
#define X second
#define Y first
using namespace std;

pair<int, int> pre[4] = {{1,0},{0,1},{-1,0},{0,-1}};
int arr[MAX][MAX] = { 0, };
int zeroUnit = 0;

queue<pair<int, int>> q;
int BFS(const int & sizeY, const int & sizeX)
{
	//안익은 토마토가 없으면 바로 0 반환
	if (zeroUnit == 0) return 0;

	int cX, cY, nX, nY;
	int day = 0;
	while (q.empty() == false)
	{
		++day;

		//큐의 길이 만큼(하루 만큼)
		int tempSize = q.size();
		for (int i = 0; i < tempSize; ++i)
		{
			cX = q.front().X;
			cY = q.front().Y;
			q.pop();

			for (int j = 0; j < 4; ++j)
			{
				nX = cX + pre[j].X;
				nY = cY + pre[j].Y;

				//정상적인 범위인지
				if (nY < 0 || sizeY <= nY || nX < 0 || sizeX <= nX) continue;

				//익은 토마토나 장애물이면 패스
				if (arr[nY][nX] != 0) continue;

				//안익은 토마토면 익히고 큐에 삽입
				arr[nY][nX] = 1;
				q.push({ nY,nX });
				--zeroUnit;
			}
		}

		//안익은 토마토 모두 익었으면
		if (zeroUnit == 0) return day;
	}
	return -1;
}

int main()
{
	//1. Get input value
	ios::sync_with_stdio(0), cin.tie(0);
	int x, y; cin >> x >> y;

	for (int i = 0; i < y; ++i)
	{
		for (int j = 0; j < x; ++j)
		{
			cin >> arr[i][j];
			if (arr[i][j] == 1) q.push({i,j});
			if (arr[i][j] == 0) ++zeroUnit;
		}
	}

	//2. Do BFS
	cout << BFS(y, x);
	return 0;
}

||사고 과정

이것도 0을 1로 만드는 최단 반복수를 구하는 BFS였다.

이번에는 BFS다 해 놓고 이차원 배열을 다시 처음부터 끝까지 0이 있나 없나 확인하는 것보다

좀 더 나이스하게 확인 하는 방법이 있는지 더 생각해봤다.

그래서 input을 저장할 때 0의 개수를 저장하고

0을 1로 변경할 때 그 개수를 감소 시켰다.

하루가 지나고 나서 그 개수가 0이 되면 모두 익은것으로 간주하여 return한다.

이러한 방법으로 시간을 좀 많이 줄인것 같아 뿌듯하당

||사용 기법

• BFS