졍's 기술 블로그

C++ 언어의 경우 훌륭한 정렬 관련 Library가 존재한다.

기본 사용법

Code - 기본

#include <iostream>
#include <algorithm> // sort()는 algorithm library에 포함되어있음
using namespace std;

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10); // 정렬할 배열의 메모리 주소, 정렬할 마지막 원소의 메모리 주소
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

Code - 정렬할 기준 정하는 방식

#include <iostream>
#include <algorithm>
using namespace std;

// 오름차순 정렬
bool comp_up(int a, int b){ // true, false를 기준으로 정렬 기준을 판단
    return a < b; // a가 b보다 작으면 정렬
}

// 내림차순 정렬
bool comp_down(int a, int b){
    return a > b; // a가 b보다 크면 정렬
}

int main(void){
    int a[10] = {4, 7, 6, 2, 1, 5, 8, 10, 3, 9};
    sort(a, a+10, comp_up);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    sort(a, a+10, comp_down);
    for(int i=0;i<10;i++)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10 
10 9 8 7 6 5 4 3 2 1

Code - Data를 묶어서 정렬

#include <iostream>
#include <algorithm>
using namespace std;

// class: 하나의 객체를 정의함으로써 여러 개의 변수를 정의
// 일종의 새로운 자료형
class Student{
public:
    string name;
    int score;
    // 생성자: 특정 객체 초기화
    Student(string name, int score){
        this->name = name;
        this->score = score;
    }
    // 정렬 기준: 점수가 낮은 순서
    bool operator <(Student &student){
        return this->score < student.score;
    }
};

bool compare(int a, int b){
    return a > b;
}

int main(void){
    // 5명의 학생
    Student students[] = {
        Student("student1", 90),
        Student("student2", 80),
        Student("student3", 79),
        Student("student4", 66),
        Student("student5", 78)
    };
    sort(students, students+5); // 이미 Class 안에 정렬 기준을 정의해두었으니 변수의 이름만 넣어주면 됨
    for(int i=0;i<5;i++)
        cout << students[i].name << " ";
    cout << endl;
    return 0;
}

출력

student4 student5 student3 student2 student1

Code - Pair library를 이용한 정렬

#include <iostream>
#include <algorithm>
#include <vector> // 연결리스트 형태로 표현되는 자료구조
using namespace std;

int main(void){
    // 한 쌍의 데이터를 묶어서 사용할 수 있는 library
    // 기본적으로 first, second 인자를 가짐
    vector<pair<int, string>> v;
    v.push_back(pair<int, string> (90, "student1"));
    v.push_back(pair<int, string> (79, "student2"));
    v.push_back(pair<int, string> (88, "student3"));
    v.push_back(pair<int, string> (69, "student4"));
    v.push_back(pair<int, string> (95, "student5"));

    sort(v.begin(), v.end());

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

출력

student4 student2 student3 student1 student5

Code - 정렬 기준을 명시하는 Pair 사용

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool comp(pair<string, pair<int, int>> a,
          pair<string, pair<int, int>> b){
    // 성적이 같으면 생년월일이 더 느린 학생이 높은 우선순위 가짐
    if(a.second.first == b.second.first)
        return a.second.second > b.second.second;
    // 성적이 다르면 성적이 더 높은 학생이 높은 우선순위 가짐
    else
        return a.second.first > b.second.first;
}

int main(void){
    vector<pair<string, pair<int, int>>> v;
    v.push_back(pair<string, pair<int, int>> ("student1", pair<int, int>(90, 970416)));
    v.push_back(pair<string, pair<int, int>> ("student2", pair<int, int>(87, 990722)));
    v.push_back(pair<string, pair<int, int>> ("student3", pair<int, int>(93, 891130)));
    v.push_back(pair<string, pair<int, int>> ("student4", pair<int, int>(87, 920631)));
    v.push_back(pair<string, pair<int, int>> ("student5", pair<int, int>(84, 950718)));

    sort(v.begin(), v.end(), comp);

    for(int i=0;i<=v.size();i++)
        cout << v[i].first << ' ';
    return 0;
}

출력

student3 student1 student2 student4 student5

병합 정렬

: 대표적인 분할 정복 방법을 채택한 알고리즘으로 O(NlogN)의 시간 복잡도를 가지는 정렬 알고리즘

특징

-. 일단 반으로 정확히 나누고 나중에 합치는 방식으로, 퀵 정렬(Quick Sort)와 다르게 Pivot 값이 존재하지 않는다.

-. 기존 데이터를 담을 추가적인 배열이 필요하다는 점에서 메모리 활용은 비효율적이다.

-. 초기 단계에는 모두 원소가 1인 상태로 분할되어있으며, 한 번 병합할 때마다 2의 배수만큼 씩 병합한다.

-. 너비는 N이지만 높이는 logN이기 때문에 전체 시간 복잡도는 NlogN이다.

더보기

너비? 높이?

너비: i와 j를 비교해 더 작은 값을 k 위치에 저장

        N번의 시도 후 정렬 완료

높이: 너비 정렬을 총 logN 번 반복하면 정렬 완료

병합 정렬(Merge Sort) Sequence

더보기

코드

#include <iostream>
using namespace std;
#define number 8

int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.

void merge(int a[], int m, int middle, int n){
    // m: 정렬할 배열의 시작 지점
    // middle: 정렬할 배열의 중간 지점
    // n: 정렬할 배열의 끝 지점

    int i = m;
    int j = middle+1;
    int k = m;

    // 작은 순서대로 배열에 삽입
    while(i<=middle && j <= n){
        // i가 j보다 더 작으면 새로운 배열에 저장
        if(a[i] <= a[j]){
            sorted[k] = a[i];
            i++;
        }
        // 그렇지 않으면 j 값 저장
        else{
            sorted[k] = a[j];
            j++;
        }
        k++; // 한 번 저장하면 k 증가
    }

    // 남은 데이터 삽입
    // i가 먼저 끝났다면 j 모두 새로운 배열에 저장
    if(i > middle){
        for(int t = j; t <= n; t++){
            sorted[k] = a[t];
            k++;
        }
    }
    // j가 먼저 끝났으면 i 모두 새로운 배열에 저장
    else{
        for(int t = i;t<=middle;t++){
            sorted[k] = a[t];
            k++;
        }
    }

    // 정렬된 배열을 실제 배열에 삽입
    for(int t = m; t <= n; t++){
        a[t] = sorted[t];
    }
}

void merge_sort(int a[], int m, int n){
    // 크기가 1보다 큰 경우 return
    if(m < n){
        int middle = (m+n) / 2;
        merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
        merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
        merge(a, m, middle, n); // 정렬 후 합치기
    }
}

int main(void){
    int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
    merge_sort(arr, 0, number-1);
    for(int i=0;i<number;i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

출력

1 3 5 5 6 7 8 9

시간 복잡도

병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.

☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.

백준 사이트

초심자라면 단계별로 풀어보기, 알고리즘 분류에서 문제 풀어보는 게 좋다.

그 중에서도 단계별로 풀어보기에서 정렬해보기부터 시작하면 좋다.

기본적으로 1초에 1억 번 정도 연산한다고 생각하고 문제 풀면 됨.

1. 수 정렬하기(2750)

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

데이터의 개수가 최대 1,000개. N^2 = 1,000,000개

N^2 알고리즘으로 풀어도 크게 문제 없이 해결 가능하다.

#include <iostream>
using namespace std;

void Print(int *data, int N){
    for(int i=0;i<N;i++)
        cout << data[i] << endl;
}

void Selection_Sort(int *data, int N){
    int tmp, min, idx = 0;
    for(int i=0;i<N;i++){
        min = 1001;
        for(int j=i;j<N;j++){
            if(min > data[j]){
                min = data[j];
                idx = j;
            }
        }

        tmp = data[i];
        data[i] = data[idx];
        data[idx] = tmp;
    }
}

void Bubble_Sort(int *data, int N){
    int tmp = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N-1;j++){
            if(data[j] > data[j+1]){
                tmp = data[j];
                data[j] = data[j+1];
                data[j+1] = tmp;
            }
        }
    }
}

int main(void){
    int N;
    int data[1000];

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

    Selection_Sort(data, N);
    Bubble_Sort(data, N);
    //Insert_Sort(data, N);
    //Quick_Sort(data, N);
    Print(data, N);
    return 0;
}

2. 세수정렬

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

#include <iostream>
using namespace std;
#define N 3

int arr[3]={0,};

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

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << " ";
}

void Insertion_Sort(){
    int j, tmp;
    for(int i=0;i<N-1;i++){
        j = i;
        while(arr[j] > arr[j+1]){
            tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
            j--;
        }
    }
}

int main(void){

    Input();
    //Selection_Sort();
    Insertion_Sort();
    Output();

    return 0;
}

3. 수 정렬하기 2

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

#include <iostream>
using namespace std;

int N;
int arr[1000000+10];

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

void Output(){
    for(int i=0;i<N;i++)
        cout << arr[i] << "\n";
}

void Quick_Sort(int start, int end){
    
    if(start >= end)
        return;

    int mid = start;
    int i = start+1;
    int j = end;
    int tmp;

    while(i <= j){
        // 오른쪽으로 가면서 pivot값보다 큰 값 찾기
        while(arr[mid] >= arr[i]){
            i++;
        }

        // 왼쪽으로 가면서 pivot값보다 작은 값 찾기
        while(arr[mid] <= arr[j] && start < j){
            j--;
        }

        // 엇갈렸으면 pivot 값과 작은 값 변경
        if(i > j){
            tmp = arr[j];
            arr[j] = arr[mid];
            arr[mid] = tmp;
        }
        // 엇갈리지 않았으면 두 값 변경
        else{
            tmp = arr[j];
            arr[j] = arr[i];
            arr[i] = arr[j];
        }
    }

    // start, end 다시 조정해 재귀
    Quick_Sort(start, j-1);
    Quick_Sort(j+1, end);
}

int main(void){
    Input();
    Quick_Sort(0, N-1);
    Output();
}

선택 정렬, 버블 정렬, 삽입 정렬의 한계

: O(N*N)은 데이터 갯수가 10만 개만 넘어가도 일반적인 상황에서 사용하기가 매우 어려운 알고리즘이다.

2^10 = 1,000

2^20 = 1,000,000

log(2)N = (N이 1,000,000일 때) 20

퀵 정렬(Quick Sort)

: 대표적인 분할 정복 알고리즘으로 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 후 배열을 반으로 나누는 정렬 알고리즘

퀵 정렬(Quick Sort) Sequence

더보기

기준값 = 피벗(Pivot)

왼쪽에서 오른쪽으로 이동하면서 Pivot 보다 큰 값 하나 선택

오른 쪽에서 왼쪽으로 이동하면서 Pivot보다 작은 값 하나 선택

작은 값의 index < 큰 값의 index: Pivot과 작은 값 교환

작은 값의 index > 큰 값의 index: 작은 값과 큰 값 교환

 

Code

#include <iostream>
using namespace std;

int number = 10;
int Data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};

void quickSort_up(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] <= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] >= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_up(data, start, j-1); // 왼쪽 data
    quickSort_up(data, j+1, end); // 오른쪽 data
}

void quickSort_down(int *data, int start, int end){
    // start: 정렬을 수행하는 부분집합의 첫 번째 원소
    // end: 정렬을 수행하는 부분집합의 마지막 원소

    // 원소가 1개인 경우
    if(start >= end){
        return;
    }

    int key = start; // pivot

    int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
    int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
    int tmp;

    // 엇갈리는 경우 while 탈출
    while(i <= j){
        // i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
        while(data[i] >= data[key]){
            i++;
        }

        // j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
        // index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
        while(data[j] <= data[key] && j > start){
            j--;
        }

        // 엇갈린 경우 pivot값과 현재 data 변경
        if(i > j){
            tmp = data[j];
            data[j] = data[key];
            data[key] = tmp;
        }
        // 엇갈리지 않은 경우 i와 j index의 data 변경
        else{
            tmp = data[j];
            data[j] = data[i];
            data[i] = tmp;
        }
    }

    // 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
    quickSort_down(data, start, j-1); // 왼쪽 data
    quickSort_down(data, j+1, end); // 오른쪽 data
}

int main(void){
    quickSort_up(Data, 0, number-1); // 오름차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    cout << endl;
    quickSort_down(Data, 0, number-1); // 내림차순
    for(int i=0;i<10;i++){
        cout << Data[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

만약 아래 배열을 정렬한다면?

선택 정렬의 시간 복잡도: N^2 = 100

퀵 정렬의 시간 복잡도: 

1 2 3 4 5 => 5 * 5 = 25

6 7 8 9 10 => 5 * 5 = 25

-> 25 + 25 = 50

∴ O(NlogN)의 시간복잡도를 갖는 알고리즘을 이용하면 100만개 정도의 데이터는 어렵지 않게 정렬이 가능하다.

시간복잡도

평균 : N*logN

최악의 경우: N^2

만약 이미 오름차순 정렬되어있는 배열을 퀵정렬을 이용해 오름차순 정렬한다면?

=> 분할 정복의 이점을 사용하지 못하고 있으므로, 이런 경우에는 insertion sort를 사용하는 게 효율적이다.

버블 정렬(Bubble Sort)

: 옆에 있는 값과 비교해 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법

버블 정렬 Sequence

더보기

한 번 반복이 끝났을 때 가장 큰 값이 가장 마지막 위치로 이동

코드

#include <iostream>
using namespace std;

int main(void){
    int i, j, tmp;
    int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
            if(arr[j] > arr[j+1]){
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }

    for(i=0;i<10;i++){
        cout << arr[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 1) / 2

= N * (N - 1) / 2

= O(N^2)

실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다.
: Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다.
반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.

참고로, 정렬 알고리즘 중 가장 느린 건 Bubble Sort이다.

선택 정렬(Selection sort)

: 가장 작은 것을 선택해서 가장 앞으로 보내는 알고리즘

코드

#include <iostream>
using namespace std;

int main(void){
    // 선택 정렬: 가장 작은 것을 선택해서 가장 앞으로 보내자
    int i, j, min, idx, tmp;
    int array[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
    for(i=0;i<10;i++){
        min = 9999;
        for(j=i;j<10;j++){
            if(min > array[j]){
                min = array[j];
                idx = j;
            }
        }
        tmp = array[i];
        array[i] = array[idx];
        array[idx] = tmp;
        cout << array[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5 6 7 8 9 10

시간 복잡도

10 + 9 + 8 + ... + 1

= 10 * (10 - 9) / 2

=> N * (N - 1) / 2

∴ O(N^2)

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론

약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms

1

티어 : Silver 3
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입출력

우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.

처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.

num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.

#include <iostream>
#include <string>
using namespace std;

int cal_len(long long n){
    string num = to_string(n);
    return num.length();
}

long long ispossible(int n){
    // n의 길이 계산
    int len = cal_len(n);
    string num;
    // n의 길이만큼 1로만 구성된 문자열 만들기
    for(int i=0;i<len;i++){
        num += '1'; // O(n)으로 동작
    }
 
    while(true){
        // num이 n의 배수인지 확인
        if(num%n==0) return num.length();
        // num 한 자리 추가
        num += '1';
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 런타임 에러(out_of_range)로 실패 ㅠ

num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.

그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.

결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.

Algorithm

Brute Force
1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음
2. num이 n으로 나누어 떨어지는지 확인
    2-1. 나누어떨어지면 num의 길이 return
    2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산)
            → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !

Code

#include <iostream>
using namespace std;

long long ispossible(int n){
    int cnt=1;
    long long num=1;
 
    while(true){
        // num이 n의 배수인지 확인
        if(!(num%n)) return cnt;
        
        // num의 크기 줄여주기
        num%=n;
        
        // num 한 자리 추가
        num = num*10+1;
        cnt++;
    }
    return -1;
}

int main(void){
    int n;
    while(true){ 
        cin >> n;
        if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
        cout << ispossible(n) << "\n";
    }
    return 0;
}

메모리: 2020 KB
시간: 0 ms