아주정은's 릴상

아기상어... 이문제는 삼성 코딩테스트를 준비할때, 기출문제로 풀기를 시도한적있다.

그 때는 풀지 못하였다. 하지만 우선순위 큐에 대해 공부하고, 비교적 쉽게? 풀수있었다.

우선 배열을 다 돌면서 나보다 작은것들을 우선순위 큐에 집어넣고 우선순위에 따라 먹이를 준다.

그리고 vis랑 우선순위 큐를 초기화 해준다. 그러면 끄읕!

초기화에만 항상 신경을 써주자!

#include<iostream>
#include <cstdio>
#include<cstring>
#include <queue>
using namespace std;

struct Que {
	int x;
	int y;
	int time;
};

struct cmp {
	bool operator()(Que t, Que u) {
		if (t.time == u.time) {
			if (t.x == u.x) {
				return t.y > u.y;
			}
			else {
				return t.x > u.x;//value에 대해 내림차순임
			}
		}
		else {
			return t.time > u.time;
		}
	}
};

int board[21][21];
bool vis[21][21];

int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,-1,0,1 };

using namespace std;

int main() {
	int N;
	queue<Que> Q;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			if (board[i][j] == 9) {
				Q.push({ i,j,0 });
				board[i][j] = 0;
				vis[i][j] = true;
			}
		}
	}
	int vol = 2;
	int brun = 0;
	int time=0;
	while (1) {
		//int size = Q.size();
		priority_queue<Que, vector<Que>, cmp> PQ;
		while (!Q.empty()) {
			auto cur = Q.front();
			Q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];
				if (board[nx][ny] > vol or nx<0 or nx>N - 1 or ny<0 or ny>N - 1)continue;
				if (board[nx][ny] <= vol and vis[nx][ny] == false) {
					Q.push({ nx,ny,cur.time+1 });
					vis[nx][ny] = true;
					if (board[nx][ny] < vol and board[nx][ny]!=0) {
						PQ.push({ nx,ny,cur.time + 1 });
					}
				}
			}
		}
		
		memset(vis, false, sizeof(vis));
		if (!PQ.empty()) {
			auto cur = PQ.top();
			PQ.pop();
			board[cur.x][cur.y] = 0;
			brun++;//먹으면 증가
			time = cur.time;
			Q.push({ cur.x,cur.y,cur.time });
			vis[cur.x][cur.y] = true;
		}
		else {
			cout << time << endl;
			break;
		}
		
		if (brun == vol) {
			vol++;
			brun = 0;
		}
	}
}

진짜 할거없어서 한문제 풀어봤다.

최근에 캡디 같이하는 현정이네 그룹에 들어갔는데, 친절하게도 소융친구들을 위해 취준을 위한 100문제만 엄선해서 문제집을 만들어 놨더라.

그래서 거기 문제를 풀어보기로 결정했다. 일단 Level test에서 가장 첫번째문제가 행렬 곱셈이었다.

뭐 처음엔 식은 죽 먹기 거의 a piece of cake이라고 생각했다. 그러나~ 입력받고 생각을 찌끔?했다.ㅋㅋㅋㅋㅋㅋ

한조각 케익은 아니었고~ 케익 두조각정도 된것같다.

배열 세개 만들고, 입력받고 이게 곱셈이 어떻게 이뤄지는지 생각해서 반복문 돌리면 된다.

미래의 정은아 행렬 곱셈 원리 설명해줘야하는 흑우 아니제~??????????

내일부터 열심히 살자

어~ 소스코드 나름 깔끔하고 좋았다~

#include <iostream>


using namespace std;

int pro1[101][101];
int pro2[101][101];
int res[101][101];

int main()
{
	int N, M, K;
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin>>pro1[i][j];
		}
	}
	cin >> M >> K;
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < K; j++) {
			cin >> pro2[i][j];
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < K; j++) {
			for (int k = 0; k < M; k++) {
				res[i][j] += pro1[i][k] * pro2[k][j];
			}
			cout << res[i][j] << " ";
		}
		cout << endl;
	}
	
}

집가기 아쉬워서 한 문제 더 풀었다~

레벨테스트 원샷원킬 너무 기분좋다 ㅋㅋㅋㅋㅋㅋ

아니 여기 너무 공개된곳이라 평소 말투 쓰긴 어렵지만 기분 좋다^^

수 뒤집기도 레벨 테스트 문제인데 이문제는 조금 생각을 했다.

수를 뒤집고 원래 숫자랑 더하고 그 숫자에 대해 대칭인지 아닌지 판단하는 것이다.

하지만 나에겐 한 조각 케익이었다. 후후훗

숫자가 대칭인지 아닌지는 배열을 이용해서 bool원소를 처음에 true로 설정해주고 아닐경우 false로 바꿔주는 방식으로 했다.

개소리지만 나는 뒤집기를 좋아한다. 뭔가 한쪽이 일방적으로 이기는것은 재미도 없고, 지는 쪽은 맘이 약해져서 응원하게 된다. 그래서 항상 역전이 짜릿하고 멋지다. 나도 지금은 바텀이지만 언젠가 세상을 뒤집을 것이다.

이게 내 포부다. ㅋㅋㅋㅋㅋㅋㅋㅋ오글거리지만 나는 항상 생각한다. from bottom to the top!.!

#include <iostream>

using namespace std;

int main()
{
	int N;
	cin >> N;
	int arr[100];
	while (N--) {
		int input,copy,sum,reverse=0;
		int i = 0;
		bool T = true;
		cin >> input;
		copy = input;
		while (1) {
			
			reverse += input % 10;
			if (input / 10 == 0) {
				break;
			}
			reverse *= 10;
			input /= 10;
		}//역수 만들기
		sum = copy + reverse;

		while (1) {
			arr[i] = sum % 10;
			i++;
			if (sum / 10 == 0) {
				break;
			}
			sum /= 10;
		}//배열에 숫자 넣기

		//i번째 숫자랑 첫번째 숫자부터 차근차근 비교한다. i/2까지만 비교하면 된다. 앞뒤 비교이기 때문
		for (int j = 0; j < i / 2; j++) {
			if (arr[j] != arr[i - 1 - j]) {
				T = false;
			}
		}
		if (T)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

흠...하는게 없어서 한문제 풀어봤다.

처음에는 배열을 사용할려고 했지만 배열크기가 너무 커서 에러가떳다.

그래서 배열 안쓰고 그냥 숫자놀이했다.

처음에는 시간을 받고 while(t--)로 풀었는데 시간초가 많이 커질경우 시간초과가 떳다.

그래서 시간을 2*w랑 2*h로 나눠서 각각 pt, qt를 만들어줬다.

그랬더니 시간초과 극---벅!

암튼 로직은 굉장히 단순하다. bool변수를 선언해줘서 p랑 q가 플러스방향으로 갈지 마이너스 방향으로 갈지 결정해준다.

흠...언제쯤 빡고수될까? 그래프 막 그리고? 어? 구글 잡으러 간다;;;

#include <iostream>

using namespace std;



int main()
{
	int w, h,p,q,t;
	cin >> w >> h;
	cin >> p >> q;
	cin >> t;
	bool pb = true, qb = true;
	int pt = t % (2 * w);
	int qt = t % (2 * h);

	while (pt--) {
		if (p == w) {
			pb = false;
		}
		else if(p==0) {
			pb = true;
		}
		if (pb)
			p++;
		else
			p--;
	}
	while (qt--) {
		if (q == h) {
			qb = false;
		}
		else if (q == 0) {
			qb = true;
		}
		if (qb)
			q++;
		else
			q--;
	}
	cout << p << " " << q;
}

이제 슬슬 취업시즌 되니깐 또다시 백준을 시작하게되었다.

초심자의 마음으로 다시 시작하였다.

하지만 이문제는 뭐...쉬웠다?ㅋㅋㅋㅋㅋㅋ

문자열 받아서 문자열의 문자 하나씩 판단하고

알파벳에 해당하는 배열을 ++해주면 된다.

소스코드보면 개쉽다...참고해라

앞으로 꾸준히 노력하는 모습 보여주겠다.

#include<iostream>
#include<string>

using namespace std;

int list[26];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string str;
	cin >> str;
	for (int i = 0; i < str.size(); i++) {
		list[str[i] - 97]++;
	}
	for (int i = 0; i < 26; i++) {
		cout << list[i]<<" ";
	}
}

이 문제는 11개월 전에 풀었던 문제였다. 그때도 굉장히 어려워했던 문제였는데, 지금도 똑같았다. ㅋㅋㅋㅋ 문자 그대로 ㅁㅊ 소리가 나왔다. 예외처리를 해줄 것이 생각보다 많았기 때문이다.

오랜만에 문제를 푸는 거라 좀 어려움이 있었고, deque를 오랜만에 써봐서 어색했지만 초반 기능 구현은 어느 정도 괜찮았던 것 같다. 그리고 코드가 좀 지저분한데 앞으로 좀 더 개선해 나갈 것이다.

코드 구성은 일단 입력받을 것들 입력받는다. 11개월 전에는 string으로 받지 않고 char 배열로 받았었는데, 배열의 크기까지 고려해야 해서 string을 사용했다. 그리고 문자열로 받은 숫자 배열을 변환하는데 고민을 조금 했는데, 코드 보면 나름 이해할 수 있을 것이다. 처음 '[' 문자는 날려주고 그다음 문자부터 '0'~'9' 사이일 때 숫자로 변화해주는 것을 했다. 처음에는 두 자릿수 세자릿수 고려를 하지 않아 틀렸었는데, 이것까지 고려해서 수정하였다.

그다음은 deque를 이용하여 쉽게 구현하였다.

궁금한 것은 deque를 while문 안에 선언했을 때가 while문 밖에 선언했을 때보다 메모리 활용이 적다는 것이다.

​

아래는 while문 밖에 선언했을 때이고, 위에는 현재 코드처럼 while문 안에 선언한 것이다.

이유를 안다면 댓글로 달아주면 감사할 것 같다.

#include<iostream>
#include<string>
#include<deque>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T, p;
	bool FR, err;
	string str, numline; //명령어, 숫자 배열

	cin >> T;
	int i;

	while (T--) {
    	deque<int> dq;
		FR = true;
		err = false;
		cin >> str >> p >> numline;
		i = 1;
		while (numline[i]!='\0'){
			int x = 0;
			while (numline[i] >= '0' and numline[i] <= '9') {
				x *= 10;
				x += int(numline[i] - '0');
				i++;
			}
			if (x != 0) {
				dq.push_back(x);
			}
			i++;
		}
		
		i = 0; //변수 또 할당하기 귀찮고 메모리 아깝다고 판단해서 변수 초기화
		while (str[i]!='\0') { //여기서 문자열 판별
			if (str[i] == 'R') {
				FR = !FR;
			}
			else if(str[i]=='D') {
				if (dq.empty()) { //deque가 비어있을때 D명령어가 나오면 error발생
					cout << "error" << endl;
					err = true;
					break;
				}
				if (FR) {
					dq.pop_front();
				}
				else {
					dq.pop_back();
				}
			}
			i++;
		}
		
        //출력하는 부분 error 여부에 따라 '[',']'기호도 출력할지 판단
		if (!err) {
			cout << "[";
		}
		while (!dq.empty()) { 
			if (FR) {
				auto c = dq.front();
				dq.pop_front();
				cout << c;
			}
			else {
				auto c = dq.back();
				dq.pop_back();
				cout << c;
			}
			if (!dq.empty()) {
				cout << ",";
			}
		}
		if (!err) {
			cout << "]"<<endl;
		}
	}
}

일단 이 문제를 처음 봤을때, 단순 무식하게 반복문 돌리면 되는거 아니야? 생각하고 첫번째 문자열의 첫번째 문자부터 다 비교하려고 했다. 뭐 그렇게 해도되겟지만,, 문자열 길이가 n이라고 치면 시간이 n^2이 되기 때문에 비효율이라고 생각은 했다.

로컬에선 돌아갔는데 문제에서는 틀렸다고 나왔다 그래서 다른 사람 소스코드를 참고했다;;;;

혹시나 소스코드 보고 피드백있으면 편하게 댓글 달아주면 감사하겠다.

​

#include<iostream>
#include<string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N; // 몇번 시행할지
	bool T; // 참 거짓을 판별하기 위한 변수
	string str1, str2; // 입력받을 문자열
	int src[26], des[26]; // 입력받은 문자열들의 알파벳 갯수 세기위한 배열들
	cin >> N;
	while (N--) {
		T = true; // 변수 초기화
		
		for (int i = 0; i < 26; i++) {
			src[i] = 0;
			des[i] = 0;
		} //변수 초기화
		
		cin >> str1 >> str2;
		
		if (str1.length() != str2.length()) { // 두 문자열의 길이가 다를경우 실패
			T = false;
		}
		else {
			for (int i = 0; i < str1.length(); i++) {
				src[str1[i] - 'a']++;
				des[str2[i] - 'a']++;
			} // 문자열의 해당 알파벳에 해당하는 인덱스를 올려준다.

			for (int i = 0; i < 26; i++) {
				if (src[i] != des[i]) {
					T = false;
					break;
				}
			} // 반복문을 돌면서 하나라도 같지 않으면 실패
		}
		
		if (T) {
			cout << "Possible" << endl;
		}
		else {
			cout << "Impossible" << endl;
		}		
	}
}

이건 뭐 문제가 워낙 a piece of cake이었다.

물론 생각은 좀 했다. 남성과 여성으로 나눠서 크기 6짜리 int배열을 두개 만들었다.

그리고 학년별로 숫자를 세어주었다.

그 다음 최대인원으로 나누기와 나머지를 구해서 필요한 방의 갯수를 늘려주었다.

항상 변수 초기화와 직관적인 연산에 주의하자!!!!!!

일리 갱!

​

#include<iostream>
#include<string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int N, K, Y; // 참가 학생수, 한방의 최대인원, 학년
	bool S; // 성별 true가 남자, false가 여자
	int male[6], female[6];
	int r = 0; // 필요한 방 갯수
	cin >> N >> K;

	for (int i = 0; i < 6; i++) {
		male[i] = 0;
		female[i] = 0;
	}

	while (N--) {
		cin >> S >> Y;
		if (S) { // 남성
			male[Y - 1]++;
		}
		else { // 여성
			female[Y - 1]++;
		}
	}
	for (int i = 0; i < 6; i++) {
		
		int m = male[i] / K;
		int f = female[i] / K;
		if ((male[i] % K)!=0) m++;
		if ((female[i] % K)!=0) f++;
		
		r += m + f; // 방 갯수 올려준다.
	}
	cout << r << endl;

}

이 문제도 시간이 남아서 깔짝 해봤다.

나를 위한 기록이긴 하지만 사람들이 많이 봐줬으면 하는건 욕심이냐? 응~ 그리디야~

이문제를 보자마자 배열 두개 선언해서 복사를 하는게 낫겠다 생각해서

원본, 복사본 배열을 만들었다. 그리고 입력받은 숫자들을 통해 원본에서 복사본으로 갱신을 해준다음

다시 원본으로 옮겨주었다.

그렇게 하니깐 쉬웠다. 이해못하는 빠가는 없제~?

어~ 소스코드 깔금하니 좋다~

#include<iostream>
#include<string>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int a, b;
	int original[20], copy[20];
	for (int i = 0; i < 20; i++) {
		original[i] = i + 1;
		copy[i] = i + 1;
	}// 배열 초기화

	for (int i = 0; i < 10; i++) {
		cin >> a >> b;
		
		for (int j = b - 1; j >= a-1; j--) {
			copy[a + b - 2 - j] = original[j];
		}
		for (int j = 0; j < 20; j++) {
			original[j] = copy[j];
		} //original 갱신
	}
	for (int i = 0; i < 20; i++) {
		cout << original[i] << " ";
	}
}

처음에 이문제를 봤을때, 무슨 문제가 이렇게 랏같지? 했다.

이게 소수인지 아닌지 어떻게 판단하지? 라는 생각을 했다. 

소수인지만 판단하면 BFS를 통해서 두번째 입력받은 숫자를 찾는다면, break해주면 된다.

소수인지 판단하는것은 2부터 자신의 수/2까지 나누었을때, 나머지가 없으면 소수가 아닌것이다.

소스코드는 좀 더러울 수 있는데, 참고하고 피드백 항상 환영한다.

#include <iostream>
#include <queue>

using namespace std;

struct Que {
	int x;
	int time;
};


bool is_prime_number(int input) {
	int last = input / 2;
	for (int i = 2; i <= last; i++) {
		if (input%i == 0) return false; // 하나라도 나누어 떨어지면 return false;
	}
	return true;
}


void BFS(int num1, int num2) {
	queue<Que> Q;
	bool vis[10000];
	
	fill(vis, vis+sizeof(vis), false);
	
	Q.push({ num1,0 });
	vis[num1] = true;
	//num1의 숫자를 하나씩 바꿔주면서 큐에 넣어도되는지 판단한다.
	while (!Q.empty()) {
		auto cur = Q.front();
		Q.pop();
		if (cur.x == num2) {
			cout << cur.time << endl;
			break;
		}
		int current = cur.x;
		int arr[4], copy[4];
		for (int i = 0; i < 4; i++) {
			arr[i] = current % 10;
			copy[i] = arr[i];
			current = current / 10;
		}
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 10; j++) {
				arr[i] = j;

				int next = arr[3] * 1000 + arr[2] * 100 + arr[1] * 10 + arr[0];
				if (vis[next] == true or next == cur.x or arr[3] == 0) continue;
				if (is_prime_number(next)) {
					Q.push({ next,cur.time + 1 });
					vis[next] = true;
				}
			}
			arr[i] = copy[i];
		}

	}
}


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

	int t, num1,num2;
	cin >> t;
	
	while (t--) {
		cin >> num1 >> num2;
		
		BFS(num1, num2);

	}

}