개발 블로그

1. [What is Machine Learning?]

<머신러닝의 정의>

1. Arthur Samuel

- 컴퓨터가 명시적(explict) 프로그램 없이도 스스로 학습할 수 있는 능력을 연구하는 학문 분야.

- 체커 게임

2. Tom Mitchell

- Well-posed learning problem (학습 과제)

- 프로그램이 일정 수준의 작업 성능(P)을 가지고 작업(T)을 수행한다고 했을 때, 경험(E)이 증가함에 따라 작업(T)를 수행하는 성능(P)이 향상될 수 있다.이 때 프로그램이 경험(E)으로부터 학습(learn)을 했다고 표현한다.

- 체커스에서 경험(E)는 ‘같은 게임을 수만 번 반복하는 과정’, 작업(T)는 체커 게임을 수행하는 행위, 작업 성능(P)는 프로그램이 다음 판을 새로운 상대로 했을 때 그 판을 이길 확률(probability).

<머신 러닝 알고리즘>

1. 지도 학습(Supervised learning) : 작업 수행 방법을 컴퓨터에게 가르침

2. 비지도 학습(Unsupervised learning) : 컴퓨터가 스스로 학습하도록 유도

3. Others : 강화 학습(Reinforcement Learning) , 추천 시스템(Recommender system)

2. [Supervised Learning]

<Supervised Learning >

: 알고리즘에 “정답이 포함 된” 데이터 집합을 줌. 즉, 데이터 집합 안의 모든 예시에 대해 알고리즘이 예측했으면 하는 정답이 우리에게 주어지는 것.

Q1 . 주택 가격을 어떻게 예측할까?

• 각 집 마다 정확한 가격이 명시 된 데이터 집합을 줌.
• 데이터를 통과하는 직선 혹은 이차함수를 그려 결과를 예측해 볼 수 있다.

=> 회귀 문제(regression problem)라고도 할 수 있다.

• 회귀 : 연속 된 값을 가진 결과를 예측하는 것.
• 집 가격은 스칼라 값이지만 연속된 값을 가진 숫자로 가정하자.

Q2 . 종양의 크기가 주어졌을 때 그 종양이 악성일 가능성은?

=> 분류 문제(classification problem)라고도 할 수 있다.

• 분류 : 불연속적인 결과값을 예측하는 것.
• ex) 종양의 크기가 주어졌을 때 어떤 종류의 종양인지. 이때 종양의 종류는 이산적이다.

<머신러닝의 궁극적인 목표>

: 주어진 어떠한 특성에 따라 결과 값을 도출하는 것.

• 주어진 특성은 매우 다양할 수밖에 없다.
• 이때 특성이 무한하다면? 메모리 해결 방안은?
• Support Vector Machine 알고리즘 이용.

3. [Unsupervised Learning]

Unsupervised Learning에 주어진 데이터 집합의 특징 :

• 데이터가 어떠한 의미를 갖는지 우리는 알 수 없음.
• 데이터 집합의 예시에 대해 정답을 제시해주지 않음.
• 데이터 집합에서 어떠한 구조를 찾을 수 있는지 분석하는 것.
• 데이터 집합이 클러스터(cluster)로 나뉨.
• 클러스터링 알고리즘(Clustering Alogrithm) 에 데이터 집합을 주어 Unspervised Learning을 시킴.

<클러스터링 알고리즘의 이용>

• 구글 뉴스 : 수천 가지의 새로운 기사들을 조사하여 연관성 있는 기사들끼리 묶어 링크시킨다.
• 유전학적 자료 : 각 사람의 유전자 발현 정도를 분석하여 사람들을 서로 다른 타입으로 묶을 수 있다.(클러스터링 함)
• Organize computing clusters : 수많은 컴퓨터 중 어떠한 기기들끼리 같이 사용되는지 클러스터링하여 효율을 높인다.
• Social network analysis : 어떠한 그룹이 사용자에게 적절한 친구 그룹인지 추천해준다.
• Market segmentation : 수많은 고객들의 정보를 분석하여 세분화된 시장을 찾아내고 각 고객에 맞게 시장에서 판매와 영업을 효율적으로 진행할 수 있다.
• Astronomical data analysis : 은하계 생성과 관련된 이론 도출.

<Cocktail party problem>

Q 1. 칵테일 파티 효과란?

A 1. 칵테일 파티 효과(cocktail party effect)는 파티의 참석자들이 시끄러운 주변 소음이 있는 방에 있음에도 불구하고 대화자와의 이야기를 선택적으로 집중하여 잘 받아들이는 현상에서 유래한 말이다. (출처 — 위키백과)

Q 2. 칵테일 파티 문제란?

A 2. 관심있는 소리만 선택적으로 받아들이는게 로봇이나 인공지능 기술에서는 불가능한 것.

Q 3. 노래와 사람의 음성을 동시에 마이크에 녹음한 후 cocktail party algorithm을 이용하여 둘을 분리할 수 있을까?

A 3. [W,s,v] = svd((repmat(sum(x.*x,1)size(x,1),1).*x)*x’);

=> 주어진 음성을 유사성에 따라 클러스터링.

• svd함수 : 특이값 분해 (Singular value decomposition)의 약자.
• Octave or Matlab 은 머신러닝 알고리즘 구현에 용이함. => 이를 이용해서 먼저 머신러닝 알고리즘의 프로토타입을 만들어 본 후 c++ or java 로 구현해 보는것이 좋다.

문제 링크 : www.acmicpc.net/problem/6588

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

접근 방법

소수구하기 문제(nanyoungkim.tistory.com/32) 에서 나왔던 "에라토스테네스의 체"를 이용하여 n의 최대값까지 소수를 구한다.

a는 3부터 시작해서 홀수이기 때문에 2씩 키워가면서 a, b 가 소수인지 체크하여 조건에 맞게 출력한다.

이때 주의할 점은 시간초과 문제였다. 아래의 코드를 작성하니 시간초과 문제가 해결되었다. 

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

또한 메인함수의 for 문에서 a는 3부터 n/2까지 하면 더 시간을 단축시킬 수 있다.

#include <iostream>

using namespace std;


#define MAX 1000000

int primeArr[MAX] = {0};

void primeChk(){
    
    for(int i = 2; i*i<=MAX; i++){
        
        if(primeArr[i]==0){
        
            for(int j = i*i; j<=MAX; j+=i){
                primeArr[j] = 1;
            }
        }
        
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    primeChk();

    
    while(1){
        
        cin >> n;
        if(n==0){
            break;
        }
                   
        bool chk = false;
        
        for(int a = 3; a<= n; a+=2){
           // int b = n - a;
            if(primeArr[a]==0 && primeArr[n-a]==0) {    //a가
                cout << n << " = " << a << " + " << n-a << "\n";
                chk = true;
                break;
            }
        }
        if(!chk){
            cout << "Goldbach's conjecture is wrong.\n";
        }
    }
  
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/3085

문제

상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다.

가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.

사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 보드의 크기 N이 주어진다. (3 ≤ N ≤ 50)

다음 N개 줄에는 보드에 채워져 있는 사탕의 색상이 주어진다. 빨간색은 C, 파란색은 P, 초록색은 Z, 노란색은 Y로 주어진다.

사탕의 색이 다른 인접한 두 칸이 존재하는 입력만 주어진다.

출력

첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다.

접근 방법

처음에는 DFS 처럼 상하좌우로 swap 하고 사탕 최대 개수를 행, 열에 대해 각각 count 하는 것인줄 알았다.

그러나 DFS가 아니라 가로에 대해 한 번 swap 하고 행, 열 각각 사탕 최대 개수를 세고 이를 반복한다.

그 다음 세로에 대해 한 번 swap 하고 행, 열에 대해 사탕 최대 개수를 센다.

즉,

1) 가로

map[0][0] 와 map[0][1] swap -> countRow() -> countCol() -> map[0][1] 과 map[0][2] swap -> countRow() -> countCol()......

2) 세로

map[0][0] 와 map[1][0] swap -> countRow() -> countCol() -> map[1][0] 과 map[2][0] swap -> countRow() -> countCol()......

과 같은 순서로 탐색하면 된다.

주의할 점은 cnt를 초기화해주는 곳이었다.

사탕은 같은 행 또는 열에 있어야 먹을 수 있으므로 행 또는 열이 바뀔 때마다 cnt를 1로 초기화 해줘야 한다.

#include <iostream>
#include <algorithm>

using namespace std;

char map[50][50];


int N;
int resMax = 0;

void countRow(){

    for(int i = 0; i<N; i++){
        int cnt=1;

        for(int j = 0; j<N-1; j++){
            if(map[i][j]==map[i][j+1]){
                cnt++;
            }
            else{
                resMax=max(resMax,cnt);
                cnt=1;
            }
        }
        resMax=max(resMax,cnt);
    }
}

void countCol(){
    
    for(int j = 0; j<N; j++){
        int cnt=1;

        for(int i = 0; i<N-1; i++){
            if(map[i][j]==map[i+1][j]){
                cnt++;
            }
            else{
            resMax=max(resMax,cnt);
            cnt=1;
            }
        }
        resMax=max(resMax,cnt);
    }
}

void swapFunc(int r,int c,int nr,int nc){
    int tmp = map[r][c];
    map[r][c] = map[nr][nc];
    map[nr][nc] = tmp;
}


void solve(int r, int c){
    countRow();	    //행 검사

    countCol();		    //열검사
}



int main(){
    
    cin >> N;
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N; j++){
            cin >> map[i][j];
        }
    }
    
    
    for(int i = 0; i<N; i++){
        for(int j = 0; j<N-1; j++){
            swapFunc(i,j,i,j+1);
            solve(i,j);             //가로 스왑
            swapFunc(i,j,i,j+1);
        }
    }
    
    
   for(int j = 0; j<N; j++){
       for(int i = 0; i<N-1; i++){
           swapFunc(i,j,i+1,j);
           solve(i,j);               //세로 스왑
           swapFunc(i,j,i+1,j);
       }
   }

    cout<<resMax<<"\n";
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/9095

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

접근 방법

DFS 구조의 재귀로 풀었다. 

다른 보통의 문제들과 다른 점은 중복이 허용되기 때문에 visited[] 을 사용하지 않고 풀어야한다는 점이다.

테스트 케이스가 반복되니 테스트케이스 마지막에는 변수들을 초기화해주는 것을 잊지 말자.

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

using namespace std;

int n;
int num[3] = {1,2,3};
int cnt = 0;
vector<int> choiceVec;


void sumFunc(int sum){
    
    if(n<sum) return;
    
    if(n==sum){
        cnt++;
        return;
    }
    
    for(int i = 0; i<3; i++){
        
        sum+=num[i];
        choiceVec.push_back(num[i]);
        
        sumFunc(sum);
        choiceVec.pop_back();
        sum-=num[i];
        
    }
    
}


int main(){
    
    int T;
    cin >> T;
    for(int tc = 0; tc<T; tc++){
    
        cin >>n;
        sumFunc(0);
        cout << cnt << "\n";
        
        cnt = 0;
        choiceVec.clear();
        
    }
    
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/2309

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

접근 방법

재귀를 이용해서 풀었다. DFS와 같은 구조이다. 

9명 중 7명을 뽑아서 toPick이 0이 되었을 때 키를 모두 더해서 키의 합이 100이면 chk를 true로 바꾸서 탐색을 멈췄다.

문제에서 조건을 만족하는 경우 중 아무거나 출력하라 했으니 sum=100이 되는 경우를 찾았을 때 진행을 멈추는 것이 효과적일 것이다.

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

using namespace std;


vector<int> heightVec;
bool isVisited[9] = {0};
bool chk = false;
vector<int> ansVec;
int ans = 0;

void Func(int sum, int toPick){
    
    if(toPick==0){
        
        if(sum==100){
            chk = true;
            return;
        }
  
    }
    
    for(int i = 0; i<9; i++){
        
        if(isVisited[i]==0){
            isVisited[i] = 1;
            ansVec.push_back(heightVec[i]);
            sum+=heightVec[i];
        
            Func(sum, toPick-1);
            if(chk){ break;}
            
            sum-=heightVec[i];
            ansVec.pop_back();
            isVisited[i] = 0;
        }
        
    }
    
}


int main(){
    
    
    for(int i = 0; i<9; i++){
        int h;
        cin>>h;
        heightVec.push_back(h);
    }
    
    sort(heightVec.begin(), heightVec.end());
    
    Func(0, 7);
    
    for(int i = 0; i<7; i++){
        cout << ansVec[i] << "\n";
    }
    
    
    return 0;
}

문제링크 : www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

접근 방식 1 

페르마의 정리 이용ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95#%ED%8E%98%EB%A5%B4%EB%A7%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

gcd(a,p)  = 1 , a<p and p가 소수이면 a^p-1 (mod p) 는 1과 합동이다.

그러나 a = 8, p = 9일때, 8^8 = 16777216이어서 이를 9로 나눈 나머지는 1인데, 9는 소수가 아니므로 예외가 발생한다.

#include <iostream>
#include <cmath>

using namespace std;

int gcd(int p, int a){
    
    int c;
    while(a!=0){
        c = p%a;
        p = a;
        a = c;
    }
    return p;
}

int main(){
    
    int M, N;
    cin >> M >> N;

    for(int p = M; p<=N; p++){

        for(int a = 2; a<p; a++){

            if(gcd(p,a) == 1){

                int chk =((int)pow(a,p-1)) % p;
                if(chk == 1){
                    cout << "a: " << a << " /p: " << p << endl;
                    break;
                }
            }
        }
    }

    return 0;
}

접근 방법 2

Miller-Rabin Primality Test 를 이용해보자. 

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;


bool Test(int a, int n){
    
    
    int u=0, t=0;
    int k = n-1;
    int tmp = k;
    if(k%2 != 0){   //k홀수 즉 n짝수(합성수 이므로 true return)
        return true;
    }
    
    while(k>=2){
        if(k%2 == 0) {
            t++;
            k /= 2;
        }
    }
    
    u = tmp / pow(2,t);
    
    int x0 = (int)pow(a,u) % n;
    int x=0;
    for(int i = 1; i<=t; i++){
        
        x = (x0*x0) % n;
        
        if(x==1 && x0 !=1 && x0!=n-1){
            return true;
        }
        
        x0 = x;
    }
    if(x!=1) return true;
    
    return false;

}


int main(){
    
    int M, N;
    cin >> M >> N;

   srand((unsigned int)time(NULL));

    for(int n = M; n<=N; n++){
        
        bool chk = true;
        for(int s = 0; s<10; s++){
            
            int a = rand();
            while(a>=n){a = rand();}
            
            if(Test(a,n) == true){
                //합성수
                chk = false;
                break;
            }
            
        }
        
        
        if(chk){ //s번 다 도는 동안 Test()가 모두 false 이면
            //n은 소수
            cout << n << endl;
        }
        
        
        
        
    }
    
    
    
    return 0;
}

시간 초과가 떴다.

접근 방법 3

많은 사람들이 선택한 '에라토스테네스의 체' 방법을 이용했다. 

참고 : ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

2가 소수니까 2의 배수는 소수가 아니다. 그러므로 2의 배수를 쭉 지운다.

3도 소수니까 3의배수는 소수가 아니다. 그러므로 3의 배수를 쭉 지운다.

이때 주의할 점은 j의 시작값이다. i*j(j<i)까지는 이미 검사했으므로 j 시작값을 i*2 에서 i*i로 개선할 수 있다.

i=5, j=3일때를 예로 들어보자.

5*3 = 15까지는 이미 i=3일때 검사가 됐다. 그러므로 j시작 값을 10(소수 5의 첫번째 배수)이 아닌 25부터 할 수 있는 것이다. 

더 자세히 따져보기 위해 실제로 2~24의 수 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24  을 봐보자.

(i = 2) 2의 배수 4,6,8,10,12,14,16,18,20,22,24 를 checked 한다

(i = 3) 3의 배수 6,9,12,15,18,21,24 를 checked 하는데 사실 이 중 2의 배수들은 i=2일때 이미 checked된 상태이다.

(i = 4) 4의 배수 -> arr[4] = 1이므로 볼 필요도 없이 Pass

(i = 5) 5의 배수 10,15,20 -> 이미 checked된 상태이다.

그러므로 j시작값을 i*i 부터 할 수 있는 것이다. 그러면 중복을 제거할 수 있다.

#include <iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>


using namespace std;

int arr[1000001] = {0};
int main(){
    
    
    int M, N;
    cin >> M >> N;

   
    arr[1] = 1; //1은 소수 아님
    
    
    
    for(int i = 2; i*i <= N; i++){
        
        if(arr[i]==0){
            for(int j = i*i; j<=N; j+=i){
                arr[j] = 1;
            }
        }
    }
    
    
    
    for(int i = M; i<=N; i++){
        if(arr[i] == 0 ) cout << i << "\n";
    }
        
    return 0;
}

문제 링크 : www.acmicpc.net/problem/1748

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다.

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

접근 방법 

입력받은 N을 10, 100, 1000으로 나눈 몫에 따라 경우를 나누어 생각해준다.

case 1) 몫 q가 0보다 클 때는 1~9, 10~99, 100~999과 같이 full로 자리수를 카운팅해준다.

case 2) q가 0이 되면 10~N, 100~N, 1000~N 과 같이 N까지 끊어서 자리수를 카운팅해준다.

예를 들어 N=120일때를 보자.

x = 1일 때, 120/10^1 = 12이므로 0보다 크고 따라서 1~9까지 쭉 썼을 때 자리수는 9개이다. (9 = (10^x  - 10^x-1) * 1)

x = 2일때, 120/10^2 = 1이므로 0보다 크고 따라서 10~99까지 쭉 썼을 때 자리수는 (99-10 + 1) * 2 개이다. 

x = 3일때, 120/10^3 = 0이므로, 이때는 999까지 쓰기 전에 N이 나오기 때문에 100~120까지 썼을 때 자리수는 (120-100+1) * 3 개이다.

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    
    
    int N;
    cin >> N;
    int x = 1;
    int ans = 0;
    while(1){
    
        int q = N/pow(10,x);
        if(q>0){
            ans += (pow(10,x)-pow(10,x-1)) * x;
        }
        else{
            ans += (N-pow(10,x-1) + 1) * x;
            break;
        }
        x++;
    }
    
    cout  << ans << "\n";

    return 0;
}

문제 링크 : www.acmicpc.net/problem/1476

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

접근 방법 1

num을 1부터 하나씩 증가시키면서 나머지가 각각 입력값 e, s, m 과 일치하는지 비교했는데 시간초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num= 1;
    while(1){
        
        if(num%15 == e && num%28 == s && num%19 == m){
            break;
        }
        else num++;
        
    }
    
    cout << num << endl;
    
    return 0;
}

접근 방법 2

num을 1부터 증가시키는 것이 아니라 28의 배수를 기준으로 증가시키면서, num을 15와 19로 나눈 나머지를 입력값과 비교했다. 28의 배수로 한 이유는 15와 19보다 28이 크기 때문에 계산량을 줄이기 위함이다. 그러나 또 시간 초과가 떴다.

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
        
        
    }
    
    
    cout << num << "\n";
    
    return 0;
}

1,2번 시간초과 난 이유

참고:www.acmicpc.net/board/view/51295

입력이 15,28,19 일때를 생각해보자. 즉 e = 15, s = 28, m = 19일때 (num%15)의 범위는 0~14이므로 절대로 15(e)가 될 수 없다. 마찬가지로 (num%19)의 범위는 0~18이므로 절대로 19(m)이 될 수 없어서 계속 반복문을 도는 것이다.

그래서 아래와 같이 28의 배수를 기준으로 할 때, 반복문 시작 전에 if 문으로 e와 m을 체크해주면 시간초과가 뜨지 않는다. 이때 주의할 점은 s에 대해서 검사하면 아예 틀린 값이 나온다. (이유 : 입력이 15, 28, 19이면 출력이 0이 나온다!)

#include <iostream>

using namespace std;


int main(){

    int e,s,m;
    cin >> e >> s >> m;
    
    if(e>=15) e = e%15;
    if(m>=19) m = m%19;
    
    int num, q = 0;
  
    while(1){
        
        num = 28*q + s;
        if(num%15 != e || num%19 !=m){
            q++;
        }
        else{
            break;
        }
    }
    
    cout << num << "\n";
    
    return 0;
}

접근 방법 3

num을 1부터 하나씩 증가시키면서 num - e를 15로 나눈 값이 0인지를 판단하고, s와 m에 대해서도 같은 방법으로 비교하여 3조건이 모두 0이면 반복문을 멈춘다.

예를 들어,

num = 5266, e = 1, s = 2, m = 3 일 때,

5266 = 15*351 + 1

5266 = 28*188 + 2

5266 = 19*277 + 3 

이므로 각 나머지를 LHS로 이항해서 15,28,19 로 나눈 나머지가 모두 0일 때 반복문을 멈춘다.

위의 방법과 어떤 점에서 다른지 모르겠지만 아래 방법은 시간초과가 나지 않았다. 

#include <iostream>

using namespace std;


int main(){
    
    
    
    int e,s,m;
    cin >> e >> s >> m;
    
    int num = 1;
  
    while(1){
        
        if((num-e)%15 == 0 && (num-s)%28==0 && (num-m)%19 == 0){
            break;
        }
        else num++;
        
    }
    
    
    cout << num << "\n";
    
    return 0;
}