아주정은's 릴상

Z라면 요즘 유미의 세포들의 컨트롤 젯이 생각난다.

흠.... 이거 문제 고민을 많이했다.

왜냐 흠 그냥 길게 생각안하고 졸렸기 때문이다.

지금은 싣니 공항이다. 공항에서 노숙중인데, 새벽에 풀어보니깐 해결됐당....

재귀함수인데, 4등분을 계속해서 갯수가 1개가 될때까지 한다.

근데 이렇게 하면, 시간초과가 된다. 그래서 재귀를 넣을때, 찾으려는 값을 조건문으로 걸러준다.

그럼 시간초과 해결!!

zza 의미는 Z자 라는 뜻?ㅋㅋㅋㅋㅋ이다.

#include<stdio.h>
#include<iostream>
#include<math.h>

using namespace std;

int x, y,time=0;

void zza(int a, int b, int c, int d, int vol) {
	if (vol==1) {
		if (a == x and b == y) {
			cout << time<<endl;
		}
		time++;
	}
	else {
		if(x< (a + c) / 2 and y< (b + d) / 2) zza(a, b, (a + c) / 2, (b + d) / 2, vol / 4);
		else time += vol / 4;
		if (x < (a + c) / 2 and y >= (b + d) / 2)zza(a, (b + d) / 2, (a + c) / 2, d, vol / 4);
		else time += vol / 4;
		if (x >= (a + c) / 2 and y < (b + d) / 2)zza((a + c) / 2, b, c, (b + d) / 2, vol / 4);
		else time += vol / 4;
		if((a + c) / 2<=x and (b + d) / 2<=y)zza((a + c) / 2, (b + d) / 2, c, d, vol / 4);
		else time += vol / 4;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N>>x>>y;
	
	zza(0,0,pow(2, N), pow(2, N), pow(4, N));
}

하노이 타워는 컴퓨터 프로그래밍 시간에 예제로 배웠었다.

또한, 자료구조시간에도 배웠다. 그래서 이동 방법을 구현하는데는 큰문제는 없었다.

그치만 계속 문제가 발생했다. 시간초과가 뜨는것이다.

아마도

ios::sync_with_stdio(false);

cin.tie(0);

를 쓰지 않아서 그런것같다.

저거를 쓰기전에 scanf printf로 해보았는데, 잘 됐다.

앞으로는 꼭 써주자. 그리고 endl 도 쓰지 말라대? 암튼 앞으로 "\n"를 사용하도록 하지.

하노이 타워는 n개의 탑을 1에서 3으로 이동시킬려면, 1에서 2로 n-1개를 옮기고 n번째 돌(?)을 1에서 3으로 옮긴다. 그리고 n-1개를 2에서 3으로 옮기면 된다.

이걸 재귀로 부르면 된다.

구웃~!

#include<stdio.h>
#include<iostream>

using namespace std;

void print(int a, int c) {
	cout<<a<<" "<<c<<"\n";
}

void hanoi(int n, int a, int b, int c) {
	if (n == 1) {
		print(a, c);
	}
	else {
		hanoi(n - 1, a, c, b);
		print(a, c);
		hanoi(n - 1, b, a, c);
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
	int N, a = 1;
	cin>>N;
	for (int i = 0; i < N; i++) {
		a *= 2;
	}
	cout<<a-1<<"\n";
	hanoi(N, 1, 2, 3);

}

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

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

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

그리고 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;

}