BOJ C++ 정렬 1920, 이분탐색 10989 2417, 수학 11966 9506

[정렬과 이분탐색]

1920 수 찾기 

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

int find(int num) {
	int s = 0, e = n - 1;
	
	while (s <= e) {
		int mid = (s + e) / 2;
		if (v[mid] == num) return 1;
		
		if (v[mid] < num) {
			s = mid + 1;
		}
		else e = mid - 1;
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a; cin >> a;
		v.push_back(a);
	}
	//int m; cin >> m;
	//for (int i = 0; i < m; i++) {
	//	int a; cin >> a;
	//	auto it = find(v.begin(), v.end(), a);
	//	if (it == v.end()) cout << 0 << "\n";
	//	else cout << 1 << "\n"; //it - v.begin()
	//}
	//시간초과

	sort(v.begin(), v.end());
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int a; cin >> a;
		cout << find(a) << "\n";
	}
}

 

10989 수 정렬하기3

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

int a[10003];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        a[x]++; //인덱스 증가
    }

    for (int i = 1; i <= 10000; i++) {
        if (a[i] != 0) {
            if (a[i] == 1) cout << i << "\n";
            else {
                for (int j = 0; j < a[i]; j++) cout << i << "\n"; //여러 개 있으면 여러 개 출력
            }
        }
    }
}

 

[수학]

11966 2의 제곱인가?

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

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	long long a = 1;
	for (int i = 0; i < 30; i++) {
		a *= 2;
		if (a == n) {
			cout << 1;
			return 0;
		}
	}
	cout<< 0;
}

 

9506 약수들의 합

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

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	while (1) {
		int n;
		cin >> n;
		if (n == -1) return 0;
		vector<int> v;

		long long sum = 0;
		for (int i = 1; i < n; i++) { //약수 구하기
			if (n % i == 0) {
				sum += i;
				v.push_back(i);
			}
		}

		if (sum == n) {
			cout << n << " = ";
			for (int i = 0; i < v.size(); i++) {
				if (i == v.size() - 1) cout << v[i];
				else cout << v[i] << " + ";
			}
		}
		else {
			cout << n << " is NOT perfect.";
		}
		cout << "\n";
	}
}

 

 

2417 정수제곱근

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath> //이거 없으면 백준에선 컴파일 에러
using namespace std;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long n; cin >> n;
	
	long long s = 0, e = sqrt(n), mid = 0;
	while (s <= e) {
		mid = (s + e) / 2;
		if (mid >= sqrt(n)) e = mid - 1;
		else s = mid + 1;
	}
	if (mid * mid == n) cout << mid;
	else cout << mid + 1;
}