대엉코딩

www.acmicpc.net/problem/7569

1. 풀이방법.

- 3차원배열을 이용한 bfs로 해결하였습니다.

- 처음에 input을 받을 때 전체토마토 수, 익은토마토 수를 체크한 후

- bfs를 돌면서 익을 때 마다 익은토마토수를 ++ 해주며,

- 큐가 비었을 때(종료조건) -> 익은토마토수 == 전체토마토수 이면 걸린시간을 출력

                                   -> 익은토마토수 != 전체토마토수 이면 (모두익힐 수 없음 -1출력)

2. 주의사항

- 3차원배열이므로 행,렬,높이 를 스스로 잘 설정하여 H,N,M 과 비교연산 등을 할 때 헷갈리지 않게 주의.

3. 나의코드

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

int tomatobox[101][101][101];//높이,세로행,가로행
bool visit[101][101][101];
int N, M, H;
int totaltomato;
int dx[6] = { 1,-1,0,0,0,0 }; //6방향탐색
int dy[6] = { 0,0,1,-1,0,0 };
int dz[6] = { 0,0,0,0,1,-1 };
struct tomato {
	int h, n, m;
};
queue<tomato> tmpq;
int timecount;
int tomatocount;

void inputs() {
	cin >> M >> N >> H;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < M; k++) {
				cin >> tomatobox[i][j][k];
				if (tomatobox[i][j][k] == 1) { //익은토마토
					totaltomato++;
					tomatocount++;
					tomatobox[i][j][k] = true;
					tmpq.push({ i,j,k });
				}
				if (tomatobox[i][j][k] == 0) { //익지않은 토마토
					totaltomato++;
				}
			}
		}
	}
}
bool sidecheck(int x, int y, int z) { //경계선 체크
	if (x >= 0 && x < H &&y >= 0 && y < N &&z >= 0 && z < M) return true;
	else return false;
}
void bfs() {
	while (1) {
		int qsize = tmpq.size();
		while (qsize--) {
			tomato thistomato = tmpq.front();
			tmpq.pop();
			for (int i = 0; i < 6; i++) {
				if (sidecheck(thistomato.h+dx[i], thistomato.n+dy[i], thistomato.m+dz[i])
					&&tomatobox[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]]==0 && visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] == false) {
					visit[thistomato.h + dx[i]][thistomato.n + dy[i]][thistomato.m + dz[i]] = true;
					tomatocount++; //토마토가 익음
					tmpq.push({ thistomato.h + dx[i],thistomato.n + dy[i],thistomato.m + dz[i] });
				}
			}
		}
		if (tmpq.empty()) { //종료조건
			if (totaltomato == tomatocount) {
				cout << timecount << "\n";
				return;
			}
			else {
				cout << -1 << "\n";
				return;
			}
		}
		timecount++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	bfs();

	return 0;
}

www.acmicpc.net/problem/16397

1. 풀이방법

- 처음에는 재귀를 이용한 DFS로 모든 경우를 탐색하려고 생각하고 코드를 구상했으나,

- 문제 조건을 보시면 T가 최대 99,999이고, A버튼만 누를 경우 숫자가 1씩 증가하는데 N이 0일경우를 생각해보면

- 재귀를 이용해서 짰을때 stackoverflow를 만났습니다. (조건을 보고 미리 생각했어야되는데....으휴 덤벙덤벙)

- 원리는 비슷한데 queue를 이용해서 bfs로 똑같이 옮겨서 해결했습니다.

2. 주의사항

- 조건도 꼼꼼히 파악하자.

3. 나의코드

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

int N, T, G;
bool visit[100000];
queue<pair<int,int>> tmpq;



int getmodnum(int tmp) {
	int maxmod = 1;
	while (1) {
		if (tmp == 0) break;
		tmp /= 10;
		maxmod *= 10;
	}
	maxmod /= 10;
	return maxmod;
}

int bfs() {
	while (!tmpq.empty()) {
		int tmpn = tmpq.front().first;
		int tmpcnt = tmpq.front().second;
		tmpq.pop();
		if (tmpcnt > T) break;
		if (tmpn == G) return tmpcnt;

		int num = tmpn + 1;
		if (num < 100000 && visit[num] == false) {
			visit[num] = true;
			tmpq.push({ num,tmpcnt + 1 });
		}

		num = tmpn * 2;
		if (num < 100000) {
			int minusnum = getmodnum(num);
			num -= minusnum;
			if (num < 100000 && visit[num] == false) {
				visit[num] = true;
				tmpq.push({ num,tmpcnt + 1 });
			}
		}
	}
	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> T >> G;
	tmpq.push({N, 0}); //시작점
	visit[N] = true;
	int result = bfs();
	if (result == -1) cout << "ANG" << "\n";
	else cout << result << "\n";
	return 0;
}

www.acmicpc.net/problem/1655

1. 풀이방법

 - 직관적인 풀이 : 중간값을 의미를 떠올리면 수빈이가 숫자를 하나 외칠 때 마다 정렬을 수행 후 중간에 위치한

                        값을 뽑아내면 된다 . ---> 시간초과 (아마? 작성해서 제출해보진 않았습니다.)

 - 우선순위 큐를 이용했습니다.

   (1단계)

      -가장 큰 값을 뽑아내는 pqless와 가장 작은 값을 뽑아내는 pqgreater를 선언 후 

      - 매 단계 마다, 그 전의 중간값을 기준으로 pqless에 넣을지 pqgreater에 넣을지를 판단해서 우선순위 큐에 삽입

   (2단계)

      - 중간값을 뽑아내기 위해서는 한쪽 우선순위 큐만 너무 커져 버리면 안됩니다 즉 데이터의 수가 1차이 이하로 나야

         하므로 2이상 차이가 날경우 큰 쪽의 우선순위 큐의 값을 작은 크기의 우선순위 큐 로 옮겨주는 작업을 수행

   (3단계)

      - 중간값을 뽑아내서 출력 (다음단계를 위한 중간값 저장)

      - 문제 조건에 따라서 두 우선순위큐의 사이즈를 비교한후 (편의상) 왼쪽 위에 뽑아낼지 오른쪽 위에서 뽑아낼지

         결정하면 됩니다.

2. 주의사항

 - 개인적으로는 우선순위 큐 두개를 사용해야 겠다 라는 생각이 든 이후 부터는 상대적으로 매우 쉬웠습니다.

 - 문제 조건에 따른 단계별 구현만 차근차근 해주시면 되겠습니다.

3. 나의코드

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

int N;
int centervalue;

priority_queue<int, vector<int>> pqless;
priority_queue<int, vector<int>, greater<int>> pqgreater;

void InputToQueue(int num) {
	if (num <= centervalue) { pqless.push(num); }
	else { pqgreater.push(num); }
}
void ModifyQueue() {
	if (pqless.size() > pqgreater.size() + 1) { //2이상 차이날 경우
		int modinum = pqless.top();
		pqless.pop();
		pqgreater.push(modinum);
	}
	else if (pqgreater.size() > pqless.size() + 1) { //2이상 차이날 경우
		int modinum = pqgreater.top();
		pqgreater.pop();
		pqless.push(modinum);
	}
}
void GetCenterValue() {
	if (pqless.size() >= pqgreater.size()) {
		centervalue = pqless.top();
	}
	else {
		centervalue = pqgreater.top();
	}
	cout << centervalue << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int tmp;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		if (i == 0) {
			pqless.push(tmp); centervalue = tmp; cout << centervalue << "\n"; continue;
		}
		InputToQueue(tmp);
		ModifyQueue();
		GetCenterValue();
	}
	return 0;
}

www.acmicpc.net/problem/1715

1. 풀이방법

- 작은 순서대로 정렬하여 카드 묶음을 묶어나가면 된다.

- 주의할 점은 처음에만 정렬하고 앞쪽부터 연산 한다고 해결되는 것이 아니다

- 만약에 20 30 40 45 70 이 있을 떄 20+30=50이 되고 연산 순서를 그대로 하면 50 40 45 70 이 된다.

- 이러면 50+40이 먼저 계산 되므로 분명 오답을 가지고 올 것이다.

- 그럼으로 한번의 연산을 할 때마다 계산을 앞으로 해야할 배열들은 정렬되어 있어야 한다.

2. 주의사항

- 위의 로직을 처음에 그대로 vector와 sort로 구현하였다...물론 답은 맞겠지만 입력사이즈를 고려하면 시간초과가 뜬다.

  (매 단계마다 sort를 할 경우)

- 그래서 priority_queue 우선순위 큐를 이용하였다 <오름차순으로> 그러면 단계마다 합친 결과를 push 할 때 정렬 되

- 어 큐에 들어가므로 sort를 할 필요가 없다.

- 한번에 두개를 큐에서 꺼내고 그 합을 다시 넣어주므로 반복문은 N번이 아닌 N-1번만 돈다.

3. 나의코드

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

int N;
priority_queue<int, vector<int>, greater<int>> carddeck;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	int card;
	for (int i = 0; i < N; i++) {
		cin >> card; carddeck.push(card);
	}
	int minsum = 0;
	int tmpcard1, tmpcard2;
	for (int i = 0; i < N-1; i++) {
		tmpcard1=carddeck.top();
		carddeck.pop();
		tmpcard2 = carddeck.top();
		carddeck.pop();
		minsum += (tmpcard1 + tmpcard2);
		tmpcard2 += tmpcard1;
		carddeck.push(tmpcard2);
	}
	cout << minsum;
	return 0;
}

* 큐(queue) 란 ?

- FIFO(First In Fisrt Out)

- 편하게 생각해보면 맛집에 줄 서있는 사람들을 떠올리면 될것이다.

  (먼저 줄을 선 사람 순서대로 식당에 들어간다.)

- 그외에 번호표, 버퍼(buffer) 도 같은 개념이라고 보시면 되겠네요 !

* 큐의 연산

- 삽입, 삭제, 비어있는지 확인, 맨 앞 (front) 확인,끝(rear) 확인 크기 등의 연산이 있다.

- 객체 : 선입선출(FIFO)의 접근 방법을 유지하는 요소들의 모임

   연산 : enqueue(x)

           dequeue()

           front()              

           rear()

           peek() -> front에 위치한 데이터 확인

           empty()

- 시간 복잡도: (배열을 통한 구현으로 생각해보겠습니다.)

                   enqueue의 경우 배열 맨 끝에 추가하면 됩니다. O(1)

                   dequeue의 경우 배열의 앞에서 빼고 다른 요소들을 모두 하나씩 당기는 방식으로 구현할 경우 O(n)

                                         (이경우 front는 무조건 index가 0일 것이므로 따로 index변수를 관리 할 필요가 없겠죠)

                                         배열의 앞에서 빼고 front index를 따로 관리하여 +1만 해주는 경우 O(1) - 효율적

                   그 외 front(), rear(), peek() 등의 연산들은 index를 관리해줄 경우 모두 O(1) 타임 이겠죠?

* 큐 구현상의 문제점

                   만약 index를( 따로 front와 rear 를 가리키는) 관리해주는 방식으로  (효율적)

                   그럴 경우 배열의 크기는 정해져 있다는 것을 생각 해보면 계속 enqueue와 dequeue 작업을 수행하면

                   계속 뒤로 밀려지게 되다가 결국 배열의 크기를 넘어 가게 되면 오류가 발생하게 될 것 입니다.

                   이 때는 환형 배열을 이용 하면 이 방식의 문제를 해결할 수 있습니다.

                   만약 자료가 많아서 배열을 모두 채울경우 배열의 크기를 두배로 늘려서 다시 모든 요소들을 새로운

                   큰 크기의 배열로 옮겨주고 수행해야 하는 경우 enqueue 는 O(n) 타임이 걸릴 것입니다.

                   만약 연결리스트(링크드 리스트)로 구현할 경우 이러한 문제는 해결 할 수 있을것입니다.

                   하지만 링크드 리스트로 구현할 경우 코드상의 즉 런타임시간에 동적할당을 자주 해야 할것이고

                   이로인해 성능이 배열을 통해 구현한 순환큐 보다는 성능이 떨어질 수도 있습니다.

                   그러므로 만약 큐(자료)의 크기가 어느정도 예측이 가능할 경우 배열을 통한 순환큐가 

                   더 적절한 상황이 나타날 수 있습니다.

* 큐 활용의 예

(큐의 특성을 생각해본다면 매우 많겠죠???)

- 프린트기

- 너비우선탐색(bfs)

- 은행업무

- 그외 등등

* 큐의 구현

< 배열 이용한 구현>

https://www.acmicpc.net/problem/1966

큐를 이용한 문제입니다.

문제조건은 상세하게 나와있는 편입니다.

다만 입력조건 중 말이 헷갈리는 부분이 나와서 이는 필기노트에 제가 이해하기 쉬운 말로 바꾸어 놓았습니다.

그리고 queue는 순회가 안되므로( for문을 이용하여 배열처럼 쉽게 탐색이 안됨)

어떻게 할까 생각을 하다가 중요도를 따로 담은 vector를 소팅을 시키고

현재 중요도를 가리키는 변수 n을 선언하여 가장 높은 중요도를 가진 문서가 queue에서 pop()

되어 프린트가 되면 n을 1증가시켜 두번쨰 높은 중요도를 가리키게끔 하였습니다.

필기노트를 보시면 이해가 빠르리라 생각합니다.

다른분들은 어떻게 푸셨는지 모르겠네요. 한번 찾아봐야겠네요!.

<필기>

<코드>

추상화 데이터 타입 그런 자료구조를 왜 만들고 왜 필요할까?

생각해보면 스케쥴러를 짜는데

큐(선입선출,FIF0)를 사용하지 않고 배열을 이용한다면....

직접 인덱스(index)관리를 일일히 해주어야 한다는 소리인데

규모가 커지면 이건 정말 쉽지 않은 문제이다.

하지만 추상화데이터타입을 만들고 그를 활용한다면 단지 pop과 푸쉬만 이용하면

따로 직접 index 를 관리 하지 않아도 된다

추상화데이터타입을 이용하는 이유 중 하나는 **인덱스 관리의 어려움** 이 있지 않을까?

스택에 함수 call과 관련된 정보를 담을 때도 스택이라는 자료구조를 이용하지 않으면 생각만 해도 끔찍하다...

들은 내용중 기억에 남기고 싶은 내용이라 정확하지 않을 수 있지만 기록을 해놓습니다...

https://www.acmicpc.net/problem/2164

- 문제에 주어진 조건만 파악 한다음 차근차근 따라가면 된다.

- 자료구조 는 여러가지를 사용해서 해결할 수 있을 것이다.

- 저는 큐 (FIFO)를 사용했습니다.

- 카드 덱을 위에서 부터 하나씩 꺼내고 다시 밑으로 넣고 함으로 큐가 적당할 것 이라고 생각해서 이용하였습니다.