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

+ Recent posts