정렬문제 아마도 내장함수를 사용하지 않는다면 n logN의 시간복잡도를 갖는 정렬로 풀어야한다.
문제 해결 방법
sort 내장함수 사용 ><
전체 코드
#include<vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> vec;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int input;
cin >> input;
vec.push_back(input);
}
sort(vec.begin(), vec.end());
for (int a : vec) {
cout << a << "\n";
}
}
#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll N, M;
vector<ll> cnt;
cin >> N >> M;
for (int i = 0; i < N; i++) {
ll input;
cin >> input;
cnt.push_back(input);
}
cnt.push_back(0); //인덱스 때문에 하나 추가
ll count = 0;
ll start = 0; ll end=0;
ll sum = cnt[start];
while (1) {
if (sum > M) { //합이 클때
sum -= cnt[start];
if (start == end) {
end++;
sum += cnt[end];
}
start++;
}
else if (sum < M) { //합이 적을때
end++;
sum += cnt[end];
}
else if (sum == M) {
count++;
sum += cnt[++end];
}
if (end == N) break;
}
cout << count;
}
#include<vector>
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll N, M;
vector<ll> cnt;
cin >> N ;
for (int i = 0; i < N; i++) {
ll input;
cin >> input;
cnt.push_back(input);
}
cnt.push_back(0); //인덱스 때문에 하나 추가
cin >> M;
ll count = 0;
ll start = 0; ll end=0;
ll sum = cnt[start];
while (1) {
if (sum > M) { //합이 클때
sum -= cnt[start];
count += N - end;
if (start == end) {
end++;
sum += cnt[end];
}
start++;
}
else if (sum <= M) { //합이 적을때
end++;
sum += cnt[end];
}
if (end == N) break;
}
cout << count;
}
이 문제는 섬과 섬 사이의 연결 관계를 파악해야 하는 그래프 관련 문제입니다. 이를 효율적으로 파악하기 위해 Union-Find 알고리즘을 사용합니다.
Union-Find는 그래프의 연결 요소를 식별하고 관리하기 위한 알고리즘입니다. Union-Find 알고리즘에서 'union' 연산은 두 집합을 하나로 합치고, 'find' 연산은 특정 원소가 어떤 집합에 속하는지를 찾는 데 사용됩니다.
본 문제에서는 다리 하나가 무너져 서로 왕복할 수 없는 섬들이 생겼습니다. 이때 두 섬을 다시 다리로 이어서 모든 섬이 왕복 가능하도록 해야 합니다. 이를 위해 먼저 주어진 섬 간 연결 정보를 이용해 각 섬의 부모 노드 정보를 업데이트합니다. 이렇게 하면 어떤 섬이 어떤 섬과 연결되어 있는지를 빠르게 알 수 있습니다.
Union-Find 알고리즘을 적용한 코드는 다음과 같습니다.
전체 코드
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int parent[1000001];
int getParent(int x) {
if (parent[x] == x) return x;
return parent[x] = getParent(parent[x]);
}
void unionParent(int a, int b) {
a = getParent(a);
b = getParent(b);
if (a > b) parent[a] = b;
else parent[b] = a;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin.tie(NULL);
int N;
cin >> N;
for (int i = 1; i <= N; i++) {
parent[i] = i;
}
for (int i = 1; i <= N - 2; i++) {
int a, b;
cin >> a >> b;
unionParent(a, b);
}
for (int i2 = 1; i2 <= N - 1; i2++) {
int A = i2;
for (int j = i2 + 1; j <= N; j++) {
int B = j;
A = getParent(A);
B = getParent(B);
if (A != B) {
cout << A << " " << B;
return 0;
}
}
}
return 0;
}
또한 포함된 5의 개수는 5부터 5의제곱수들을 차례대로 나눈 몫을 구하면 5의 개수를 구하는
함수를 만들 수 있다.
#전체 코드
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
//5가 들어간 개수를 찾는 함수
int findFive(int a) {
int count = 0;
for (int i = 5; i <= a; i *= 5) {
count += (a / i);
}
return count;
}
int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
//0의 개수는 5의 개수와 동일
//제곱이 나오는 경우는 숫자가 건너뛰어짐
int input;
cin >> input;
int left = 1;
int right = input*5;
int target = input;
int result = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (findFive(mid) == target) {
right = mid -1;
}
else if (findFive(mid) > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (findFive(left) == target) {
cout << left;
}
else {
cout << -1;
}
return 0;
}
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int arr[10001] = {
0,
}; // 좌표의 길이
int N; // 테스트 케이스
cin >> N;
int a, b;
for (int i = 0; i < N; i++) { // 입력된 작대기만큼 배열 활성화
cin >> a >> b;
for (int j = a; j < b; j++) { // a 에서 b 범위에 신경쓸것
arr[j] = 1;
}
}
int cnt = 0;
for (int k = 1; k <= 10001; k++) { // 작대기 길이 세주기
if (arr[k] == 1) {
cnt++;
}
}
cout << cnt;
}