minjgziii

📍 문제

📍 풀이

BFS 활용

- 사람 관계는 꼭 양뱡향으로 리스트에 삽입해 주어야 함

- 이중 for문을 돌면서 BFS를 실행

   - 이때, 시작과 끝 사람이 같은 경우 (즉, 같은 사람일 경우) pass

   - 한 사람이 다른 사람까지 가는 단계를 count에 저장

   - 한 사람이 모든 다른 사람의 단계를 합쳐 케빈 베이컨 수 구함 (temp)

📍 코드

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

int N, M;
int A, B;
bool visited[101];
vector<int> vec[101];
int cnt = 0;

void BFS(int start, int end) {
	queue<pair<int, int>> q;
	q.push({ start, 0 });
	visited[start] = true;

	while (!q.empty()) {
		int cur = q.front().first;
		int num = q.front().second;
		q.pop();

		if (cur == end) {
			cnt = num;
			break;
		}

		for (int i{ 0 }; i < vec[cur].size(); i++) {
			if (!visited[vec[cur][i]]) {
				q.push({ vec[cur][i], num + 1 });
				visited[vec[cur][i]] = true;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i{ 0 }; i < M; i++) {
		cin >> A >> B;

		vec[A].push_back(B);
		vec[B].push_back(A);
	}

	int min = 98765432;
	int ans = 0;

	for (int i{ 1 }; i <= N; i++) {
		int temp = 0;
		for (int j{ 1 }; j <= N; j++) {
			memset(visited, false, sizeof(visited));

			if (i != j) {
				BFS(i, j);
				temp += cnt;
				cnt = 0;
			}
		}
		if (min > temp) {
			min = temp;
			ans = i;
		}
	}

	cout << ans;
}

📍 문제

📍 풀이

BFS 활용

- 각 지역의 높이를 입력 받으면서 가장 높은 지역의 값을 maxHeight 변수에 저장해 놓는다. (가장 높은 지역의 높이보다 큰 비가 내리면 어차피 다 잠기기 때문에 똑같기 때문에 maxHeight까지만 반복하면 됨)

- x = 0 (*이때, x = 1부터 돌게 되면 틀린다!! 이거 때문에 계속 틀림)부터 앞에서 구한 maxHeight 까지 반복하면서 BFS를 돌린다. 이때 당연히 아직 방문하지 않았고, 안전한 구역인 곳만 BFS를 실행한다. (안전한 구역 => 현재 x 값보다 큰 구역) 

*x = 0로 돌릴 때 틀리는 이유는 문제에 나와있는 이 조건 때문인 듯하다.

📍 코드

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

int N;
int arr[101][101];
bool visited[101][101];
int xDir[4] = { 1,-1,0,0 };
int yDir[4] = { 0,0,1,-1 };

void BFS(int i,int j, int bound) {
	queue<pair<int, int>> q;
	q.push({ i,j });
	visited[i][j] = true;

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

		for (int i{ 0 }; i < 4; i++) {
			int nowX = x + xDir[i];
			int nowY = y + yDir[i];

			if (nowX < 0 || nowY < 0 || nowX >= N || nowY >= N) {
				continue;
			}
			if (visited[nowX][nowY]) {
				continue;
			}
			// 물에 잠긴 경우 (bound이하)
			if (arr[nowX][nowY] <= bound) {
				continue;
			}

			q.push({ nowX,nowY });
			visited[nowX][nowY] = true;
		}
	}
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	int maxHeight = -1;
	int max = 0;

	for (int i{ 0 }; i < N; i++) {
		for (int j{ 0 }; j < N; j++) {
			cin >> arr[i][j];
			if (maxHeight < arr[i][j]) {
				maxHeight = arr[i][j];
			}
		}
	}

	for (int x{ 0 }; x <= maxHeight; x++) {
		memset(visited, false, sizeof(visited));
		int ans = 0;

		for (int i{ 0 }; i < N; i++) {
			for (int j{ 0 }; j < N; j++) {
				// 방문하지 않았고 안전한 구역
				if (!visited[i][j] && arr[i][j] > x) {
					BFS(i, j, x);
					ans++;
				}
			}
		}

		if (max < ans) {
			max = ans;
		}
	}

	cout << max;
}

📍 문제

📍 풀이

- 이분탐색 활용

start 값은 1,

end 값은 예산 요청에서 가장 큰 값

으로 설정했다.

예산 배정 과정

for문 안에서 sum 변수를 만들어

start와 end값을 기준으로 생성된

1) mid값보다 작으면 : 그대로 더하고,

2) mid값보다 크면 : mid값을 더했다.

문제에서 제시한 예시를 보면 쉽게 파악할 수 있다.

각 지방의 예산 요청이 (120, 110, 140, 150) 일 때,

상한액을 127로 잡았을 때, (이때의 mid 값이 127인 것이다.)

위의 요청들에 대해 (120, 110, 127, 127) 을 배정해 주었다. 

📍 코드

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

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

	int N = 0; // 지방의 수
	int money = 0; // 배정된 예산
	int max = 0; // 총 예산
	
	int answer = 0; // 답

	cin >> N;

	vector<int> v;

	// 각 지방의 예산요청 입력 받기
	for (int i{ 0 }; i < N; i++) {
		cin >> money;
		v.push_back(money);
	}

	cin >> max;

	sort(v.begin(), v.end());

	int start = 1; 
	int end = v.back();


	while (start <= end) {
		int mid = (start + end) / 2;
		int sum = 0;

		for (int i{ 0 }; i < v.size(); i++ ) {
			if (v[i] <= mid) {
				sum += v[i];
			}
			else {
				sum += mid;
			}
		}

		// 예산을 초과하는 경우
		if (sum > max) {
			end = mid - 1;
		}

		// 예산을 초과하지 않는 경우
		else {
			if (mid <= end) {
				answer = mid;
			}
			start = mid + 1;
		}
	}

	cout << answer;
}

💡 우선순위 큐

• 오름차순과 내림차순과 같은 정렬 기능이 들어간 queue
• 우선순위 큐는 각 원소들이 우선순위를 갖는다.
• priority_queue는 기본적으로 내림차순으로 정렬
• priority_queue<자료형, 구현체, 비교연산자>
• 비교 연산자에는 less<자료형>, greater<자료형>이 있음
  • less : 내림차순 ( 큰 -> 작은)
  • greater : 오름차순 ( 작은 -> 큰)

오름차순 정렬을 위해서는 다음과 같이 정렬해야 한다.

priority_queue<int, vector<int>, greater<int>> q; // 오름차순

아래의 두 가지 코드는 같다.

priority_queue<int> q;
priority_queue<int, vector<int>, less<int>> q;

operator < 를 사용

💡 우선순위 큐 구현하는 방법

• 배열
• 링크드 리스트
• 힙

힙으로 우선순위 큐를 구현하는데 가장 효과적이고, STL 또한 priority_queue는 make_heap 기반으로 구현되어 있다.

💡 make_heap

C++ heap의 헤더파일은 <algorithm>에 정의되어 있다.

STL에서도, make_heap은 힙이라는 container를 제공해 주는 것이 아니라 사용자의 vector를 인자로 받아 힙 구조로 변환 시켜 준다.

vector를 make_heap을 통해 힙을 구성하면, 우선순위가 가장 높은 데이터는 첫번째 Index에 위치하게 된다. 그리고, 나머지 요소는 heap에 맞는 구조를 띄게 된다.

데이터 우선순위를 재정의 해 주지 않으면 기본적으로 max_heap으로 구성된다.

요약하자면,

• make_heap : comp는 생략하면 기본적으로 operator< 함수를 사용하여 max_heap을 구성
• priority_queue : 내부적으로 make_heap을 사용하는데 이 container에도 comp를 생략하면 less Class를 사용해 make_heap의 인자로 operator < 를 넘겨주는 것과 동일한 역할을 수행하게 된다.

🧐 참고 사이트

📍 문제

📍 우선순위 큐 (priority_queue)

• 오름차순과 내림차순과 같은 정렬 기능이 들어간 queue
• 우선순위 큐는 각 원소들이 우선순위를 갖는다.
• priority_queue는 기본적으로 내림차순으로 정렬
• priority_queue<자료형, 구현체, 비교연산자>
• 비교 연산자에는 less<자료형>, greater<자료형>이 있음
  • less : 내림차순 ( 큰 -> 작은)
  • greater : 오름차순 ( 작은 -> 큰)

오름차순 정렬을 위해서는 다음과 같이 정렬해야 한다.

priority_queue<int, vector<int>, greater<int>> q; // 오름차순

📍 코드

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

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

	int N = 0;
	int x = 0;

	priority_queue<int, vector<int>, greater<int>> q;

	cin >> N;

	for (int i{ 0 }; i < N; i++) {
		cin >> x;
		if (x == 0) {
			if (q.size() == 0) {
				cout << 0 << "\n";
			}
			else {
				cout << q.top() << "\n";
				q.pop();
			}
		}
		else {
			q.push(x);
		}
	}
}

📍 문제

📍 풀이

입출력 예의 첫 번째인 [6, 10, 2]를 보자.

예상했겠지만 이 문제를 integer로 정렬하면 답은 1062 가 된다. => 틀림!

즉, integer로 정렬하면 올바를 답을 구할 수 없다.

따라서, string으로 변환 후, 비교해야 한다.

먼저 입력 받은 numbers 들을 string으로 변환하여 vector에 삽입한다.그리고 나서 정렬을 할 건데, (여기서 sort와 사용자 정의 compare 함수를 사용하였다.)

compare 함수에서는for문을 돌며

a[i]와 b[i]가 같다면  a+b를 int로 바꾼 것과 b+a를 int로 바꾼 것 중 더 큰 수를 가지는 문자열을 결정한다.(예를 들어 "3" 과 "30"을 비교할 때, 0번째 인덱스에서 두 문자열이 동일한 숫자를 가지고 있다. 따라서 stoi("3"+"30") 와 stoi("30"+"3") 를 비교하면 330이 303보다 크다. )

그렇지 않다면, (a[i]와 b[i]가 같지 않다면)

a[i]와 b[i]를 비교하여 더 큰 숫자를 가진 문자열을 결정한다.

그런데, 이렇게 코드를 쓰고 제출하면 테스트케이스 11에서만 실패가 뜬다.

🖐 여기서 잠깐!

이 문제에는 예외 처리 해야 하는 케이스가 하나 있다.

모든 numbers가 0일 때 ( [0, 0, 0, 0] 의 경우, "0000"으로 출력됨)

따라서, answer의 첫 원소가 "0"인 경우, "0"을 return하는 예외 처리를 해 주어야 한다.

📍 코드

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

bool compare(string a, string b) {
    bool answer = true;

    int mx = max(a.size(), b.size());

    for (int i{ 0 }; i < mx; i++) {
        if (int(a[i]) == int(b[i])) {
            answer = stoi(a + b) > stoi(b + a);
            break;
        }
        else {
            answer = a[i] > b[i];
            break;
        }
    }
    
    return answer;
}

string solution(vector<int> numbers) {
    string answer = "";
    vector<string> v;

    for (int i{ 0 }; i < numbers.size(); i++) {
        v.push_back(to_string(numbers[i]));
    }

    sort(v.begin(), v.end(),compare);

    if (v[0] == "0") {
        return "0";
    }

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

    return answer;
}

📍 문제

📍 풀이

자료구조 deque 사용

deque에 입력 받은 원소들 삽입

첫 번째 for문에서

먼저,

deque의 첫번째 원소를 변수 a에 저장 (a에 저장된 값이 현재 계산할 주식 price)

deque의 첫번째 원소 pop

그리고 두 번째 for문에서

1) a (현재 비교를 할 price)보다 deque의 i번째 원소보다 크거나 같으면 cnt++ 를 해 준다 (가격이 떨어지지 않은 경우)

2) 그렇지 않으면, 가격이 떨어졌으므로, cnt++를 해 주고 break로 반복문을 빠져나간다

여기서 cnt++를 해 주는 이유는 [ 1, 2, 3, 2, 3 ] 의 예에서 3->2 에서 가격이 떨어지지 않은 시간은 1이다.

🤔 여기서 잠깐!

이 문제는 prices의 길이는 10,000 이하이다.

따라서 보통의 문제에서는 이중 for문을 돌리게 되면, O(N^2)으로 시간초과가 나게 된다.

하지만 특이하게도 이 문제에서는 시간초과가 나지 않는다.

O(N)의 시간복잡도로 푸는 방법에 대해서도 생각해 보아야 한다. => 이후 글 참고~!

📍 코드

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

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    deque<int> d;

    for (int i{ 0 }; i < prices.size(); i++) {
        d.push_back(prices[i]);
    }

    for (int i{ 0 }; i < prices.size(); i++) {
        int cnt = 0;
        int a = d.front();
        d.erase(d.begin());

        for (int i{ 0 }; i < d.size(); i++) {
            if (a <= d[i]) {
                cnt++;
            }
            else {
                cnt++;
                break;
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

📍 문제

📍 풀이

• 자료구조 스택 활용
• '(' 를 담을 stack<char> open 선언

 올바른 괄호가 아닌 조건 2가지 

 1)  ')' 가 들어왔는데 스택이 비어있는 경우

 2)  마지막에 스택에 데이터가 남아있는 경우

입력 받은 string s의 길이만큼 반복문을 돌며

▶️ '(' 일 때 => 스택에 push

▶️ ')' 일 때 => 스택에서 pop

    이 때,  1)  스택이 비어있어서 pop을 하지 못하는 경우 => 올바르지 않은 괄호

반복문을 다 돌고도,  2)  마지막에 스택에 데이터가 남아있는 경우 => 올바르지 않은 괄호

📍 코드

#include <string>
#include <stack>
#include <iostream>
using namespace std;

bool solution(string s)
{
    bool answer = true;

    stack<char> open;

    for (int i{ 0 }; i < s.size(); i++) {
        // '(' 일 때
        if (s[i] == '(') {
            open.push(s[i]);
        }
        // ')' 일 때
        else {
            // ')'일 때, pop을 하려고 하는데 스택이 비어있다 -> 올바르지 않은 괄호
            if (open.size() == 0) {
                return false;
            }
            else {
                open.pop();
            }
        }
    }

    // 마지막에 스택에 데이터가 남아있다 -> 올바르지 않은 괄호
    if (open.size() != 0) {
        answer = false;
    }

    return answer;
}