작은시작

programmers.co.kr/learn/courses/30/lessons/42586#

코드 설명

큐를 이용하여 100을 넘길시 pop시킨다 (cnt를 통해 while문이용)

progresses 인덱스와 speeds 인덱스를 각각 어떻게 매번 더해줄까 생각하다가 그냥 큐에있는것을 하나씩 빼서 더한후 다시 push해주는 방법을 이용하였다.(단순..)

IDE를 쓰지 않으려는 연습을 계속하다보니까 core dumped가 너무 자주 발생한다...설계를 정확히하고 짧은 구문마다 디버깅을 해보자 

이번에도 while(q.front()>100) 만하고 큐가 비어있는 상황을 위에서 if문으로 그냥 해버리니까 당연히 while문 내에서 큐가 비는 상황이 발생한다....조심하자!

코드

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

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<int> q;
    for(int i=0;i<progresses.size();i++){
            q.push(progresses[i]);
            
        }
    
    while(1){
        int cnt=0;
        
        
        
    while(q.front()>=100 && !q.empty()){
        
            if(q.front()>=100) cnt++;
            q.pop();
            progresses.erase(progresses.begin());
            speeds.erase(speeds.begin());
            
        }
        
        
        
        
        for(int i=0;i<speeds.size();i++){
            int temp=q.front()+speeds[i];
            cout << q.front() << temp << endl;
            q.pop();
            q.push(temp);
        }
        
        
        if(cnt>0) answer.push_back(cnt);
        if(q.empty())break;
    }
    
    
    return answer;
}

C++ STL들 중 코딩테스트에서 자주 쓰이는 정렬 방식에 대해 복습 겸 정리

1) #include <algorithm> 에서 sort 사용

2) #include <queue> 헤더에서 priority_queue 사용시 우선순위 배정

결말부터 이야기하면,  1번 케이스(sort)는 첫번째 인자가 기준

                             2번 케이스(queue)에서는 두번째 인자가 기준이다.(따로 cmp 함수 생성 시)

pair에서 sort시 기본적으로 첫 번째 인자를 기준으로 정렬된다. 즉 두 번째 인자를 기준으로 정렬하고싶으면 비교 함수 cmp를 작성한다.

🤦‍♂️🤦‍♂️헷갈리지 말자!!

★greater <int>()는 sort() 시 내림차순

★greater <int>는 priority_queue에서 오름차순(즉, Min Heap)

1번 작성 예시 

2번 작성 예시 (pair second 기준 내림차순 정렬)

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        
            return b.second > a.second; //b가기준이므로 내림차순 정렬(두번째 pair인자기준)
        

        
    }

};

//main문
priority_queue<pair<int, int>,vector<pair<int,int>>, cmp >abc;

 서

sort 같은 경우 

sort(a.begin(), a.end()); -> 오름차순

sort(a.begin(), a.end(), greater<int>()); -> 내림차순  두가지 경우를 자주 쓰는것 같고,

우선순위 큐에서는 반대로 오름차순시 greater<int> 를 써주면되고 괄호는 빼준다.

참고 블로그 : coding-insider.tistory.com/entry/sort-%EC%82%AC%EC%9A%A9%EB%B2%95-priorityqueue%EC%97%90%EC%84%9C%EC%9D%98-sort-%EC%B0%A8%EC%9D%B4

www.acmicpc.net/problem/4963

코드 설명

BFS + visited배열을 이용하여 탐색하였다. 보통 4방향인데 대각선도 포함이므로 8방향으로 탐색하였다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N, M;
int map[51][51];
bool visited[51][51];
int dy[] = { 0,0,-1,-1,-1,1,1,1 };
int dx[] = { -1,1,-1,1,0,-1,1,0 };
int cnt;
vector<int> answer;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	visited[y][x] = true;
	q.push({ y,x });

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 8; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
			if (!visited[ny][nx] && map[ny][nx]==1) {
				q.push({ ny,nx });
				visited[ny][nx] = true;
			}

		}

	}


}
int main()
{
	while (1) {
	cin >> M >> N;
	if (N == 0 && M == 0) break;
	memset(map, 0, sizeof(map));
	memset(visited, false, sizeof(visited));
	cnt = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			cin >> map[y][x];


		}
	}
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (map[y][x] == 1 && !visited[y][x]) {
				cnt++;
				bfs(y, x);
			}
		}
	}
	answer.push_back(cnt);
	
	
	


	}
	for (int i = 0; i < answer.size(); i++) {
		cout << answer[i] << endl;
	}
	
	return 0;
}

www.acmicpc.net/problem/9012

코드 설명 

string배열과 stack을 이용하여 풀이하였다. 스택+ 제약조건을 걸어주면 금방 풀린다.

처음에 제약조건을 단순히 top과 들어오는 값과 다르면 pop으로 제거해줬는데 그러면 당연히 예외케이스가 생긴다

(2번case)

문제읽고 알고리즘생각하고 설계해본후 예외케이스 없는지 꼭 다시 확인해보자 !

코드

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int N;
int check[100];

int main() {
	cin >> N;
	string abc;
	for (int i = 0; i < N; i++) {
		cin >> abc;
		stack<char> st;
		for (int j = 0; j < abc.size(); j++) {
			if (!st.empty())
			{
				if (st.top() == '(' && abc[j] == ')')
					st.pop();
				else st.push(abc[j]);
			}
			else st.push(abc[j]);
		}
		if (st.empty()) check[i] = 1;
		else check[i] = 2;

		
	}
	for (int i = 0; i < N; i++) {
		if (check[i] == 1) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
	


	return 0;
}