Codetesing의 코딩공부

정수론에 관한 문제이다.

새로운 이론은 없으며 다만 연산해야 하는 제곱수 N을 log(N)으로 줄여 연산하였다.

MOD는 제곱에 대하여 결합과 교환법칙이 성립하므로 쉽게 풀 수 있는 문제이다.

#include<iostream>

#define MOD 1000000007

using namespace std;

int main(int argc, char** argv)
{
	long long N, K, P;

	cin >> K >> P >> N;

	N *= 10;
	int cur = 1;
	
	while(1) {
		if(N == 1)
			break;
		
		if(N % 2 == 0)
		{
			P = P * P;
			P %= MOD;
			N /= 2;
		}
		else
		{
			K *= P;
			K %= MOD;
			N--;
		}
	}

	long long out = K * P;
	out %= MOD;

	cout << out << '\n';

	return 0;
}

정답률 28%의 문제이다.

가장 긴 증가 부분순열을 구하는 문제이다.

DP를 사용하여 푸는 흔한 문제이며 어렵지 않게 풀었다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N; cin >> N;
	vector<int> arr(N, 0);
	vector<int> cnt(N, 1);

	for(int i = 0; i < N; i++)
		cin >> arr[i];

	for(int i = 0; i < N; i++)
	{
		for(int j = i + 1; j < N; j++)
			if(arr[i] < arr[j] && cnt[j] <= cnt[i])
			{
				cnt[j] = cnt[i] + 1;
			}
	}

	int max_val = *max_element(cnt.begin(), cnt.end());

	cout << max_val << '\n';

	return 0;
}

정답률 68%로 쉬운 문제에 속한다.

반복문을 이용하여 풀었으며 구간별로 합하여 평균을 나타내면 된다.

#include<iostream>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K; cin >> N >> K;
	vector<int> arr(N, 0);
	for(int i = 0; i < N; i++)
		cin >> arr[i];

	int A, B;
	for(int i = 0; i < K; i++)
	{
		cin >> A >> B;

		float out = 0;
		for(int j = A - 1; j < B; j++)
			out += arr[j];
		out /= (float)(B - A + 1);

		printf("%.2f\n", out);
	}

	return 0;
}

딱히 어려운것 없이 조건에 따라 시뮬레이션 돌리는 문제같다.

다만 문자열의 괄호 처리를 알맞게 해야 하며 조건을 잘 설정해야 한다.

#include <iostream>

#include <string>
#include <vector>

using namespace std;

bool IS_RIGHT(string s) {
    if(s[0] == ')')
        return false;
    
    int cnt = 1;
    for(int i = 1; i < s.size(); i++)
    {
        if(s[i] == ')')
            cnt--;
        else
            cnt++;
        if(cnt < 0)
            return false;
    }
    
    if(cnt == 0)
        return true;
    else
        return false;
}

string DFS(string s) {
    string u, v;
    
    if(s == "")
        return "";
    
    int cnt = 0;
    
    for(int i = 0; i < s.size(); i++)
    {
        if(s[i] == '(')
            cnt++;
        else
            cnt--;
        
        if(cnt == 0)
        {    
            u = s.substr(0, i + 1);
            if(i == s.size() - 1)
                v = "";
            else
                v = s.substr(i + 1, s.size());
            
            if(IS_RIGHT(u))
                return u + DFS(v);
            else
            {
                string temp = "";
                for(int j = 1; j < u.size() - 1; j++)
                {
                    if(u[j] == ')')
                        temp += '(';
                    else
                        temp += ')';
                }
                
                return '(' + DFS(v) + ')' + temp;
            }
        }
    }
}

string solution(string p) {
    string answer = "";
    
    if(p.size() == 0)
        return "";
    
    answer = DFS(p);
    
    return answer;
}

동일 테이블에서 비교하는 문제이다.

각 테이블의 이름을 정해주어 WHERE로 풀었다.

SELECT DISTINCT A.CART_ID FROM CART_PRODUCTS A, CART_PRODUCTS B
 WHERE A.CART_ID = B.CART_ID AND 
 ((A.NAME = 'Milk' AND B.NAME = 'Yogurt') OR (B.NAME = 'Milk' AND A.NAME = 'Yogurt')) 
 ORDER BY cart_id;