c++ 4주차 알고리즘스터디 숙제

• A - 평범한 배낭
• B - 연구소
• C - 암기왕
• D - 스타트 택시
• E - 상근이의 여행
• F - 감소하는 수

1204 기분 개좋음 왜냐? 3문제나 풀었기 때문ㅜ 야호

평범한 배낭은 저 배낭 알고리즘 공부할 때 설명했으니까 pass 

 

E. 상근이의 여행 9372번 (www.acmicpc.net/problem/9372)

이제 유니온파인드나 크루스칼 알고리즘은 나의 favorite 가뿐하다구욧

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

//vector<pair<int, int>> airplane;
vector<int> parent;

int getparent(int x) {
	if (parent[x] == x) return x;
	return  parent[x] = getparent(parent[x]);
}

void unionparents(int x, int y) {
	x = getparent(x);
	y = getparent(y);
	if (x < y) parent[y] = x;
	else parent[x] = y;
}

int find(int x, int y) {
	if (getparent(x) == getparent(y)) return 1;
	else return 0;
}


int main() {
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++) {
		int n, m;
		cin >> n >> m; //국가수 , 비행기 종류
		//부모 배열 초기화
		parent.resize(n+1);

		for (int j = 1; j <= n; j++) {
			parent[j] = j;
		}

		int cnt = 0;
		for (int j = 0; j < m; j++) {
			int depart, arrive;
			cin >> depart >> arrive;
			if (!find(parent[depart], parent[arrive])) {
				cnt++;
				unionparents(parent[depart], parent[arrive]);
			}
		}
		cout << cnt <<endl;
	}
}

 

• C - 암기왕  

보자마자 인덱스에 대해서 이진탐색을 쓰면 될 거 같다고 생각이 났다.

나 자신 너무 대견하다,,,,, BUT 수첩2를 기준으로 수첩1을 찾는건데 반대로 풀어서 한참 애먹음;;

바보같은 녀석,,,, 게다가 시간초과 떠서 CIN , COUT , ENDL 다 바꿔줌 ㅠ힝 그니까 해결됨 우하하하하ㅏㅎ

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

vector<int> note1;
vector<int> note2;

int main() {
	int testcase;
	scanf("%d" , &testcase);
	for (int i = 0; i < testcase; i++) {
		int n, m;
		
		scanf("%d", &n);
		note1.resize(n + 1);
		for (int j = 1; j <= n; j++) scanf("%d", &note1[j]);
		sort(note1.begin(), note1.end());
		
		scanf("%d", &m);
		note2.resize(m + 1);
		for (int j = 1; j <= m; j++) scanf("%d", &note2[j]);

		for (int j = 1; j <= m; j++) {
			int ans = 0;
			int mid , start = 1, end = n;

			while (end >= start) {
				mid = (start + end) / 2;
				if (note2[j] == note1[mid]) {
					ans = 1;
					break;
				}
				else if (note2[j] < note1[mid]) end = mid - 1;
				else start = mid + 1;		
			}
			printf("%d\n", ans);
		}
	}
}

 

와 이 이후로 나머지 3문제는 어려워서 풀지 못했다,,,, 이틀을 고민해도 안되다니,,,, 

좀 더 레벨업하면 그 때 무조건 ㄷㅏ시 풀자,,,