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

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

	int s;
	int list[9] = { 1,2,3,4,5,6,7,8,9 };
	vector<int> q(9,0);
	stack<int> stc;
	for (int i = 0; i < T; ++i)
	{
		cin >> s;
		for (int j = 9; 0 <= j; --j)
		{
			//원값이 클때
			if (s > j)
			{
				s -= j;
				stc.push(j);
			}
			//같을때
			else if (s == j)
			{
				stc.push(j);
				break;
			}
		}

		while (stc.empty() == false)
		{
			cout << stc.top();
			stc.pop();
		}
		cout << "\n";
	}

	return 0;
}

||사고 과정

먼저 규칙이 있나 확인했다.

input값이 1 ~ 45이기 때문에 분명 규칙이 있을거라고 생각했다.

10은 1 + 9,11은 2 + 9,12는 3 + 9 이런식으로 이루어지는걸 발견하고

뒤에서부터 숫자를 비교해 크면 빼고 작으면 다음, 같으면 종료 하기로 생각했고

또 생각해야할것은 어떻게 출력할까였는데 값을 뒤집어야 했다.

그래서 값을 뒤집기 편한 스택을 사용했다.

||사용 기법

• Greedy
• Stack

||나아 진것

• 규칙을 찾아보는것
• 자료구조를 이용한것

값 뒤집는 스택을 사용한건 편하게 잘 사용한것 같다.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#define MAX 100005
using namespace std;


vector<int> v[MAX];
int result[MAX];
bool visit[MAX];

int Cnt = 0;
void DFS(const int & node)
{
	//0.방문했다면 종료
	if (visit[node] == true) return;

	//1. 방문하지 않았으면 방문처리
	visit[node] = true;
	result[node] = ++Cnt;

	//2.주변노드 방문
	for (const auto & data : v[node])
	{
		if (visit[data] == false)
		{
			DFS(data);
		}
	}
	return;
}

int main()
{
	//1. 입력받기
	ios::sync_with_stdio(0), cin.tie(0);
	int N, M, R; cin >> N >> M >> R;

	int a, b;
	for (int i = 0; i < M; ++i)
	{
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}

	//2. 오름차순 정렬
	for (auto & data : v)
	{
		sort(data.begin(), data.end(), less());
	}

	//3. DFS
	DFS(R);

	//4. Print
	for (int i = 1; i <= N; ++i)
	{
		cout << result[i] << "\n";
	}
	return 0;
}

||사고 과정

단순 DFS구현

||사용 기법

• DFS

||풀면서 느낀 것

• 재귀형과 스택

오랜만에 풀어서 재귀형과 스택형을 혼합해서 사용해버려 처음에 틀렸었다.

이번문제로 과정을 확실히 알고 넘어가야겠다.

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

vector<string> v;
int i, j;
int main()
{
	//1. 입력받기
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	v.resize(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> v[i];
	}

	//2. 각 자리수 합하고 저장
	int alp[27];
	memset(alp, 0, sizeof(int) * 27);

	for (i = 0; i < v.size(); ++i)
	{
		int pow = 1;
		for (j = v[i].size() - 1; 0<= j ; --j)
		{
			alp[v[i][j] - 'A'] += pow;
			pow *= 10;
		}
	}
	sort(alp, alp + 27, greater());

	int result = 0;
	int cnt = 9;
	for (auto data : alp)
	{
		result += data * cnt;
		--cnt;
	}
	cout << result;
	return 0;
}

||사고 과정

이번 문제는 못풀었다ㅠ

못푼 주 요인은 문제 해석을 잘못했다.

완전 핀트가 나갔었음

||사용 기법

• Greedy

||풀면서 느낀 것

• 테스트 케이스를 좀 분석해야봐야 할듯하다.

문제 해석하고 대충 테스트케이스에서 이러니까 이렇게 나오는구나 말고

input, output이 내가 확인한 과정과 똑같이 나오는지 세세하게 확인을 해야겠다

• 그리디는 거의 정렬이 필수인듯하다.

여태 그리디를 풀면서 정렬을 안쓴적이 없는거 같다.

• 가중치

어떻게 보면 가중치가 있다고 볼수있는데 가중치를 이용한건 처음인거 같아서

앞으로 가중치도 필수로 고려해봐야겠다.

#include <stdio.h>

int main()
{
	int A, B;
	while (scanf("%d %d", &A, &B) == 2)
	{
		printf("%d\n", A + B);
	}
	return 0;
}

||새로 알게 된것

• Scanf의 반환 값

scanf의 반환 값이 있는 줄 처음 알았다.

반환 값은 입력 받은 개수!

또한 EOF을 반환 할 수도 있다

그리고 그와 짝궁인 printf에도 반환 값이 있다.

반환 값은 출력되는 문자의 개수!

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

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

	int R;
	string str;
	for (int i = 0; i < N; ++i)
	{
		cin >> R;
		cin >> str;
		for (char c : str)
		{
			cout << string(R, c);
		}
		cout << "\n";
	}
	return 0;
}

||사용 기법

• string 생성자
• string을 이용한 ranged for loop

||새로 알게 된것

• string 생성자에서 원하는 개수와 원하는 문자로 생성 

string (원하는 개수, 원하는 문자) 로 생성하는걸 처음알았다.

ex) string(5,'A') == "AAAAA" 가 생성된다.

#include <iostream>
using namespace std;

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

	for (int i = 0; i < t; ++i)
	{
		cin >> n;
		if (n == 1) cout << 2 << "\n";
		else
		{
			int add = n % 3 == 0 ? 0 : 1;
			cout << n / 3 + add << "\n";
		}
	}

	return 0;
}

||사고 과정

일단 최소 이동 횟수가 나오려면 최대한 3으로 많이 가야하니까 목적지에서 3을 나누어야겠다고 생각했다.

3으로 나눈 나머지는 0, 1, 2 세가지 경우의 수가 나오는데 이 각 수에 2를 어떻게 넣느냐를 생각했다.

1이 남은 7같은 경우에는 3으로 2번 이동해서 6만큼 가고 여기서 3만큼 한번 뒤로가고 2만큼 두번 가면 7이 된다.

하지만 애시당초 3만큼 1번가고 2만큼 2번가면 최소 3번만에 갈 수가 있다.

즉, n / 3 + 1을 하면 최소 횟수가 나왔다.

이는 1이 남는 모든수에 해당하고 2도 비슷한 방식으로 +1을 해주면 최소 횟수가 나왔다.

그렇기에 나머지 값이 1,2가 나오면 단순 +1 을 해주면 되고 0이면 나눈 값을 반환하면 되겠다.

예외로 1은 무조건 0부터 시작하기에 2만큼 뒤로 갔다 3만큼 앞으로 가야하기에 1은 예외처리 했다.

||사용 기법

• Greedy

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

#define MAX 100'005
#define FRONT q.front()

vector<int> nodes[MAX];
bool isVisit[MAX];
int result[MAX];

queue<int> q;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	int N, M, R; cin >> N >> M >> R;

	int temp1, temp2;
	for (int i = 0; i < M; ++i)
	{
		cin >> temp1 >> temp2;
		nodes[temp1].push_back(temp2);
		nodes[temp2].push_back(temp1);
	}

	//내림차순 정렬하기
	for (int i = 1; i <= N; ++i)
	{
		sort(nodes[i].begin(), nodes[i].end(),greater<>());
	}

	q.push(R);
	memset(isVisit, 0, sizeof(bool) * MAX);
	isVisit[R] = true;
	memset(result, 0, sizeof(int) * MAX);
	result[R] = 1;
	int cnt = 1;
	while (q.empty() == false)
	{
		for (const auto & data : nodes[FRONT])
		{
			if (isVisit[data] == false)
			{
				q.push(data);
				isVisit[data] = true;
				result[data] = ++cnt;
			}
		}
		q.pop();
	}

	for (int i = 1; i <= N; ++i)
	{
		cout << result[i] << "\n";
	}
	return 0;
}

||사고 과정

단순 BFS를 구현하는것이기에 특별한 사고는 없었다.

||사용 기법

• BFS

||풀면서 느낀 것

• 노드를 1부터 시작하면 주의할것

이번에 이것때문에 30분정도 시간을 소모했는데 BFS는 노드의 인덱스가 1부터 N까지 탐색하지만

입력 받을 때 0부터 N-1 까지 탐색하고 있었다 =~=

이건 종종 있는 일이라 주의할 겸 포스팅을 했다.

||나아 진것

• 좀 더 수월한 BFS

역시 계속 다루다 보니까 계속 더 빠르게 구현이 되는듯하다.

#include<iostream>
#include<string>

typedef unsigned int integer;
using namespace std;

int main()
{
	integer A, B;
	cin >> A >> B;

	integer cnt = 1;
	while (A <= B && B != 0)
	{
		if (A == B)
		{
			cout << cnt;
			return 0;
		}

		if (B % 10 == 1)
		{
			B /= 10;
		}
		//홀수 체크
		else if ((B & 0x1) == 0x1)
		{
			cout << -1;
			return 0;
		}
		else
		{
			B /= 2;
		}
		++cnt;
	}

	cout << -1;
	return 0;
}

||사고 과정

처음에 분명 각 *2를 하거나 1을 추가하는 특정 조건이 있을거라 생각했다.

그래서 언제 1이 추가될까 생각을 했는데 정말 규칙이 없었다.

생각하던중에 A를 계속 순서없이 계속 연산하면 규칙도 없고 경우의 수도 많기 때문에

미로처럼 거꾸로 찾으면 쉽지 않을까 생각해서

A →  B가 아닌 B →  A로 거꾸로 연산해보던 중에

마지막 자리가 1이 되는 순간  나눗셈은 불가능하고 무조건 1을 빼야하는 규칙을 찾았다.

||사용 기법

• 그리디

• 비트연산

||풀면서 느낀 것

• 무언가 그리디는 규칙이 딱딱 있는 느낌같다

규칙이 딱 정해져있어서 그냥 쭉 나아가다가 정답나오면 정답을 하는 느낌이다 =~=

• 그래프?

다 풀고나서 다른 사람들도 보니까 그래프로 푸는 사람들도 있던데

나도 처음에 그래프로 풀수 있는가? 생각은 해봤지만 전혀 아닌거 같아서 다른 방법을 찾았는데

역시 아직 그래프적 사고는 서툰듯하다 😪

• 정수 뒷자리 빼기

나는 처음에 뒷자리를 빼야해서 string으로 pop하는걸 생각했었는데

정수도 / 10 을 저장하면 뒷자리가 빠지더라..

이렇게 정수를 사칙연산으로 여러가지 응용 할 수 있는 방법도 생각해봐야겠다.

||나아 진것

• 잘했다

요즘 잘 못풀어서 자신감이 하락했었는데

푸는 과정자체가 잘 돌아갔던 문제로 전체적으로 초반보다 나아졌다고 생각한다