코딩생존기

https://www.acmicpc.net/problem/3009

세점을 가지고 축에 평행한 직사각형을 만들기 위한 네번째 점을 찾아야한다. 2번나온 x,y좌표를 제외하고 한번만 나온 x,y값을 사용하여 좌표를 완성해주자

나는 모든값을 받고  2번이상나왔는지 if문을 통해 확인했지만 더 효율적으로 푸는 방법은 모든 값을 받고 XOR 연산을 통해 X,Y값을 얻어내는 것이 가장 효율적이다 .

정답코드1

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int main() {
    vector<pair<int, int>> vp(3); // 세 점을 받으므로 크기 3으로 설정

    for (int i = 0; i < 3; i++) {
        cin >> vp[i].first >> vp[i].second; // 세 점의 좌표 입력
    }

    int x, y;

    // X 좌표 구하기
    if (vp[0].first == vp[1].first) {
        x = vp[2].first;
    }
    else if (vp[0].first == vp[2].first) {
        x = vp[1].first;
    }
    else {
        x = vp[0].first;
    }

    // Y 좌표 구하기
    if (vp[0].second == vp[1].second) {
        y = vp[2].second;
    }
    else if (vp[0].second == vp[2].second) {
        y = vp[1].second;
    }
    else {
        y = vp[0].second;
    }

    cout << x << " " << y << endl; // 네 번째 점 출력

    return 0;
}

정답코드2(XOR연산사용)

#include <iostream>

using namespace std;

int main() {
    int x1, y1, x2, y2, x3, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    // XOR 연산을 통해 x 좌표와 y 좌표를 구한다
    int x4 = x1 ^ x2 ^ x3;
    int y4 = y1 ^ y2 ^ y3;

    cout << x4 << " " << y4 << endl;

    return 0;
}

https://www.acmicpc.net/problem/1085

직사각형의 경계셔선까지 최소거리를 구하면 되는 문제이다. 이떄, 원점에서 시작되는 직선이 가까운지 아니라면 (w,h)

에서 시작되는 직선이 가까운지 구하면 된다. 

정답코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int x, y, w, h;

    cin >> x >> y >> w >> h;

    // 각각의 경계선까지의 거리
    int distance_to_left = x;         // (x, y)에서 왼쪽 경계선 (0, y)까지의 거리
    int distance_to_right = w - x;    // (x, y)에서 오른쪽 경계선 (w, y)까지의 거리
    int distance_to_bottom = y;       // (x, y)에서 아래쪽 경계선 (x, 0)까지의 거리
    int distance_to_top = h - y;      // (x, y)에서 위쪽 경계선 (x, h)까지의 거리

    // 최솟값 구하기
    int min_value = min({ distance_to_left, distance_to_right, distance_to_bottom, distance_to_top });

    cout << min_value << endl;

    return 0;
}

https://www.acmicpc.net/problem/11653

소인수분해를 하는 문제이다. 문제자체는 쉽기때문에 일단 풀고 어떻게 해야 시간복잡도를 줄일지 고민해보았다. 

일단 먼저 풀어본 방식은 순회를 하면서 나누어떨어지는게 있으면 벡터에 저장하고 전체를 순회했다면 벡터를

순회하면서 출력해주게 했다.

정답코드1

#include "iostream"
#include "vector"
#include "cma"

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	if (n == 1) cout << "" << endl;

	for (int i = 2; i <= n;)
	{
		if (n % i == 0)
		{
			n /= i;
			v.push_back(i);
		}
		else
		{
			i++;
		}
	}

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


	return 0;
}

2번째 방식은 어떤 수 n이 a * b로 표현될 때, 적어도 하나의 인수는 sqrt(n) 이하인 것을 사용하여 주어진 수의 제곱근까지만 순회를 하는 방식으로 구현하였다.

정답코드2

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

int main()
{
	int n;
	vector<int> v;
	cin >> n;

	if (n == 1) cout << "" << endl;

	for (int i = 2; i <= sqrt(n); i++) {
		while (n % i == 0) {
			n /= i;
			v.push_back(i);
		}
	}

	// 남아있는 소수 `n`이 있다면 그것도 출력
	if (n > 1) {
		v.push_back(n);
	}

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


	return 0;
}

3번째 방식은 에타토스테네스의 체를 이용하는 방식이다. 일단 범위내의 소수를 모두 구해두고 구한 소수를 통해 소인수분해를 하는 방식이다. 

정답코드3

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 에라토스테네스의 체를 이용하여 범위 내의 모든 소수를 구함
vector<int> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= max; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * 2; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "" << endl;
        return 0;
    }

    // 소수 리스트를 미리 구함
    int max_prime = sqrt(n);  // 소수를 구할 최대 범위 설정
    vector<int> primes = sieve(max_prime);

    // 소인수 분해 수행
    vector<int> factors;
    for (int prime : primes) {
        while (n % prime == 0) {
            factors.push_back(prime);
            n /= prime;
        }
    }

    // 남아있는 소수 n이 있으면 그것도 출력
    if (n > 1) {
        factors.push_back(n);
    }

    // 결과 출력
    for (int factor : factors) {
        cout << factor << endl;
    }

    return 0;
}

https://www.acmicpc.net/problem/2581

이것또한 에라토스테네스의 체 방식을 사용하여 최대값까지의 소수를 구한 뒤에 m~n 까지 순회하면서 소수라면 벡터에 저장하고 sum도 같이 추가하면서 최종적인 최솟값과 합을 출력해주면된다. 만약 벡터의 크기가 0이라면 -1을 출력해준다.

정답코드

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

// 에라토스테네스의 체로 소수 목록을 생성
vector<bool> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님

    for (int i = 2; i * i <= max; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return is_prime;
}

int main()
{
    int m, n, sum = 0;
    vector<int> sumv;
    cin >> m >> n;

    vector<bool> is_prime = sieve(n);

    for (int i = m; i <= n; i++)
    {
        if (is_prime[i])
        {
            sumv.push_back(i);
            sum += i;
        }
    }

    if (sumv.size() > 0) cout << sum << "\n" << sumv[0] << endl;
    else cout << -1 << endl;

    return 0;

}

https://www.acmicpc.net/problem/1978

소수를 찾는 문제이다. 나는 n이 100이하이고 n의 수도 1000이하라서 반복문을 순회하면서 소수인지 판별했으나

에라토스테네스의 체를 통해 소수를 미리 구해두고 확인하는 방식이 훨씬 효율적이다. 

밑은 에라토스테네스의 체를 설명한 그림이다. 소수를 찾고 그 배수는 모두 소수에서 제외시키는 방식으로 소수가 아닌것을 제외하면 된다.

정답코드 

#include "iostream"
#include "vector"
#include "cmath"

using namespace std;

bool isValue(int n)
{
	if (n == 1) return false;
	
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0) return false;
	}

	return true;
}

vector<int> v;
int main()
{
	int n, cnt = 0;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int j;
		cin >> j;
		v.push_back(j);
	}

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

	cout << cnt << endl;
	return 0;
}

시간복잡도를 줄인 버전

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// 에라토스테네스의 체로 소수 목록을 생성
vector<bool> sieve(int max) {
    vector<bool> is_prime(max + 1, true);
    is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님

    for (int i = 2; i * i <= max; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return is_prime;
}

int main() {
    int n, count = 0;
    cin >> n;
    
    vector<int> numbers(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }

    // 1000까지의 소수를 구하기 위해 에라토스테네스의 체 실행
    vector<bool> is_prime = sieve(1000);

    // 입력된 숫자들에 대해 소수인지 확인
    for (int i = 0; i < n; i++) {
        if (is_prime[numbers[i]]) {
            count++;
        }
    }

    cout << count << endl;
    return 0;
}

https://www.acmicpc.net/problem/9506

약수를 구한 다음 약수의 총합이 본래의 수와 같으면 기존의 수를 저장한 벡터를 순서대로 출력해주면 된다.

시간복잡도를 줄이기 위해 약수가 대칭인 점을 이용하여 제곱근까지만 약수를 구해주자

정답코드

#include "iostream"
#include "vector"
#include "cmath"
#include "algorithm"

using namespace std;

int main()
{
	int n;
	while (true)
	{
		cin >> n;
		if (n == -1) return 0;

		vector<int> v;
		int sum = 0;
		for (int i = 1; i <= sqrt(n); i++)
		{
			if (n % i == 0)
			{
				v.push_back(i);
				if (i != 1 && i != n / i)  //n / i과 다를 경우
				{
					v.push_back(n / i); // 약수 n/i 추가
				}
				sum += i;  // 약수의 합에 추가
				if (i != 1 && i != n / i)
				{
					sum += n / i; // n / i가 약수일 경우 합에 추가
				}
			}
		}
		sort(v.begin(), v.end());
		// 완전수 판별
		if (sum == n)
		{
			cout << n << " = ";
			for (int i = 0; i < v.size(); i++)
			{
				cout << v[i];
				if (i != v.size() - 1)
				{
					cout << " + ";
				}
			}
			cout << endl;
		}
		else
		{
			cout << n << " is NOT perfect." << endl;
		}
	}
}

https://www.acmicpc.net/problem/2869

원래는 반복문을 통해 얼마나 걸리는지 계산하려고 했으나 시간제한을 보면 0.25초이고 최대가 10억이라 무조건 시간초과

가 뜬다 그렇기 때문에 일반화된 식을 통해 기간을 계산해야한다. 

이때 먼저 낮에 A미터를 올라가고 밤에 B미터를 미끄러지기 때문에 일단 낮 밤을 합쳤을 때는 V-A 만큼을 가야하고 그 다음에는 A만큼만 가면 되기때문에 결국에는 V-A / A-B 를 계산한다음 낮에 한번 더 가야하니 1을 더해주면 답이 된다.

정답코드

#include "iostream"
#include "cmath"

using namespace std;

int main()
{
	int a, b, v;

	cin >> a >> b >> v;
	
	int days = ceil((double)(v - a) / (a - b)) + 1;

	cout << days;
	return 0;
}

https://www.acmicpc.net/problem/2941

단어가 몇개의 크로아티아 알파벳으로 이루어져있는 지 확인해야하는 문제이다. 

이때 주어진 입력은 변경된 알파벳이기 때문에 받아준 단어를 순회하면서 변경된 문자라면 하나의 크로아티아 알파벳

으로 인식하여 횟수를 추가해주고 아니라면 그냥 한글자 단위만큼만 횟수를 추가해줘서 전체 횟수를 반환해주면 된다.

정답코드

#include "iostream"
#include "string"
#include "vector"

using namespace std;

int countCro(string s)
{
	// 크로아티아 알파벳 목록 정의
	vector<string> croatianAlphabets = { "c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z=" };

	int cnt = 0;

	for (int i = 0; i < s.length();)
	{
		bool matched = false;

		for (string alpha : croatianAlphabets)
		{
			if (s.substr(i, alpha.length()) == alpha)
			{
				cnt++;
				i+=alpha.length();
				matched=true;
				break;
			}
		}

		if (!matched)
		{
			i++;
			cnt++;
		}
	}

	return cnt;
}

int main()
{
	string s;

	cin >> s;

	int result = countCro(s);
	cout << result << endl;
}

https://www.acmicpc.net/problem/25206

주어진 학점과 등급을 통해 전공 평점을 계산하면 되는 것이다. 

나는 이때 vector와 pair 자료형을 통해 모든 학점과 등급을 저장하고 이를 순회하면서 전공 평점을 계산해줬다 이때 

고정소수점방식으로 6자리까지만 출력되도록 했다.

정답코드

#include "iostream"
#include "string"
#include "vector"
#include "utility"

using namespace std;

vector<pair<double, string>> scores;

// 학점 계산 함수
double ch(string s)
{
    if (s == "A+")
        return 4.5;
    else if (s == "A0")
        return 4.0;
    else if (s == "B+")
        return 3.5;
    else if (s == "B0")
        return 3.0;
    else if (s == "C+")
        return 2.5;
    else if (s == "C0")
        return 2.0;
    else if (s == "D+")
        return 1.5;
    else if (s == "D0")
        return 1.0;
    else if (s == "F")
        return 0.0;
    else
        return 0.0;  // Default case
}

int main()
{
    string course_name, grade;
    double credit;
    for (int i = 0; i < 20; i++)
    {
        cin >> course_name >> credit >> grade;
        scores.push_back(make_pair(credit, grade));  // 학점과 등급을 벡터에 저장
    }

    double total_score = 0.0;
    double total_credits = 0.0;

    for (int i = 0; i < scores.size(); i++) {
        if (scores[i].second == "P") continue;  // P 등급인 과목은 계산에서 제외
        total_score += (scores[i].first * ch(scores[i].second));  // 학점 * 과목평점
        total_credits += scores[i].first;  // 총 학점
    }

    // 전공평점 계산
    double gpa = total_score / total_credits;
    //cout << fixed; // 고정 소수점 형식
    //cout.precision(6); // 소수점 아래 6자리까지 출력
    cout << gpa << endl;

    return 0;
}

https://www.acmicpc.net/problem/1316

그룹단어가 몇개인지 찾는 문제이다. 같은 문자가 연속해서 나오다가 끊기고 다시 나오면 그룹문자가 아니기 때문에 map을 통해 갯수를 세고 이게 전에 나왔던 개수이면 false를 반환 만약 순회가 끝나면 그룹문자이기 때문에 true를 반환해주자.

정답코드

#include "iostream"
#include "string"
#include "map"
using namespace std;

bool isGroup(string s)
{
	map<char, int> smap;
	char prechar = s[0];
	smap[prechar]++;
	for (int i = 1; i <s.length(); i++) \
	{
		if (s[i-1] != s[i] && smap[s[i]] > 0) return false;
		else smap[s[i]]++;
	}
	return true;
}
int main()
{
	int n, cnt = 0;
	string s;
	
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> s;
		if (isGroup(s)) cnt++;
	}

	cout << cnt;
	return 0;
}