PS) 백준 12764, 7576, 1260번 (싸지방에 간 준하, 토마토, DFS와 BFS) in c++

백준 12764번 싸지방에 간 준하

 

이전에 시간초과 난 이유 분석 -> 수정한 부분 설명 아이패드 p32

사용할 수 있는 컴퓨터를 다 빼주고 컴퓨터의 index를 고려하지 않고 사용자를 앉혀 주면 된다고 생각했다. 어짜피 이후의 사람들이 앞 컴퓨터를 앉으므로 => 마지막 컴퓨터일 경우 

해결 ) 컴퓨터를 빼 주고, 컴퓨터의 index를 우선순위 큐에 담아 정렬시킨다. 우선순위가 높은 컴퓨터를 먼저 이용한다.

 

마지막 하나의 반례가 더 있었다. 이미 종료한 컴퓨터를 사용하는 경우, (computerq에 있는 컴퓨터) 다시 컴퓨터의 종료시간을 종료시간 큐에 넣어주어야 한다. 그런데 방금 사용한 컴퓨터가 다음 컴퓨터 시작 전에 종료하는 경우, 이 컴퓨터는 우선순위 큐에 담기지 않았기 때문에, 우선순위 큐에 담겨 있는 다른 컴퓨터가 사용될 수 있다. 따라서 우선순위 큐에 담겨 있는 컴퓨터를 무조건 바로 사용하지 말고, 항상 종료시간 큐를 확인하여 컴퓨터 우선순위 큐를 갱신해주어야 한다. 

 

시간 복잡도

풀이 과정 적기

 

#include<stdio.h>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;

int computer[100010] = { 0, };

int main() {

	int n; scanf("%d", &n);
	int s, e;
	int computerindex = 1;
	int vindex = 0;
	int pqsecond;

	vector<pair<int, int>>v; //시작시간과 종료시간을 담음
	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 끝나는 시간을 담음
	priority_queue<int, vector<int>, greater<int>> computerq; //사용할 수 있는 대기 컴퓨터 명단을 저장

	for (int i = 0; i < n; i++) {
		scanf("%d%d", &s, &e);	v.push_back(make_pair(s, e));
	}
	//시작시간을 기준으로 정렬함.
	sort(v.begin(), v.end());
	while (vindex < v.size()) {
		if (pq.empty()) { //사용하고 있는 컴퓨터가 없을 경우
			pq.push({ v[vindex].second, computerindex });
			computer[computerindex]++;	computerindex++;
			vindex++;
		}
		else { //사용하고 있는 컴퓨터가 있는 경우에 
			//만약 시작시간이 종료시간보다 늦으면 컴퓨터를 다 빼주고 컴퓨터번호를 computerq에 넣어준다
			if (pq.empty() == false && pq.top().first < v[vindex].first || computerq.empty()==false) {
				while (pq.empty()==false && pq.top().first < v[vindex].first) {
					computerq.push(pq.top().second);
					pq.pop();
				}
				computer[computerq.top()]++; //사용할 수 있는 컴퓨터 중에서 가장 앞 컴퓨터를 사용
				pq.push({ v[vindex].second,computerq.top() }); 
				computerq.pop(); vindex++;
			}
			else {
				pq.push({ v[vindex].second, computerindex });
				computer[computerindex]++;
				computerindex++;
				vindex++;
			}
		}
	}
	printf("%d\n", computerindex - 1);
	for (int i = 1; i <= computerindex-1; i++) {
		printf("%d ", computer[i]);
	}
}

 

12755 수면 장애

 

#include<stdio.h>
#include<string>
using namespace std;
int main() {
	string str;
	int n; scanf("%d", &n); //n번째 자리에 있는 숫자를 구해야 함
	int number = 9;  //9 90 900 9000
	int one = 1;	//1 2 3 4 5
	while (n-number*one>0) {
		n = n - number * one;
		number = number * 10; one++;
	} 
	number = number / 10; int nine = 10;
	while (number/nine > 0) {
		number += number / nine;  nine = nine * 10;
	}
	int con = (n + one - 1) / one; //div번째 수
	int div = n % one;
	number = number + con;

	if (div == 0) 	printf("%d", number % 10);
	else {
		n++;
		str = to_string(number); //stoi string to int
		printf("%d", str[div - 1]-48);
	}
}

수학 문제

못 품 개 어려움 실버 5인데 .... 넘...너무..ㅇ ㅓ렵더라

내 접근 방법은 자리수 1인 수가 9개, 자리수 2인 수가 90개, 자리수 3인 수가 900개인것을 이용해서 수를 다듬어 주고, n자리수의 con번째 수의 div 자리수를 출력하는 코드를 작성하였다. 중간에 틀리고 틀리고 또 틀렸다. 반례가 많았음. 구현을 애초에 깔끔하게 해주지 못했다.(몫과 나머지를 구하는 식이 실제로 의도했던 결과를 내지 않았던 것, 따로 처리해준 부분이 후에 가니 이해가 되지 않았던 것)

 

앞으로는 변수가 많아질 경우 변수 이름을 직관적으로 설정하자 => 특히 수학 문제에서는 더더욱.,,,

몫과 나머지를 구하는 경우, 수를 압축할 경우, 케이스를 나누어 다르게 구현하는 경우 => 노트에 적어가면서 변수의 변화나 반례 충분히 찾고 확실해진 후에 구현해보자!

 

다음에 풀어본다....

★ 수학 문제는 변수가 많아지면 헷갈려서 코드가 길어지더라도 주석으로 변수명, 설명 잘 적고 구현해주기!!

 

---

그래프, 너비우선탐색, 깊이우선탐색

 

dp가 질려서.. 요번주는 새로운 유형을 공부하기로 했다. 개념은 알고리즘 시간에 배웠지만 코드로 구현하려 했더니 헷갈렸다.

 

복습 노트

그래프를 표현하는 방법은 배열에 간선 정보를 저장하는 방법과, 인접 리스트로 저장하는 방법이 있다. 배열은 메모리를 많이 차지하지만(n*n) 노드가 연결되어 있는지 탐색하려고 할 때 효율적이다. 이에 반해 인접 리스트는 메모리는 배열보다 상대적으로 적지만(n+e) 노드가 연결되어 있는지 탐색하려고 할 때 시간이 많이 걸릴 수 있다.

 

먼저 노드를 방문했는지 저장하는 배열과, 그래프의 상태를 저장해 줄 인접리스트 or 배열을 선언한다.

이후, BFS는 큐로 구현하고, DFS는 스택이나 재귀함수로 구현한다.

 

1260 DFS와 BFS

 

#include<stdio.h>
#include<stack>
#include<queue>
using namespace std;
//n 정점개수 1000, e 간선개수 10000, v 탐색시작번호
//방문 여부를 체크할 배열, 간선의 정보를 저장할 배열 선언
int n, e, v;
int isvisit[1005];
int edge[1005][1005];
void bfs() {
	queue<int>q;
	int visitnodenum;
	q.push(v); isvisit[v] = 1;
	while (q.empty()==false) { 
		visitnodenum = q.front();
		printf("%d ", visitnodenum);
		for (int i = 1; i <= n; i++) {
			if (edge[visitnodenum][i] == 1 && isvisit[i] == 0) { //연결되어 있으면 큐에 넣어준다
				q.push(i); isvisit[i] = 1;
			}
		}
		q.pop();
	}
}
void dfs() {
	stack<int>s; 
	int visitnode; int neinode = 0;
	s.push(v);
	while (s.empty()==false) {
		visitnode = s.top(); 
		if (isvisit[visitnode] == 0) {
			printf("%d ", visitnode);  s.pop();
			for (int i = n; i >= 1; i--) {
				if (edge[visitnode][i] == 1 && isvisit[i] == 0) {
					s.push(i);
				}
			}
		}
		else {
			s.pop();
		}
		isvisit[visitnode] = 1;
	}
}
int main() {
	scanf("%d%d%d", &n, &e, &v);
	int a, b;
	for (int i = 1; i <= e; i++) {
		scanf("%d%d", &a, &b);
		edge[a][b] = 1;	edge[b][a] = 1; //양방향 edge이므로
	}
	dfs(); printf("\n"); 
	for (int i = 1; i <= n; i++) isvisit[i] = 0;
	bfs();
}

 

 

7576번 토마토

 

토마토

 

#include<stdio.h>
#include<queue>
#include<utility>
using namespace std;
int arr[1005][1005]; //토마토의 상태
queue<pair<int, int>> q;
int greentomato = 0;
int m, n; //상자의 가로, 세로

int pushqueue(pair<int,int> a) {
	//토마토 위치를 기준으로 상하좌우의 토마토를 익힌다.
	int sum = 0;
	int i = a.first; int j = a.second;
	if (arr[i - 1][j] == 0 && i-1 > 0) {
		arr[i - 1][j] = 1; q.push({ i - 1,j }); greentomato--; sum++;
	}
	if (arr[i + 1][j] == 0 && i+1 <= n) {
		arr[i + 1][j] = 1; q.push({ i + 1,j }); greentomato--; sum++;
	}
	if (arr[i][j - 1] == 0 && j-1 > 0) {
		arr[i][j - 1] = 1; q.push({ i,j - 1 }); greentomato--; sum++;
	}
	if (arr[i][j + 1] == 0 && j+1 <= m) {
		arr[i][j + 1] = 1; q.push({ i,j + 1 }); greentomato--; sum++;
	}
	return sum;
}

int search(int ot) {
	if (greentomato == 0) return 0;
	int tomatolocation; int day = 0;
	int sum = ot; int prevtoone = 0; //전날에 익은 토마토 수 => 이 수만큼 반복하면서 큐를 빼줌
	while (q.empty()==false) {
		while(sum > 0) {
			pair<int, int> tomatolocation = q.front();
			prevtoone += pushqueue(tomatolocation);
			q.pop();
			sum--;
		}
		sum = prevtoone; prevtoone = 0;
		day++;
	}
	if (greentomato > 0) return -1;
	return day - 1;
}

int main() {
	scanf("%d%d", &m, &n); int t;
	int onetomato = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &t);  
			if (t == 0) greentomato++;
			if (t == 1) {
				q.push({ i,j }); onetomato++;
			}
			arr[i][j] = t;
		}
	}
	int day = search(onetomato);
	printf("%d", day);
}

 

 

이게 왜 bfs인가? 그래프 탐색으로 푸는 문제인지 몰랐으면 구현 헷갈렸을듯

실제로 저번주에 dp인줄 알고 dp로 풀었다가 틀렸음..