0. 문제

어떤 수를 소인수분해 했을 때 그 소인수가 2 또는 3 또는 5로만 이루어진 수를 Ugly Number라고 부릅니다. Ugly Number를 차례대로 적어보면
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, .......입니다. 숫자 1은 Ugly Number의 첫 번째 수로 합 니다. 자연수 N이 주어지면 Ugly Number를 차례로 적을 때 N번째 Ugly Number를 구하는 프로그램을 작성하세요.

1. 입력설명

   • 첫 줄에 자연수 N(3<=N<=1500)이 주어집니다.

2. 출력 설명

   • 첫 줄에 N번째 Ugly Number를 출력하세요.

3. 입력 예제1

   • 10

4. 출력 예제1

   • 12

5. 입력 예제2

   • 1500

6. 출력 예제2

   • 859963392

7. 문제 풀이 핵심

   • vector(또는 배열)에 ugly number를 순서대로 입력 한다.
   • ugly number는 2,3,5를 이용해 작은 값 순서대로 입력한다.

1. 풀이1 : vector에 ugly number를 순서대로 입력한다.

1. p2,p3,p5 변수를 생성하여 vector의 제일 앞을 가리킨다.
   • p2,p3,p5 는 각각 vector를 가리키는 인덱스 값
2. p2,p3,p5 가 각각 가리키는 값을 곱하여 최소값을 구한다.
   • p2V = vector[p2] * 2 : p2가 가리키는 uglynumber에 2를 곱함
   • p3V = vector[p3] * 3 : p3가 가리키는 uglynumber에 3를 곱함
   • p5V = vector[p5] * 2 : p5가 가리키는 uglynumber에 5를 곱함
3. p2V, p3V, p5V의 최소값을 vector에 넣는다.
4. 최소값을 가리키는 인덱스는 1증가한다.
   • 만약 p2V가 가장 작으면, p2 에 +1을 한다.
   • 만약 여러 개(p2V,p3V 등) 이 동시에 가장 작으면 , p2,p3에 +1을 한다.
5. 최종적으로 입력받은 number에 해당하는 vector값을 출력한다.

#include<iostream>
#include<vector>
int p2 = 0, p3 = 0, p5 = 0;
int p2V, p3V, p5V;
std::vector<int> vecData;

// 최소값 구하기
int findMin() {
    int min = 0;
    p2V = vecData[p2] * 2;
    p3V = vecData[p3] * 3;
    p5V = vecData[p5] * 5;

    if (p2V <= p3V) {
        if (p2V <= p5V) {
            min = p2V;
        }
        else {
            min = p5V;
        }
    }
    else {
        if (p3V <= p5V) {
            min = p3V;
        }
        else {
            min = p5V;
        }
    }
    return min;
}

int main() {
    int n;
    scanf_s("%d", &n);
    int data;
    vecData.push_back(1);
    for (int i = 1; i < n; i++) {
        int min = findMin();
        if (min >= p2V) {
            p2++;
            data = p2V;
        }
        if (min >= p3V) {
            p3++;
            data = p3V;
        }
        if (min >= p5V) {
            p5++;
            data = p5V;

        }
        vecData.push_back(data);
    }
    std::cout << vecData.back() << std::endl;
    return 0;
}

6. 예시
   

   

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가
로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다.
전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.

1. 입력설명

   • 첫 줄에 H(세로길이)와 W(가로길이)가 입력된다. (5<=H, W<=50) 그 다음 H줄에 걸쳐 각 사각형 지역에 오렌지의 나무 개수(1~9개) 정보가 주어진다.
   • 그 다음 영지의 크기인 세로길이(1H)와 가로길이(1W)가 차례로 입력된다.

2) 출력 설명

• 첫 줄에 현수가 얻을 수 있는 오렌지 나무의 최대 개수를 출력한다.

3) 입력 예제1

• 6 7
• 3 5 1 3 1 3 2
• 1 2 1 3 1 1 2
• 1 3 1 5 1 3 4
• 5 1 1 3 1 3 2
• 3 1 1 3 1 1 2
• 1 3 1 3 1 2 2
• 2 3

4. 출력 예제1

   • 16

5. 문제 풀이 핵심

   • DP 테이블을 구한다.
   • DP 테이블을 이용해 면적을 계산한다.

1. 풀이1 : DP 테이블을 구한다.

1. DP 테이블을 구함
   • i,j 번째 DP 테이블은 아래와 같이 구할 수 있다.
     

     

2. DP 테이블을 이용하여 영지크기를 계산한다.
   • i,j 번째 영지 크기는 아래와 같이 구할 수 있다.
     

     

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

int a[701][701], dy[701][701];
int main() {
    int h, w, n, m, i, j, tmp, max = -2147000000;
    scanf_s("%d %d", &h, &w);
    for (i = 1; i <= h; i++) {
        for (j = 1; j <= w; j++) {
            scanf_s("%d", &a[i][j]);
            dy[i][j] = dy[i - 1][j] + dy[i][j - 1] - dy[i - 1][j - 1] + a[i][j];
        }
    }

    scanf_s("%d %d", &n, &m);
    for (i = n; i <= h; i++) {
        for (j = m; j <= w; j++) {
            tmp = dy[i][j] - dy[i - n][j] - dy[i][j - m] + dy[i - n][j - m];
            if (tmp > max) max = tmp;
        }
    }
    printf("%d\n", max);
    return 0;
}

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번
노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

1. 입력설명

   • 첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.

2. 출력 설명

   • 첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

3. 입력 예제1

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

4. 출력 예제1

   • 17

5. 문제 풀이 핵심

   • 입력값을 모두 더한 값을 sum, DVD 개수를 m이라고 했을 때 정답은 sum / m ~ sum 안에 존재한다고 가정한다.
   • 시작값 : sum / m, 끝값 : sum 으로 잡고 이분 검색 방법으로 정답을 찾는다.

1. 풀이1 : 정답의 범위를 정해놓고, 정답을 이분 검색으로 찾아 나가자!

1. 입력
   • 데이터 개수 저장 : n
   • DVD 개수 저장 : m
   • 데이터 저장 : data
   • 입력 받을 때 합계 sum 저장
2. 정답 가능한 시작값 설정
   • lt = sum / m;
3. 정답 가능한 끝값 설정
   • rt = sum;
4. mid값이 정답 가능한지 확인
   • mid = (lt + rt) / 2
   • 가능하다면, mid보다 큰값은 무조건 가능하므로, rt = mid -1 하면서 solution 변수에 mid값을 저장
   • 안된다면, mid보다는 커야 하므로, lt = mid + 1
   • 4를 반복하다가 lt와 rt가 엇갈리면 중단하고 solution 을 출력
5. 주의 할점
   • 가능 여부 판단 시에 mid는 반드시 값의 max값 보다 커야함
   • DVD 용량이 음악 1곡의 크기보다 커야만 저장이 가능하기 때문

#include<iostream>
#include<vector>

int main() {
#include<iostream>
#include<vector>

bool isAvailable(std::vector<int> data, int mid, int num, int max) {
    int cnt = 1;
    int sum = 0;
    for (int i = 0; i < data.size(); i++) {
        sum += data[i];
        if (mid < sum) {
            cnt++;
            sum = data[i];
        }
    }
    if (mid >= max && cnt <= num) {
        return true;
    }
    return false;
}

int main() {
    int n, m, sum = 0, max = 0;;

    scanf_s("%d %d", &n, &m);
    std::vector<int> data(n);
    for (auto& dd : data) {
        scanf_s("%d", &dd);
        sum += dd;
        if (max < dd) {
            max = dd;
        }
    }
    int lt = sum / m, rt = sum, mid, solution = sum;
    while (lt <= rt) {
        mid = (lt + rt) / 2;
        if (isAvailable(data, mid, m, max)) {
            solution = mid;
            rt = mid - 1;
        }
        else {
            lt = mid + 1;
        }
    }

    std::cout << solution;
    return 0;
}

9. 예시

   • 입력 : 9, 3
   • 데이터 : 1 2 3 4 5 6 7 8 9
   • sum = 45, m = 3
   • 정답은 45 / 3 = 15 ~ 45 사이에 존재
   • 중간 값인 60/2 = 30 이 가능한지 확인
   • 가능하므로 범위는 15 ~ 29, sol 변수에 30 저장
   • 중간 값인 44/2 = 22 가 가능한지 확인
   • 가능하므로 범위는 15 ~ 21, sol 변수에 22 저장
   • 중간 값인 36/2 = 18 이 가능한지 확인
   • 가능 하므로 범위는 15 ~ 17, sol 변수에 18 저장
   • 중간 값인 32/2= 16 이 가능한지 확인
   • 불가능 하므로 범위는 17~17
   • 중간 값인 34/7 = 17 이 가능한지 확인
   • 가능하므로 범위는 17 ~ 16, sol 변수에 17 저장
   • lIdx와 rIdx가 엇갈리므로 빠져나오고 sol변수에 저장된 17이 정답

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
만약 N=15이면
7+8=15
4+5+6=15
1+2+3+4+5=15
와 같이 총 3가지의 경우가 존재한다.

1. 입력설명

   • 첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어진다.

2. 출력 설명

   • 첫줄부터 각각의 경우의 수를 출력한다. 맨 마지막 줄에 총 개수를 출력한다

3. 입력 예제1

   • 15

4. 출력 예제1

   • 7 + 8 = 15
   • 4 + 5 + 6 = 15
   • 1 + 2 + 3 + 4 + 5 = 15
   • 3

5. 문제 풀이 핵심

   • 2개 연속된 수의 경우 숫자에서 1,2를 뺀 값이 2로 나누어지는지 확인한다.
   • 3개 연속된 수의 경우 숫자에서 1,2,3을 뺀 값이 3으로 나누어지는지를 확인한다.
   • 반복한다.

1. 풀이1 : 오른쪽으로 +1 왼쪽으로 -1을 반복하자.

1. 방법 요약
   • 입력 변수(num)를 n(2~num)으로 나누고, 좌/우로 값을 번갈아 하나씩 연결시키며 더한다.(n 개수 만큼 연결)
   • 더한 값이 num과 같으면 기록하고, 커지면 break한다.
   • 반복하다가 왼쪽 값이 1이거나 오른쪽값이 num과 같아지면 그만한다.

#include<iostream>
#include<vector>

int main() {
#include<iostream>
#include<deque>
int main() {
    int num;
    scanf_s("%d", &num);

    int cnt = 0;
    int lIdx = 0, rIdx = 0;
    int n = 2;

    for (n = 2; n < num; n++) {
        int sum = 0;
        int mok = num / n;
        std::deque<int> result;
        bool flag = true;
        lIdx = mok;  rIdx = mok;
        int kk = 1;
        sum += mok;
        result.push_back(mok);
        while (kk < n) {
            if(flag){
                rIdx++;
                sum += rIdx;
                flag = false;
                result.push_back(rIdx);
            }
            else {
                lIdx--;
                sum += lIdx;
                flag = true;
                result.push_front(lIdx);
            }
            kk++;
            if (sum > num) break;
            else if (sum == num) {
                std::cout << result[0];
                for (int ii = 1; ii < result.size(); ii++) {
                    std::cout << " + " << result[ii];
                }
                std::cout << " = " << sum << std::endl;

                cnt++;
            }
            if (lIdx == 1 || rIdx == num) break;
        }

    }
    std::cout << cnt;
    return 0;
}

9. 예시

   • 입력 : 15
   • 2로 나누어질 경우
   • 15 / 2 = 7 => 오른쪽하나 증가하여 8 , ==> {7,8}
   • 15 / 3 = 5 => 오른쪽하나 증가 6, 왼쪽하나 증가 4, ==> {4,5,6}
   • 15 / 4 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5 ==> 2+3+4+5 != 15 이므로 (x)
   • 15 / 5 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5, 왼쪽 하나 증가 1 ==> {1,2,3,4,5}
   • lIdx가 1이므로 멈춤

2. 풀이2 : n이 연속된 2개로 분리된다면, n에서 1,2 를 뺀값을 2로 나누어 떨어진다.

1. 방법 요약
   • n = 2일 경우, 15 에서 1,2를 뺀 12를 2로 나누어 떨어진다.
   • 1,2에 12/2의 몫 6을 각각 더해주면 된다. ( 7,8 )
   • n = 3일 경우, 15에서 1,2,3을 뺀 9를 3으로 나누어 떨어진다.
   • 1,2,3에 9/3의 몫 3를 각각 더한다. (4,5,6)
   • 반복한다.

int main() {
#include<iostream>
using namespace std;

int main() {
    int a, b = 1, cnt = 0, tmp, i;
    scanf_s("%d", &a);
    tmp = a;
    a--;

    while (a > 0) {
        b++;
        a = a - b;
        if (a%b == 0) {
            for (i = 1; i < b; i++) {
                printf("%d + ", (a / b) + i);
            }
            printf("%d = %d\n", (a / b) + i, tmp);
            cnt++;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

9. 예시

   • 입력 : 15
   • n : 2일 경우
   • 15 에서 1,2를 뺀 12 / 2 는 나머지가 0이므로 1,2에 6을 더한 값이 정답 => {7,8}
   • n : 3일 경우
   • 15 에서 1,2,3를 뺀 9 / 3 은 나머지가 0이므로 1,2,3에 3을 더한 값이 정답 => {4,5,6}
   • 15 에서 1,2,3,4를 뺀 5 / 4 은 나머지가 1이므로 pass
   • 15에서 1,2,3,4,5를 뺀 0 / 5 는 나머지가 0이므로 1,2,3,4,5에 0을 더한 값이 정답 => {1,2,3,4,5}
   • a가 0이므로 멈추고 개수 출력

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다.
예를 들어 다음과 같은 수열의 경우
4 8 6 2 5 1 3 7
1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고,
2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개,
3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개......
따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다.
n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하는 프로그램을 작성하세요.

1. 입력설명

   • 첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 inversion sequence가 숫자 사이에 한 칸의 공백을 두고 주어진다.

2. 출력 설명

   • 오름차순으로 정렬된 수열을 출력합니다.

3. 입력 예제1

   • 8
   • 5 3 4 0 2 1 1 0

4. 출력 예제1

   • 4 8 6 2 5 1 3 7

5. 문제 풀이 핵심

   • 입력 데이터 끝에서 부터 시작!
   • 입력 데이터의 값 만큼 앞으로 땡기고, 그 자리에 해당 숫자를 입력
   • 삽입 정렬!!

1. 풀이1 : 1부터 자기 위치에 저장하자!

1. 입력
   • 사용자에게 num을 입력 받음
   • data vector를 num 개수 만큼 초기화
   • reuslt vector를 num 개수 만큼 101로 초기화(최대값이 100이므로)
2. i = 0 ~ n-1 까지 반복
   • 숫자는 1부터 시작하므로 idx = i+1로 저장
3. j = 0 ~ n-1 까지 반복
   • result[j] 가 idx보다 크면 개수를 +1
   • 개수가 data[i] + 1 과 같으면 break
4. result[j] 에는 idx를 저장
5. 반복이 끝나면 값 출력

#include<iostream>
#include<vector>

int main() {
    // 데이터 입력
    int num;
    scanf_s("%d", &num);
    std::vector<int> data(num);
    for (auto & dd : data) {
        scanf_s("%d", &dd);
    }

    std::vector<int> result(num,101);
    int j = 0;
    for (int i = 0; i < data.size(); i++) {
        int idx = i + 1;    // 해당 번호 저장(1~n)
        int cnt = 0;
        for (j = 0; j < result.size(); j++) {
            if (result[j] > idx) {
                cnt++;
            }
            if (cnt == data[i]+1) {
                break;
            }
        }
        result[j] = idx;
    }

    for (auto dd : result) {
        std::cout << dd << " ";
    }
    return 0;
}

9. 예시

   • 입력 : 8
   • data : 5,3,4,0,2,1,1,0
   • result : 101,101,101,101,101,1,101,101
   • result : 101,101,101,2,101,1,101,101
   • result : 101,101,101,2,101,1,3,101
   • result : 4,101,101,2,101,1,3,101
   • result : 4,101,101,2,5,1,3,101
   • result : 4,101,6,2,5,1,3,101
   • result : 4,101,6,2,5,1,3,7
   • result : 4,8,6,2,5,1,3,7

2. 풀이2 : 뒤에서 부터 저장하자!

1. 입력
   • 사용자에게 num을 입력 받음
   • data vector를 num 개수 만큼 초기화
   • reuslt vector를 num 개수 만큼 101로 초기화(최대값이 100이므로)
2. i는 끝에서부터 시작까지 반복
   • j는 i에서 시작하여 data[i]의 개수만큼 데이터를 앞으로 땡김
   • result[j] 에 idx를 저장

int main() {
    int num;
    scanf_s("%d", &num);

    std::vector<int> data(num);
    std::vector<int> result(num);

    for (auto & dd : data) {
        scanf_s("%d", &dd);
    }

    int i = 0, j = 0, idx;

    for (i = data.size() - 1; i >= 0; i--) {
        idx = i + 1;
        for (j = i; j < i + data[i]; j++) {
            result[j] = result[j + 1];
        }
        result[j] = idx;
    }
    for (auto dd : result) {
        std::cout << dd << " ";
    }
    return 0;
}

9. 예시

   • 입력 : 8
   • data : 5,3,4,0,2,1,1,0
   • result : 0,0,0,0,0,0,0,8
   • result : 0,0,0,0,0,0,8,7
   • result : 0,0,0,0,0,8,6,7
   • result : 0,0,0,0,8,6,5,7
   • result : 0,0,0,4,8,6,5,7
   • result : 0,0,4,8,6,5,3,7
   • result : 0,4,8,6,2,5,3,7
   • result : 4,8,6,2,5,1,3,7

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다.
예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다.
자연수 N이 입력되면 1부터 N까지 숫자를 적을 때, 3의 개수가 몇 개인지 구하여 출력하는 프로그램을 작성하세요.

1. 입력설명

   • 첫 줄에 자연수의 개수 N(3<=N<=1,000,000,000)이 주어집니다.

2. 출력 설명

   • 3의 개수를 출력하세요.

3. 입력 예제1

   • 15

4. 출력 예제1

   • 2

5. 문제 풀이 핵심

   • 1의 자리~ n의 자리 숫자까지 순회 한며, 각 자리에서 3이 나오는 횟수를 계산한다.
   • i 번째 자리 수를 기준으로 왼쪽과 오른쪽의 숫자로 분리한다.
   • i 번째 자리 수가 3일 경우는 왼쪽의 수와 오른쪽 수의 조합으로 계산 가능하다.

1. 풀이1

1. 사용자에게 num을 입력 받음

2. vector에 각 자리수를 저장

3. 1의 자리 부터 n의 자리까지 순회 아래 반복

4. i 번째 기준 왼쪽 숫자와 오른쪽 숫자로 분리

5. i번째 숫자가 3보다 작으면, 왼쪽 숫자 * 10^i 만큼 3이 발생

6. i번째 숫자가 3이면 왼쪽 숫자*10^i + 오른쪽 숫자 + 1 만큼 발생

7. i번째 숫자가 3보다 크면, 왼쪽 숫자*10^i + 10^i만큼 발생

8. 모든 자리에서 3이 나오는 횟수를 합함

#include<iostream>
#include<vector>
#include<deque>
int main() {
    int num, cnt = 0;;
    scanf_s("%d", &num);
    std::vector<int> a;
    int sum = 0;
    int kk = 1;

   //벡터에 각 자리수 삽입
    while (num > 0) {
        a.push_back(num % 10);
        num = num / 10;
    }

    for (int i = 0; i < a.size(); i++) {
        // 앞의 숫자
        int numFront = 0, n10 = 1;
        for (int j = i + 1; j < a.size(); j++) {
            numFront += a[j] * n10;
            n10 *= 10;
        }

        // 뒤의 숫자
        int numBack = 0;
        for (int j = i - 1; j >= 0; j--) {
            numBack = numBack * 10;
            numBack += a[j];
        }

      //3의 개수 구하기
        sum += numFront * kk;
        if (a[i] == 3) {
            sum += numBack + 1;
        }
        else if (a[i] > 3 ){
            sum += kk;
        }
        kk *= 10;
    }
    std::cout << sum;
    return 0;
}
}

9. 예시
   • 1534의 경우 {4,3,5,1} 형태로 저장
   • i가 0이면(일의 자리 수) 4가 기준이며, 153 , 0 으로 분리
   • 4는 3보다 크므로 3이 나올 경우는 153*10^0 + 10^0 = 154회 발생
   • i가 1이면(십의 자리 수) 3이 기준이며, 15, 4로 분리
   • 3이므로 3이 나올 경우는 15*10^1 + 4 + 1 = 155회 발생
   • i가 2이면(백의 자리 수) 5가 기준이며, 1, 34로 분리
   • 5는 3보다 크므로 3이 나올 경우는 1*10^2 + 10^2 = 200
   • i가 3이면(천의 자리 수) 1이 기준이며, 0 ,534로 분리
   • 1은 3보다 작으므로 3이 나올 경우는 0 * 10^3 = 0
   • 총 509회 발생

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.

1. 입력설명
   • 첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
2. 출력 설명
   • 첫 줄에 소수의 개수를 출력합니다.
3. 입력 예제1
   • 20
4. 출력 예제1
   • 8
5. 문제 풀이 핵심
   • 소수를 구할 때 n까지 할 필요 없고 sqrt(n)까지만 하면 된다.!

1. 풀이1 : 소수를 별도 컨테이너에 저장하여 비교

1. 사용자에게 num을 입력 받음
2. 소수를 관리할 컨테이너 생성 및 2를 추가
3. i 는 3~num 까지 순회
   • j는 소수 컨테이너를 순회
   • i를 j번째 소수로 나누어 나머지가 0 이면 바로 멈춤
   • j가 소수 컨테이너를 다 순회하였으면, i를 소수 컨테이너에 추가
4. 소수 컨테이너 사이즈를 출력

#include<iostream>
#include<vector>
int main() {
    int num, i, j;
    std::cin >> num;
    std::vector<int> sosus;
    sosus.push_back(2);
    for (i = 3; i <= num; i++) {
        for (j = 0; j < sosus.size(); j++) {
            if (i % sosus[j] == 0) {
                break;
            }
        }
        if (j == sosus.size()) {
            sosus.push_back(i);
        }
    }

    std::cout << sosus.size();
    return 0;
}

5. 예제(20 입력 시)
   • 3 => 1번 순회 {2,3}
   • 4 => 2번 순회 {2,3}
   • 5 => 2번 순회 {2,3,5}
   • 6 => 3번 순회 {2,3,5}
   • 7 => 3번 순회 {2,3,5,7}
   • 8 => 4번 순회 {2,3,5,7}
   • 9 => 4번 순회 {2,3,5,7}
   • 10 => 4번 순회 {2,3,5,7}
   • 11 => 4번 순회 {2,3,5,7,11}
   • 12 => 5번 순회 {2,3,5,7,11}
   • 13 => 5번 순회 {2,3,5,7,11,13}
   • 14 => 6번 순회 {2,3,5,7,11,13}
   • 15 => 6번 순회 {2,3,5,7,11,13}
   • 16 => 6번 순회 {2,3,5,7,11,13}
   • 17 => 6번 순회 {2,3,5,7,11,13,17}
   • 18 => 7번 순회 {2,3,5,7,11,13,17}
   • 19 => 7번 순회 {2,3,5,7,11,13,17,19}
   • 20 => 8번 순회 {2,3,5,7,11,13,17,19}
   • 총 : 83번 순회

2. 풀이2 : i의 제곱근까지만 순회

1. 사용자에게 num을 입력 받음
2. i 는 2~num 까지 순회
   • j는 2 부터 i의 제곱근 까지 순회
   • i 를 j로 나누어 떨어지면 break
   • j가 끝까지 순회했으면 개수를 +1
3. 개수 출력

#include<iostream>

int main() {
    int num, i, j, cnt = 0;
    bool flag;
    std::cin >> num;
    for (i = 2; i <= num; i++) {
        flag = true;
        for (j = 2; j * j <= i; j++) {
            if (i%j == 0) {
                flag = false;
                break;
            }
        }
        if (flag == true) cnt++;
    }
    std::cout << cnt;

    return 0;
}

4. 예시(20 입력시)
   • 2 => 1회 순회(j=2)
   • 3 => 1회 순회(j=2)
   • 4 => 1회 순회(j=2)
   • 5 => 1회 순회(j=2)
   • 6 => 1회 순회(j=2)
   • 7 => 1회 순회(j=2)
   • 8 => 1회 순회(j=2)
   • 9 => 2회 순회(j=2,3)
   • 10 => 2회 순회(j=2,3)
   • 11 => 2회 순회(j=2,3)
   • 12 => 2회 순회(j=2,3)
   • 13 => 2회 순회(j=2,3)
   • 14 => 2회 순회(j=2,3)
   • 15 => 2회 순회(j=2,3)
   • 16 => 3회 순회(j=2,3,4)
   • 17 => 3회 순회(j=2,3,4)
   • 18 => 3회 순회(j=2,3,4)
   • 19 => 3회 순회(j=2,3,4)
   • 20 => 3회 순회(j=2,3,4)
   • 총 36회 순회
5. 풀이1 vs 풀이2
   • 풀이 1 : 83번 순회로 계산 가능
   • 풀이 2 : 36번 순회로 계산 가능
   • 풀이 2가 훨씬 효율적

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 문제

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4개) 와 같이 각 숫자의 약수의 개수가 구해집니다.
출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.
1 2 2 3 2 4 2 4 와 같이 출력한다.

1. 입력설명
   • 첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.
2. 출력 설명
   • 첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.
3. 입력 예제1
   • 8
4. 출력 예제1
   • 1 2 2 3 2 4 2 4
5. 문제 풀이 핵심
   • 순서 대로 약수를 구하면 속도가 너무 느리다.
   • i는 1~num 을 순회하며, i의 배수의 자리 개수를 더해주자.!

1. 풀이1 : 순서대로 약수 구하는 방법

1. 두 개의 for문을 돌며, 순서대로 약수를 구하는 방법
   • 이해가 쉽고, 동작되나 속도가 매우 느림(O(N제곱))

int getCount(int num){
   int cnt = 2;
   for ( int i = 2; <= num / 2; i++ ){
      if (num % i == 0){
         cnt++;
      }
   }
   return cnt;
}

int main(){
   int num;
   std::cin >> num;

   cout << "1 2 2 3";   // 4까지는 그냥 출력
   for ( int i = 5 ; i<= num; i++){
      cout<< " " << getCount(i);
   }
}

2. 풀이2 : 배수를 이용하는 방법

1. 사용자에게 num을 입력 받음
2. num개의 숫자에 대한 약수 개수를 가지고 있는 공간 할당
   • num 개수 만큼 공간 확보 및 1로 초기화
3. i는 2 에서 num 까지 순회
   • j는 i 에서 num 까지 i의 배수로 순회
   • j의 위치 공간에 count를 +1함
4. 최종 출력

#include<iostream>
#include<vector>
int main() {
    int num;
   // 1. 사용자에게 num을 입력 받음
    std::cin >> num;
   // 2. num 개수 만큼 공간 확보 및 1로 초기화
    std::vector<int> cnt(num, 1);
    // 3. i 는 2부터 num까지 순회
    for (int i = 2; i <= num; i++) {
      // 4. j는 i부터 num까지 순회하며, i의 배수 위치 공간에 count + 1
        for (int j = i; j <= num; j = j + i) {
            cnt[j - 1] = cnt[j - 1]++;
        }
    }

   // 5. 결과를 출력
    std::cout << cnt[0];
    for (int i = 1; i < num; i++) {
        std::cout << " " << cnt[i];
    }
    return 0;
}

5. 예시(8 입력 시)
   • {1,1,1,1,1,1,1,1} : 1은 모두의 약수이므로 제외하고, 개수 공간을 1로 초기화
   • {1,2,1,2,1,2,1,2} : 2의 배수 위치 개수 증가(4번 순회->2,4,6,8)
   • {1,2,2,2,1,3,1,2} : 3의 배수 위치 개수 증가(2번 순회->3,6)
   • {1,2,2,3,1,3,1,3} : 4의 배수 위치 개수 증가(2번 순회->4,8)
   • {1,2,2,3,2,3,1,3} : 5의 배수 위치 개수 증가(1번 순회->5)
   • {1,2,2,3,2,4,1,3} : 6의 배수 위치 개수 증가(1번 순회->6)
   • {1,2,2,3,2,4,2,3} : 7의 배수 위치 개수 증가(1번 순회->7)
   • {1,2,2,3,2,4,2,4} : 8의 배수 위치 개수 증가(1번 순회->8)
6. 풀이1 vs 풀이2
   • 풀이 1 : 48번(7*7) 순회로 계산 가능
   • 풀이 2 : 12번 순회(1 제외)로 계산 가능
   • 풀이 2가 훨씬 효율적

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 요약

1. 이분 검색 이란?

1. 정렬된 데이터를 계속해서 반으로 나누어 빠르게 찾는 방법
2. 복잡도 : O(logn)
3. 사용 예시
   • 자료구조 내에 특정 값을 찾을 떄(vector에 30이 있는지)
   • 특정 값이 정답인지 추려나갈 때 사용(lt~rt사이에서 정답을 찾을 때)

2. 이분 검색 방법

1. n개의 데이터를 정렬
2. 양끝을 가리키는 포인터 생성
   • lt = 0번째 인덱스
   • rt = n-1번째 인덱스
3. 가운데를 가리키는 포인터 생성
   • mid = (lt+rt) / 2
4. mid 가 찾는 값(key) 인지 확인
   • 같다면 그 index(몇번째인지 출력시 index + 1)를 출력
   • mid가 key보다 크다면, rt를 mid - 1로 설정
   • mid가 key보다 작다면, lt를 mid + 1로 설정
   • 2~4를 반복
5. lt 가 rt보다 크면 찾는 값이 없으므로 중단함

3. 예제

1. 입력 데이터
   • 개수 8
   • 데이터 : 12, 23, 32, 57, 65, 81, 87, 99
   • 찾는 값 : 32
2. lt = 0, rt = 7
   • mid = 3
   • data[mid] = 57 > 32
   • rt = mid -1 = 2
3. lt = 0, rt = 2
   • mid = 1
   • data[mid] = 23 < 32
   • lt = mid + 1 = 2
4. lt = 2, rt = 2
   • mid = 2
   • data[mid] = 32 == 32
5. 찾는 인덱스는 mid+2 = 3번째 인덱스

4. 소스

#include<iostream>
#include<vector>
#include<algorithm>
int main() {
    int cnt, num;
    scanf_s("%d %d", &cnt, &num);

    std::vector<int> data(cnt);
    for (auto& dd : data) {
        scanf_s("%d", &dd);
    }

    std::sort(data.begin(), data.end());

    int lt = 0, rt = data.size() - 1, mid;
    while (1) {
        mid = (lt + rt) / 2;
        if (num == data[mid]) {
            std::cout << mid + 1;
            break;
        }
        else if (num > data[mid]) {
            lt = mid + 1;
        }
        else {
            rt = mid - 1;
        }
        if (lt > rt) {
            std::cout << "찾는 값 없음";
            break;
        }
    }
    return 0;
}

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

0. 요약

1. 선택 정렬

1. 핵심

   • 가장 작은 값(또는 가장 큰 값)을 제일 앞으로 보내자
   • 앞쪽(index 0) 부터 정렬이 된다.

2. 예제(파란색 : 정렬 완료, 빨간색 : 교환)

   • 13, 5, 11, 7, 23, 15
   • 5, 13, 11, 7, 23, 15
   • 5, 7, 11, 13, 23, 15
   • 5, 7, 11, 13, 15, 23

3. 복잡도 : O(N^2)

4. 소스

std::vector<int> data = { 13,5,11,7,23,15 };
for (int i = 0; i < data.size(); i++) {
    int minIdx = i;
    for (int j = i + 1; j < data.size(); j++) {
        if (data[minIdx] > data[j]) {
            minIdx = j;
        }
    }
    int temp;
    temp = data[i];
    data[i] = data[minIdx];
    data[minIdx] = temp;
}

5. 사용 예시
   • N명의 수학 성적 중 3등의 점수를 구하라
   • 입력 : 80 96 75 82 96 92 100
   • 출력 : 92
   • 1등부터 3등까지만 정렬하면 되므로 선택정렬이 효율적임.

2. 버블 정렬

1. 핵심

   • 이웃값과 비교해서 더 큰 값을 뒤로 보내길 반복하자
   • 제일 큰 값이 오른쪽으로 이동하여 오른쪽부터 정렬된다.

2. 예제(파란색 : 정렬 완료, 빨간색 : 교환)

   • 13, 5, 11, 7, 23, 15
   • 5, 13, 11, 7, 23, 15
   • 5, 11, 13, 7, 23, 15
   • 5, 11, 7, 13, 23, 15
   • 5, 11, 7, 13, 15, 23
   • 5, 7, 11, 13, 15, 23

3. 복잡도 : O(N^2)

4. 소스

std::vector<int> data = { 13,5,11,7,23,15 };

for (size_t i = 0; i < data.size(); i++) {
    for (size_t j = 0; j < data.size() -1 - i; j++) {
        if (data[j] > data[j + 1]) {
            int temp;
            temp = data[j + 1];
            data[j + 1] = data[j];
            data[j] = temp;
        }
    }
}

5. 사용 예시
   • 음의 정수를 양의 정수 앞으로 오도록 하되 음의 정수, 양의 정수 순서에는 변함이 없게 하라
   • 입력 : 1,2,3,-3,-2,5,6,-6
   • 출력 : -3,-2,-6,1,2,3,5,6

3. 삽입 정렬

1. 핵심

   • 두 번째 위치 부터 끝까지 돌면서 나보다 왼쪽의 위치 중 알맞은 위치로 삽입하자.
   • 데이터가 이미 정렬된(또는 거의 정렬된) 상태에서는 굉장히 빠르다.

2. 예제(파란색 : 정렬 완료, 빨간색 : 삽입 원소, □ : 삽입 위치)

   • □, 13, 5, 11, 7, 23, 15
   • 5, □, 13, 11, 7, 23, 15
   • 5, □, 11, 13, 7, 23, 15
   • 5, 7, 11, 13, 23, 15
   • 5, 7, 11, 13, □, 23, 15
   • 5, 7, 11, 13, 15, 23

3. 복잡도 : O(N^2)

4. 소스

std::vector<int> data = { 13,5,11,7,23,15 };

int j = 0;
for (size_t i = 1; i < data.size(); i++) {
    int temp = data[i];
    for (j = i - 1; j >= 0; j--) {
        if (data[j] > temp) {
            data[j + 1] = data[j];
        }
        else {
            break;
        }
    }
    data[j + 1] = temp;
}

4. 병합 정렬

1. 핵심

   • 제일 작은 2개의 단위로 분리하여 정렬하고 합치자

2. 예제(빨간색 : 비교 대상)

   • 13, 5, 11, 7, 23, 15
   • 5, 13, 11, 7 ,23 ,15
   • 5, 11, 13, 7, 23, 15
   • 5, 11, 13, 7, 23, 15
   • 5, 11, 13, 7, 15, 23
   • 5, 7, 11, 13, 15, 23

3. 복잡도 : O(N*logN)

4. 소스

int number = 6;
int size;
int count = 0;
std::vector<int> sorted(number);
void merge(std::vector<int>& a, int startIdx, int middle, int endIdx) {
    int i = startIdx;
    int j = middle + 1;
    int k = startIdx;

    // 두개의 영역을 각각 비교하여 작은 수선대로 sorted에 삽입
    while (i <= middle && j <= endIdx) {
        if (a[i] <= a[j]) {
            sorted[k] = a[i];
            i++;
        }
        else {
            sorted[k] = a[j];
            j++;
        }
        k++;
    }

    // 남은 데이터 삽입(i나 j가 먼저 도달했을 경우을 대비)
    if (i > middle) {
        // i가 먼저 끝났다면 남은 j값을 넣어주자
        for (int t = j; t <= endIdx; t++) {
            sorted[k] = a[t];
            k++;
        }
    }
    else {
        // j가 먼저 끝났다면 남은 i값을 넣어주자
        for (int t = i; t <= middle; t++) {
            sorted[k] = a[t];
            k++;
        }
    }

    // 실제 배열에 복사
    for (int t = startIdx; t <= endIdx; t++) {
        a[t] = sorted[t];
    }
}

void mergeSort(std::vector<int>& a, int startIdx, int endIdx) {

    if (startIdx < endIdx) {
        int middle = (startIdx + endIdx) / 2;
        mergeSort(a, startIdx, middle);
        mergeSort(a, middle + 1, endIdx);
        merge(a, startIdx, middle, endIdx);
    }
}

int main() {
    std::vector<int> array = { 13, 5, 11, 7, 23, 15 };
    mergeSort(array, 0, array.size() - 1);
    for (auto dd : array) {
        std::cout << dd << " ";
    }
    return 0;
}

5. 퀵 정렬

1. 핵심

   • 피벗(특정 값)을 기준으로 두고 왼쪽부터 시작해 오른쪽으로 피벗보다 큰 숫자를 찾고, 동시에 오른쪽부터 시작해 왼쪽으로 피벗보다 작은 숫자를 찾아 두 숫자를 교환한다.
   • 위의 과정을 반복하다가 왼쪽과 오른쪽이 엇갈릴 때 작은 원소와 피벗을 교환한다.
   • 피벗을 기준으로 왼쪽 집단과 오른쪽 집단에 대해 위의 과정을 반복 수행한다.
   • 일반적으로 집단의 가장 앞 원소를 초기 피벗값으로 설정한다.

2. 예제(빨간색 : 피벗, 파란색 : 왼쪽부터 가서 큰 원소, 초록색 : 오른쪽부터 가서 작은 원소)

   • 13, 5, 11, 7, 23, 15
   • 엇갈렸으므로 작은 원소(7)과 피벗(13)을 교환
   • 7, 5, 11, 13, 23, 15
   • 7, 5, 11, 13, 23, 15
   • 엇갈렸으므로 작은 원소(5)와 피벗(7)을 교환
   • 5, 7, 11, 13, 23, 15
   • 엇갈렸으므로 작은 원소(15)와 피벗(23)을 교환
   • 5, 7, 11, 13, 15, 23

3. 복잡도 : O(N*logN)

4. 소스

#include<iostream>
#include<vector>
void quick(std::vector<int>& data, int startIdx, int endIdx) {
    if (startIdx >= endIdx) return;
    int pivot = data[startIdx];
    int i = startIdx, j = endIdx;
    for (i = startIdx + 1; i <= endIdx; i++) {
        if (data[i] > pivot) {
            break;
        }
    }
    for (j = endIdx; j >= startIdx + 1; j--) {
        if (data[j] < pivot) {
            break;
        }
    }

    if (i >= j) {
        data[startIdx] = data[j];
        data[j] = pivot;
    }
    else {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
    quick(data, startIdx, j - 1);
    quick(data, j + 1, endIdx);
}

int main() {
    std::vector<int> data = { 13,5,11,7,23,15 };
    quick(data, 0, 5);
    return 0;
}

참고

1. it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

2. 동빈나