AI(Artificial Intelligence)

  • 인간의 지능을 인공적으로 구현한 것

 

머신러닝

 

학습 종류

지도학습

  • 정답이 있는 데이터를 활용해 학습
비지도학습
  • 정답 라벨이 없는 데이테로 학습

 

  • 비슷한 특징 → 군집화 → 결과 예측
강화학습
  • 데이터 규정 X
  • 정답 X
  • 한 행동에 보상을 받으며 학습 → 보상 최대화

 

지도학습의 종류

회귀(regression)

  • 값을 예측하는 방식
  • 대표적으로, 선형 회귀(Linear Regression)가 있음.

분류(Classification)

  • True, False 판별
  • 로지스틱 회귀(Logistic Regression)가 대표적.

 


 

선형 회귀(Linear Regression)

 

단순 선형 회귀

y=wx+b(w=weight,b=biased)y = wx + b(w = weight, b = biased)

다중 선형 회귀

y=w1∗x1+w2∗x2+b(w1,w2=weight,b=biased)y = w1 * x1 + w2 * x2 + b(w1, w2 = weight, b = biased)

 

오차 계산법

  • 평균 제곱 오차(MSE, Mean Squared Error)
    • 차이를 제곱하여 평균 낸 값
    • MSE=1nΣ(y^−y)2(y^=PredictedValue)MSE = {1 \over n}\Sigma(\hat{y} - y)^2 (\hat{y} = Predicted Value)
  • 평균 절대값 오차(MAE, Mean Absolute Error)
    • 차이의 절대값을 평균낸 값
    • MAE=1nΣ∣y^−y∣(y^=PredictedValue)MAE = {1 \over n}\Sigma|\hat{y} - y| (\hat{y} = Predicted Value)

MSEMSE 그래프의 모양을 나타내면 다음과 같다.

오차가 가장 작은 지점의 기울기는 0, 따라서 미분값이 0인 지점의 W, b 의 값을 구하면 된다.

구하는 과정은 다음과 같다.

w 값을 구하는 과정

y^=wx+b,∂∂wMSE=1nΣ(wx+b−y)2=1nΣ2(wx+b−y)w=2nΣ(y^−y)w\hat{y} = wx + b, {\partial \over \partial w}MSE = {1 \over n}\Sigma(wx + b - y)^2 = {1 \over n}\Sigma2(wx + b - y)w = {2 \over n}\Sigma(\hat{y} - y)w
2×((y^−y)∗w).mean()2 \times ((\hat{y} - y)*w).mean()

같은 방법으로 b의 값을 구하면,

∂∂bMSE=2nΣ(y^−y){\partial \over \partial b}MSE = {2 \over n}\Sigma(\hat{y} - y)
2×(y^−y).mean()2 \times (\hat{y}-y).mean()

학습률(Learning Rate)

  • Learning Rate 가 너무 크면, 발산할 위험이 있고, 너무 작으면 제대로 학습되지 않을 수 있음.
  • 적절한 조율 필요
  • 단순 선형 회귀 경사하강법 code
    import numpy as np
    import matplotlib.pyplot as plt
    
    x_train = np.random.rand(100)
    y_train = 1000 * x_train + 500
    
    def plot_prediction(pred):
        plt.figure(figsize=(10, 10))
        plt.scatter(x_train, y_train)
        plt.scatter(x_train, pred)
        plt.draw()
        plt.pause(0.5)
        plt.close()
        
    
    w = np.random.uniform(-1, 1) # 초기값 설정(기울기)
    b = np.random.uniform(-1, 1) # 초기값 설정(y절편)
    
    learning_rate = 0.7
    
    for epoch in range(1000):
        y_pred = w * x_train + b
    
        error = np.abs(y_pred - y_train).mean()
        if error < 0.001:
            break
    
        w_grad = learning_rate * ((y_pred - y_train)*x_train).mean()
        b_grad = learning_rate * (y_pred - y_train).mean()
    
        w -= w_grad
        b -= b_grad
    
        if epoch % 10 == 0:
            print("[" + str(w) + "] [" + str(b) + "] [" + str(error) + "]")
            y_pred = w * x_train + b
            plot_prediction(y_pred)
    
    print("[" + str(w) + "] [" + str(b) + "] [" + str(error) + "]")
    
    #참고자료: https://s.sheenji.com/VCg2gL

 

  • 다중 선형 회귀 경사하강법 code
    import numpy as np
    import matplotlib.pyplot as plt
    
    x1_train = np.random.rand(100)
    x2_train = np.random.rand(100)
    y_train = 1000 * x1_train + 100 * x2_train + 500
        
    
    w1 = np.random.uniform(-1, 1) # 초기값 설정(기울기 1)
    w2 = np.random.uniform(-1, 1) # 초기값 설정(기울기 2)
    b = np.random.uniform(-1, 1) # 초기값 설정(y절편)
    
    learning_rate = 0.7
    
    for epoch in range(1000):
        y_pred = w1 * x1_train + w2 * x2_train + b
    
        error = np.abs(y_pred - y_train).mean()
        if error < 0.001:
            break
    
        w1_grad = learning_rate * ((y_pred - y_train)*x1_train).mean()
        w2_grad = learning_rate * ((y_pred - y_train)*x2_train).mean()
        b_grad = learning_rate * (y_pred - y_train).mean()
    
        w1 -= w1_grad
        w2 -= w2_grad
        b -= b_grad
    
        if epoch % 10 == 0:
            print("[" + str(w1) + "] [" + str(w2) + "] [" + str(b) + "] [" + str(error) + "]")
    
    print("[" + str(w1) + "] [" + str(w2) + "] [" + str(b) + "] [" + str(error) + "]")
    
    #참고자료: https://s.sheenji.com/VCg2gL

 

반응형

문제 링크: https://www.boj.kr/1182 

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 256MB 29396 13560 8585 44.296

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절대값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

예제 입력 1

5 0
-7 -3 -2 5 8

예제 출력 1

1

C++ code

#include <stdio.h>
#include <vector>
using namespace std;

int n, s, ans;
vector<int> a;

void dfs(int idx, int sum)
{
	if (idx == n)
    {
    	if (sum == s)
        	ans++;
        return;
    }
    
    dfs (idx + 1, sum + a[idx]);
    dfs (idx + 1, sum);
}

int main (void)
{
	scanf("%d %d", &n, &s);
    
    for (int i = 0; i < n; i++)
    {
    	int temp;
        scanf("%d", &temp);
        a.push_back(temp);
    }
    
    dfs(0, 0);
    if (!s)
    	ans--;
    printf("%d", ans);
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1162 - 도로포장  (0) 2020.11.07
1105 - 팔  (0) 2020.11.06
1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02

문제 링크: https://www.boj.kr/1162 

 

1162번: 도로포장

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128MB 5133 659 456 22.072%

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 k개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로릉 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 반드시 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1

C++ code

#include <stdio.h>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const ll inf = LLONG_MAX;

typedef struct
{
	vector<int> to, cost;
}Road;

typedef struct
{
	ll city, cost, kk;
}pq_elem;

bool operator<(pq_elem x, pq_elem y)
{
	return x.cost > y.cost;
}

int main(void)
{
	int n, m, k, size;
    vector<Road> road;
    vector<vector<ll>> ans;
    priority_queue<pq_elem, vector<pq_elem>> pq;
    
    scanf("%d %d %d", &n, &m, &k);
    road.resize(n+1);
    ans.resize(n+1, vector<ll>(k+1, inf));
    
    for (int i = 0; i < m; i++)
    {
    	int s, e, c;
        scanf("%d %d %d", &s, &e, &c);
        road[s].to.push_back(e);
        road[s].cost.push_back(c);
        road[e].to.push_back(s);
        road[e].cost.push_back(c);
    }
    
    pq.push(pq_elem{1, 0, 0});
    ans[1][0] = 0;
    
    while (pq.size())
    {
    	ll city = pq.top().city, cost = pq.top().cost, kk = pq.top().kk;
        pq.pop();
        
        size = road[city].to.size();
        for (int i = 0; i < size; i++)
        {
        	pq_elem temp;
            temp.city = road[city].to[i];
            temp.cost = cost + road[city].cost[i];
            temp.kk = kk;
            
            if (ans[temp.city][temp.kk] > temp.cost)
            {
            	ans[temp.city][temp.kk] = temp.cost;
                pq.push(temp);
            }
            
            temp.cost = cost;
            temp.kk++;
            if (temp.kk <= k && ans[temp.city][temp.kk] > temp.cost)
            {
            	ans[temp.city][temp.kk] = temp.cost;
                pq.push(temp);
            }
        }
    }
    
    ll minans = ans[n][0];
    for (int i = 1; i <= k; i++)
    	minans = min(minans, ans[n][i]);
    
    printf("%lld\n", minans);
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1182 - 부분수열의 합  (0) 2020.11.08
1105 - 팔  (0) 2020.11.06
1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02

문제 링크: https://www.boj.kr/1105 

 

1105번: 팔

첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 512MB 1754 582 483 34.426%

문제

L과 R이 주어진다. 이때, L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 수에 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 L보다 크거나 같고, R보다 작거나 같은 자연수 중에 8이 가장 적게 들어있는 8의 개수를 구하는 프로그램을 작성하시오.

예제 입력 1

8808 8880

예제 출력 1

2

C++ code

#include <iostream>
using namespace std;

int main (void)
{
	string str1, str2;
    cin >> str1 >> str2;
    
    if (str1.size() != str2.size())
    	cout << 0;
    else
    {
    	int size = str1.size(), ans = 0;
        
        for (int i = 0; i < size; i++)
        {
        	if (str1[i] != str2[i])
            	break;
            if (str1[i] == '8')
            	ans++;
        }
        cout << ans;
    }
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1182 - 부분수열의 합  (0) 2020.11.08
1162 - 도로포장  (0) 2020.11.07
1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02

문제 링크: https://www.boj.kr/1081 

 

1081번: 합

첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128MB 2016 390 328 36.203%

문제

L보다 크거나 같고, U보다 작거나 같은 모드 정수의 각 자리의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 L과 U이 주어진다. U은 0보다 크거나 같고, 2,000,000,000보다 작거나 같은 정수이고, L은 0보다 크거나 같고, U보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

10 14

예제 출력 1

15

C++ code

#include <stdio.h>
#include <vector>
using namespace std;
typedef long long ll;

ll f(int x)
{
	vector<int> a(10, 0);
    
    int left = 1;
    int right = x;
    int base = 1;
    
    while (left <= right)
    {
    	while(right % 10 != 9 && left <= right)
        {
        	int temp = right;
            while (temp)
            {
            	a[temp % 10] += base;
                temp /= 10;
            }
            right--;
        }
        
        if (right < left)
        	break;
        
        while (left % 10 != 0 && left <= right)
        {
        	int tmp = left;
            while (tmp)
            {
            	a[tmp % 10] += base;
                tmp /= 10;
            }
            left++;
        }
        
        left /= 10;
        right /= 10;
        
        for (int i = 0; i < 10; i++)
        	a[i] += (right - left + 1) * base;
        
        base *= 10;
    }
    
    ll ret = 0;
    for (int i = 0; i <= 9; i++)
    	ret += (a[i]*i);
    
    return ret;
}

int main(void)
{
	int lower, upper;
    scanf("%d %d", &lower, &upper);
    
    printf("%lld", f(upper)-f(lower-1));
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1162 - 도로포장  (0) 2020.11.07
1105 - 팔  (0) 2020.11.06
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02
1043 - 거짓말  (0) 2020.11.01

문제 링크: https://www.boj.kr/1074 

 

1074번: Z

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원

www.acmicpc.net

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

C++ code

#include <stdio.h>
int n, r, c;

int pow2 (int k)
{
	int 1 << k;
}

int solve (int n, int x, int y)
{
	if (n == 1)
    {
    	return 2 * x + y;
    }
    
    if (x < pow2(n - 1))
    {
        if (y < pow2(n - 1)) // 1번째 영역
        	return solve(n - 1, x, y);
        else // 2번째 영역
        	return solve(n - 1, x, y - pow2(n - 1)) + pow2(2 * (n - 1));
    }
    else
    {
    	if (y < pow2(n - 1)) // 3번째 영역
        	return solve(n - 1, x - pow2(n - 1), y) + 2 * pow2(2 * (n - 1));
        else // 4번째 영역
        	return solve(n - 1, x - pow2(n - 1), y - pow2(n - 1)) + 3 * pow2(2 * (n - 1));
    }
}

int main (void)
{
	scanf("%d %d %d", &n, &r, &c);
    
    int res = solve(n, r, c);
    
    printf("%d", res);
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1105 - 팔  (0) 2020.11.06
1081 - 합  (0) 2020.11.05
1059 - 수2  (0) 2020.11.02
1043 - 거짓말  (0) 2020.11.01
1038 - 감소하는 수  (0) 2020.10.31

문제 링크: https://www.boj.kr/1059 

 

1059번: 수2

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128MB 3860 929 827 26.520%

문제

Lucky Set이란 정수의 집합이다.

구간 [A,B]란 A보다 크거나 같고, B보다 작거나 같은 모든 정수가 있는 구간이다. 이때, A와 B는 모두 양수이고, B는 A보다 크다.

구간 [A,B]가 Unlucky가 되기 위해선 구간에 속한 모든 정수가 Lucky Set에 없어야 한다.

Lucky Set과 N이 주어질 때, N을 포함하는 Unlucky 구간의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 Lucky Set에 포함된 숫자의 개수 L이 주어진다. 둘째 줄에는 L개의 수가 주어진다. 이 수는 1,000보다 작거나 같은 자연수이고, L은 50보다 작거나 같은 자연수이다. 그리고 중복되지 않는다. 마지막 줄에는 N이 주어진다. N은 Lucky Set에서 가장 큰 수보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

4
1 7 14 10
2

예제 출력 1

4

C++ code

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

int main(void)
{
	int n, left = 0, right, m;
    vector<int> Lucky;
    scanf("%d", &n);
    right = n - 1;
    
    for (int i = 0; i < n; i++)
    {
    	int temp;
        scanf("%d", &temp);
    }
    
    scanf("%d", &m);
    
    sort(Lucky.begin(), Lucky.end());
    
    while(left <= right)
    {
    	int mid = (left + right) / 2;
        
        if (Lucky[mid] < m)
        	left = mid + 1;
        else if (Lucky[mid] > m)
        	right = mid - 1;
        else
        {
        	printf("0");
            return 0;
        }
    }
    int temp = Lucky[left];
    left = Lucky[right];
    right = temp;
    
    printf("%d", (m - left - 1) * (right - m) + (right - m - 1));
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1043 - 거짓말  (0) 2020.11.01
1038 - 감소하는 수  (0) 2020.10.31
1010 - 다리놓기  (0) 2020.10.30

문제 링크: https://www.boj.kr/1043 

 

1043번: 거짓말

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128MB 4702 1310 1096 32.037%

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수와 각 파티마다 오는 사람의 수는 모두 0 이상 50 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

4 3
0
2 1 2
1 3
3 2 3 4

예제 출력 1

3

C++ code

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> g;
vector<bool> check;

int find(int x)
{
	if(g[x]==x)
		return x;
	else
	{
		g[x]=find(g[x]);
		return g[x];
	}
}

void group(int x, int y)
{
	int findx=find(x);
	int findy=find(y);
	
	if(check[findx])
		g[findy]=g[findx];
	else
		g[findx]=g[findy];
}

int main(void)
{
	int n,m, size, temp, cnt=0;
	vector<int> party;
	scanf("%d %d", &n, &m);
	check.resize(n+1);
	
	for(int i=0; i<=n; i++)
		g.push_back(i);
	
	scanf("%d", &size);
	if(size==0)
	{
		printf("%d", m);
		return 0;
	}
	
	for(int i=0; i<size; i++)
	{
		scanf("%d", &temp);
		check[temp]=true;
	}
	
	for(int i=0; i<m; i++)
	{
		scanf("%d", &size);
		
		scanf("%d", &temp);
		party.push_back(temp);
		
		for(int j=1; j<size; j++)
		{
			scanf("%d", &temp);
			group(party[i], temp);
		}
	}
	
	for(int i=0; i<m; i++)
		if(!check[find(party[i])])
			cnt++;
	
	printf("%d", cnt);
	return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02
1038 - 감소하는 수  (0) 2020.10.31
1010 - 다리놓기  (0) 2020.10.30

문제 링크: https://www.boj.kr/1038

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1초 512MB 11353 2941 2363 30.237%

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 1

18

예제 출력 1

42

c++ code

#include <stdio.h>
#include <queue>
using namespace std;
typedef long long ll;

int main(void)
{
    int n, idx=1;
    ll temp = 0;
    queue<ll> q;
    scanf("%d", &n);

    for(int i=1; i<=9; i++)
        q.push(i);

    while(idx<=n)
    {
        if(q.empty())
        {
            temp=-1;
            break;
        }
        temp=q.front();
        q.pop();
        int m = temp%10;
        for(int i=0; i<m; i++)
            q.push(temp*10+i);

        idx++;
    }

    printf("%lld", temp);
    return 0;
}
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02
1043 - 거짓말  (0) 2020.11.01
1010 - 다리놓기  (0) 2020.10.30

문제 링크: https://www.boj.kr/1010

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 128 MB 27084 12647 10206 48.429%

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예제 입력 1

3
2 2
1 5
13 29

예제 출력 1

1
5
67863915
  • code

    #include <stdio.h>
    #include <vector>
    using namespace std;
    
    vector<vector<int> > a;
    
    int t, l, r;
    
    int main(void)
    {
        scanf("%d", &t);
    
        a.resize(31);
        a[0].push_back(1);
        a[1].push_back(1);
        a[1].push_back(1);
    
        for(int i=2; i<=30; i++)
        {
            a[i].push_back(1);
            a[i].push_back(i);
    
            for(int j=2; j<i; j++)
            {
                a[i].push_back(a[i-1][j-1]+a[i-1][j]);
            }
            a[i].push_back(1);
        }
        for(int i=0; i<t; i++)
        {
            scanf("%d %d", &l, &r);
            printf("%d\n", a[r][l]);
        }
    
        return 0;
    }
반응형

'알고리즘 > 백준' 카테고리의 다른 글

1081 - 합  (0) 2020.11.05
1074 - Z  (0) 2020.11.03
1059 - 수2  (0) 2020.11.02
1043 - 거짓말  (0) 2020.11.01
1038 - 감소하는 수  (0) 2020.10.31

아래 두 과정을 모두 한 후, 이 글에 따라 진행하자

2019/08/06 - [프로그램 설치방법/vscode] - visual studio code 설치

 

visual studio code 설치

https://code.visualstudio.com/ Visual Studio Code - Code Editing. Redefined Visual Studio Code is a code editor redefined and optimized for building and debugging modern web and cloud applications...

sheenji.tistory.com

2019/08/06 - [프로그램 설치방법/vscode] - c/c++ 설치하기 (mingw-w64)

 

c/c++ 설치하기 (mingw-w64)

MinGW-w64 - for 32 and 64 bit Windows Download MinGW-w64 - for 32 and 64 bit Windows for free. A complete runtime environment for gcc. The mingw-w64 project is a complete runtime environment for gcc..

sheenji.tistory.com


  • c/c++ 검색 후 설치

  • mingw-w64 컴파일러 설정
  • ctrl + k, o를 눌러 파일 열기를 한다
  • 혹은 파일 → 폴더 열기를 눌러 vscode에서 작업할 폴더를 생성한다.

  • mingw-w64 컴파일러 설정
  • ctrl + k, o 를 눌러 파일 열기를 한다
  • 혹은 파일 → 폴더 열기를 눌러 vscode에서 작업할 폴더를 생성한다.

  • Ctrl + Shift + p 를 눌러 찾기 모드를 연다.
  • C/C++:Edit Configurations(JSON) 선택

  • c_cpp_properties.json 생성됨

  • compilerPath를 앞 글에서 컴파일러를 깐 위치로 변경해 준다.

  • 빌드 및 디버깅
  • Ctrl + Shift + p 를 통해 Tasks: Configure task를 선택한다.

  • Create Tasks.json file 옵션을 선택한다.

  • others를 선택한다.

  • tasks.json 파일이 생성된다.

  • 다음과 같이 정의한다.
{ // 한 파일에서 컴파일, 여기에선 a.exe로 진행한다.
    "version": "2.0.0",
    "tasks": [
        {
            "label": "compile",
            "type": "shell",
            "command": "g++",
            "args": [
                "-g",
                "${file}"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ],
    
}
{ // 한 파일당, 같은 이름으로 만들어서 컴파일, ex) a.cpp 실행 -> 같은 폴더에서 a.exe 만들어짐
    "version": "2.0.0",
    "tasks": [
        {
            "label": "compile",
            "type": "shell",
            "command": "g++",
            "args": [
                "-g",
                "${file}",
                "-o",
                "${fileDirname}\\${fileBasenameNoExtension}.exe"
            ],
            "group": {
                "kind": "build",
                "isDefault": true
            }
        }
    ],
    
}
  • 디버깅
  • 먼저 디버깅을 설정하기 전에 helloworld.cpp 파일을 만들어 준다.

  • 디버깅 단축키인 F5 버튼을 누르면 다음과 같이 나온다.

  • 디버깅 단축키인 F5 버튼을 누르면 다음과 같이 나온다.

  • 생성된 launch.json 파일을 다음과 같이 수정해 준다.
  •  
{
    // IntelliSense를 사용하여 가능한 특성에 대해 알아보세요.
    // 기존 특성에 대한 설명을 보려면 가리킵니다.
    // 자세한 내용을 보려면 https://go.microsoft.com/fwlink/?linkid=830387을(를) 방문하세요.
    "version": "0.2.0",
    "configurations": [
        
        
        {
            "name": "(gdb) Launch",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/a.exe", // 위에서 첫번째 과정 사용시 이 부분 사용
            // "program": "${fileDirname}\\${fileBasenameNoExtension}.exe", // 위에서 두번째 과정 사용시 이 부분 사용
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb",
            "miDebuggerPath": "C:/mingw-w64/x86_64-8.1.0-win32-seh-rt_v6-rev0/mingw64/bin/gdb.exe",
            "setupCommands": [
                {
                    "description": "Enable pretty-printing for gdb",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                }
            ],
            "preLaunchTask": "compile"
        }
    ]
}
반응형

'프로그램 설치방법 > vscode' 카테고리의 다른 글

c/c++ 설치하기 (mingw-w64)  (0) 2019.08.06
visual studio code 설치  (0) 2019.08.06

https://s.sheenji.com/AYOo9A

 

MinGW-w64 - for 32 and 64 bit Windows Files

A complete runtime environment for gcc

https://s.sheenji.com/AYOo9A

2020.10.19 update) 위 사진 대신, 아래의 방법으로 다운로드

아래로 스크롤 하면 나옴

  • 나중 설정을 위해 program files 아래가 아닌 c밑에 바로 설치해준다.

  • 나중 설정을 위해 program files 아래가 아닌 c밑에 바로 설치해준다.

  • 나중 설정을 위해 program files 아래가 아닌 c밑에 바로 설치해준다.

  • 변수 설정 확인하기

  • gcc --version으로 환경 변수 등록 확인

반응형

'프로그램 설치방법 > vscode' 카테고리의 다른 글

c/c++ 설치(vscode)  (0) 2020.10.30
visual studio code 설치  (0) 2019.08.06
반응형

'프로그램 설치방법 > vscode' 카테고리의 다른 글

c/c++ 설치(vscode)  (0) 2020.10.30
c/c++ 설치하기 (mingw-w64)  (0) 2019.08.06

+ Recent posts