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. 요약

1. 값에 의한 전달 방식이 유리한 경우
   • 기본 자료형(int 등)
   • STL 반복자
   • STL 함수 객체 타입
2. 위의 경우를 제외하고 모두 상수 객체에 대한 참조자로 전달하자
   • 생성자/소멸자를 호출하지 않기 때문에 효율적
   • const를 사용하여 전달되는 객체가 변경되지 않음을 보장
   • 복사 손실 문제가 없어짐

1. 값에 의한 전달 방식

1. 함수로부터 객체를 전달 받거나, 함수에 객체를 전달할 때 값에 의한 전달 방식을 사용

   • 함수 매개 변수는 실제 인자의 '사본'을 통해 초기화
   • 함수 호출 시 : 함수가 반환한 값의 '사본'을 전달 받음
   • 이들 사본을 만들어내는 것은 복사 생성자

2. 복사 생성자는 고비용 연산!

   • 아래 예제 참고
   • plato를 인자로 전달하면 매개 변수 s를 초기화 하기 위해 student의 복사 생성자 호출!
   • validateStudent 함수가 끝나면 Student의 소멸자 호출!
   • Student에는 총 4개의 string이 있기 때문에 4개의 생성/소멸자 호출됨

class Person{
public:
   Person();
   virtual ~Person();
private:
   std::string name;
   std::string address;
};

class Student: public Person{
public:
   Student();
   ~Student();
private:
   std::string schoolName;
   std::string schoolAddres;
};

bool validateStudent(Student s);
Student plato;
bool platoIsOk = validateStudent(plato);

2. 상수객체에 대한 참조자로 전달

bool validateStudent(const Student& s);

1. 새로운 객체가 만들어지지 않는다.
   • 생성자/소멸자가 호출되지 않는다.
2. const를 사용
   • Student 객체 s는 변경되지 않음을 보장한다!
3. 복사 손실 문제가 없어지는 장점
   • 상속받은 객체 생성 시 부모 객체의 멤버만 있는 문제
   • 참조자는 보통 포인터를 써서 구현됨(C++ 컴파일러 동작 원리)
   • 즉, 참조자를 전달한다는 것은 포인터를 전달한다는 것

class Window {
public:
   std::string name() const;
   virtual void display() const;
};

class WindowWithScrollBars: public Window{
public:
   virtual void display() const;
};

void printNameAndDisplay(Window w){
   std::cout << w.name();
   w.display(); // Window의 display 함수만 호출
}

// 위 함수에 WindowWithScrollBars 객체를 전달
WindowWithScrollBars wwsb;
// Window 객체 부분만 있고,
// WindowWithScrollBars 부분은 초기화 되지 않음
printNameAndDisplay(wwsb);

// 상수 객체 참조자로 전달하여 문제 해결
// 어떤 종류의 Window가 전달되더라도 복사 손실 문제 없어짐
void printNameAndDisplay(const Window& w){
   std::cout<< w.name();
   w.display();   // 전달되는 타입에 따라 다른 display 호출됨
}

3. 값에 의한 전달이 상수 객체에 대한 참조자 전달보다 효율적인 때도 있다

1. 기본 자료형(int 등)일 경우
2. STL의 반복자와 함수 객체의 경우
   • 반복자와 함수 객체 구현시 반드시 아래 2가지 고려하여 만들어야함
   • 복사 효율을 높여야함
   • 복사 손실 문제에 노출되지 않도록 해야함

4. 사용자 타입은 가급적 참조자 전달을 사용하자

1. 위에서 언급한 상황을 제외하고는 참조자 전달을 사용하자!
2. 타입의 크기가 작으면 값에 의한 전달이 효율적일까?
   • 꼭 그렇지는 않다.
   • 멤버 데이터로 포인터 변수 하나만 가지고 있더라도, 복사 시에 해당 포인터 값을 모두 복사하기 때문에(깊은 복사) 비효율적일 수 있다.
3. 지금은 크기가 작더라도 나중에 커질 수 있다.

참고

1. Effective C++

0. 요약

1. 클래스 설계는 타입 설계와 같다
   • 아래 내용들을 깊게 고민하고 질문하자

1. 클래스 설계는 새로운 타입을 정의한다고 생각하자

1. 함수와 연산자를 오버로딩
2. 메모리 할당 및 해제를 제어
3. 객체 초기화 및 종료를 처리하는 작업 정의

2. 효과적인 클래스 설계를 위한 질문들

1. 새로 정의한 타입의 객체 생성 및 소멸은 어떻게 이루어져야 하는가?

   • 이 부분에 따라 클래스 생성자/소멸자의 설계가 바뀜
   • 메모리 할당 함수를 직접 작성할 경우 설계에 영향을 미침

2. 객체 초기화는 객체 대입과 어떻게 달라야 하는가?

   • 생성자와 대입 연산자의 동작 및 둘 사이의 차이점을 결정
   • 초기화와 대입을 헷갈리지 말자!

3. 새로운 타입으로 만든 객체가 값에 의해 전달되는 경우에 어떤 의미를 줄 것인가?

   • 값에 의한 전달을 구현하는 쪽은 복사 생성자라는 점을 기억하자

4. 새로운 타입이 가질 수 있는 적법한 값에 대한 제약은 무엇으로 잡을 것인가?

   • 클래스 데이터 멤버 몇 가지 조합은 반드시 유효해야함
   • 이런 조합을 불변속성이라고 하며, 클래스 차원에서 지켜줘야함
   • 불변 속성에 따라 멤버 함수 안에서 해야할 에러 점검 루틴 결정
   • 불변 속성에 따라 생성자, 대입 연산자, setter 함수 결정
   • 불변 속성은 함수가 발생시키는 예외에도 영향을 미침

5. 기존의 클래스 상속 계통망에 맞출 것인가?

   • 이미 존재하는 클래스를 상속받아 설계시 이들 클래스에 의해 제약을 받음
   • 멤버 함수의 가상 여부가 가장 큰 요인
   • 내가 만든 클래스를 다른 클래스에서 상속받을 수 있게 한다면, 가상 함수 여부 결정이 필요함

6. 어떤 종류의 타입 변환을 허용할 것인가?

   • 새로운 클래스와 다른 타입간의 변환의 정의가 있어야함
   • 암시적으로 변환하길 원한다면, 타입 연산자 오버로딩 필요
   • 아니면, non-explicit 생성자를 T2 클래스에 넣어야함
   • 명싲거으로 변환하길 원한다면, 변환을 맡는 함수를 만들자
   • 이때 타입 변환 연산자 또는 non-explicit 생성자를 만들지 말자

7. 어떤 연산자와 함수를 두어야 의미가 있을까?

   • 클래스 안에 선언할 함수가 여기서 결정

8. 표준 함수들 중 어떤 것을 허용하지 말 것인가?

   • private로 선언해야 하는 함수를 결정

9. 새로운 타입의 멤버에 대한 접근권한을 어느 쪽에 줄 것인가?

   • 클래스 멤버에 대한 public, protected, private 영역 결정
   • friend로 만들어야할 클래스 및 함수를 결정

10. 선언되지 않은 인터페이스로 무엇을 둘 것인가?

    • 만들 타입이 제공할 보장이 어떤 종류인가에 대한 질문
    • 보장할 수 있는 부분은 수행 성능 및 예외 안전성 그리고 자원 사용
    • 보장하겠다고 결정한 결과는 클래스 구현에 있어 제약으로 작용

11. 새로 만드는 타입이 얼마나 일반적인가?

    • 새로 만드는 것은 하나의 타입이 아니라 동일 계열의 타입군일 수 있다.
    • 그렇다면, 새로운 클래스를 만드는 것이 아니라, 새로운 클래스 템플릿을 정의해야 한다!

12. 정말로 꼭 필요한 타입인가?

    • 기존의 클래스에서 기능 몇 개가 아쉽다면, 상속 받지 마라
    • 간단하게 비멤버 함수 또는 템플릿을 정의하자!

참고

1. Effective C++

0. 요약

1. 인터페이스를 잘못 사용하지 못하도록 고민하자!!
   • 사용자가 저지를만한 실수를 생각하자
   • 새로운 타입을 들이고, 제약을 넣어 실수를 방지하자
2. 특별한 이유가 없다면 기본 타입처럼 사용자 타입을 구현하자
3. 일관성 있는 인터페이스를 제공하자
4. 스마트 포인터를 써서 사용자 오류를 방지하자

1. 인터페이스를 잘 못 사용하지 못하도록 하자

1. 사용자가 저지를만한 실수를 미리 생각하자!
   • ex) 날짜를 나타내는 클래스
   • 매개 변수를 잘 못 넣을 수 있음

class Date{
public:
  Date(int month, int day, int year);
};

Date d(30, 3, 1995) ; // 3과 30을 잘못씀
Date d(3, 40, 1995); // 30을 넣어야했는데 오타로 40..

2. 새로운 타입을 들여와 인터페이스를 강화하자!
   • 일, 월, 연을 구분하는 랩퍼 타입을 만들자.
   • 이 타입을 Date 생성자 안에 두자.

// 일 타입
struct Day{
   explicit Day(int d) : val(d) {}
   int val;
};

// 월 타입
struct Month{
   explicit Month(int m) : val(m) {}
   int val;
}

// 년 타입
struct Year {
   explicit Year(int y) : val(y) {}
   int val;
}

// Date 클래스 재정의
class Date{
public:
  Date(const Month& m, const Day& d, const Year& y);
};
Date d(Month(3), Day(30), Year(1995));

3. 새로운 타입에 제약을 넣어 오류를 방지하자!
   • 월은 12개 값만 가지므로, 제약을 주자

class Month{
public:
   static Month Jan() {return Month(1);}
   ...
   static Month Dec() {return Month(12);}
private:
  explicit Month(int m);
};

Date d(Month::Mar(), Day(30), Year(1995));

4. 특별한 이유가 없다면, 사용자 정의 타입은 기본 제공 타입처럼 동작하게 하자!

   • 항목 3의 if(a*b = c) 의 예제 참고
   • operator*의 반환타입을 const로 한정하여, 사용자 실수로 인한 c 대입 방지 가능

5. 일관성 있는 인터페이스를 제공하자

   • STL 컨테이너는 대체로 일관성이 있어서 사용하기 편리하다.
   • ex) STL 컨테이너는 size란 멤버 함수를 공통적으로 제공한다.
   • length, size, count 등 혼용하면 헷갈린다.

2. 스마트 포인터 사용

1. 사용자가 신경쓰지 않도록 하자(외우지 않도록)
   • Factory 함수에서 포인터를 반환할 때 shared_ptr을 반환하여 메모리 누수 문제를 해결하자.

Investment* createInvestment(); // (X)
std::shared_ptr<Investment> createInvestment(); // (O)

2. 스마트 포인터의 삭제자를 활용하자
   • Investment* 포인터를 직접 삭제하지 않고, 별도 삭제자를 통해 삭제하자
   • 하지만 별도 삭제자를 사용하지 않고 직접 delete를 할 가능성이 있다.
   • 또한 실수로 delete를 하고, 삭제자도 호출 할 수도 있다.
   • 아래와 같이 create할 때 삭제자가 포함된 shared_ptr을 반환하도록 구현

std::shared_ptr<Investment> createInvestment(){
// 방법 1. 포인터를 null ptr로 초기화 하고 나중에 대입하는 방석
   std::shared<Investment> retVal(static_cast<Investment*>(0), getRidOfInvestment);

// 방법 2. 실제 객체 포인터를 바로 생성자에 넘기는 방법
   std::shared_ptr<Investment> retVal(new Investment, getRidOfInvestment);

   retVal = ...;
   return retVal;
}

3. shared_ptr은 '교차DLL 문제' 를 방지한다.
   • 교차 DLL 문제 : 어떤 DLL에서 객체를 생성하고, 다른 DLL에서 소멸하는 문제
   • 객체 생성/삭제가 서로 다른 DLL에서 호출될 때 발생
   • shared_ptr은 생성된 DLL과 동일한 DLL에서 delete를 사용하도록 삭제자가 만들어져 있어서 방지 가능

// 아래 함수가 반환하는 shared_ptr은 다른 DLL 사이에 이리저리 넘겨져도 교차 DLL 문제를 걱정하지 않아도 된다.
std::shareD_ptr<Investment> createInvestment(){
   return std::shared_ptr<Investment>(new Stock);
}

참고

1. Effective C++

0. 요약

1. new로 생성한 객체를 스마트포인터에 저장하는 코드를 별도의 한 문장으로 만들자
   • shared_ptr pw(new xxx);
2. 이유
   • new 실행과 해당 자원을 스마트포인터 생성자로 전달하는 사이에 예외 발생시 자원 누수 발생!

1. 문제 사항

1. 가정
   • 처리 우선 순위를 알려주는 함수 존재
   • 동적 할당한 Widget 객체에 대해 어떤 우선순위에 따라 처리를 적요하는 함수 존재

int priority();
void processWidget(std::shared_ptr<Widget> pw, int priority);

// processWidget을 사용
processWidget(new Widget, proiority());

2. 위의 processWidget() 함수가 동작할까?
   • shared_ptr의 생성자는 explicit로 선언되어 있음
   • new Widget으로 만들어진 포인터가 shared_ptr 타입으로 암시적 변환이 되지 않음!
   • 아래와 같이 명시적으로 생성 후 호출하도록 변경

processWidget(std::shared_ptr<Widget>(new Widget), priority());

3. 하지만 위의 문장은 자원이 누수될 가능성이 존재!
   • 위의 한 문장을 수행전 매개 변수 인자를 평가하는 순서 가짐
   • 본 예시에서는 3가지 단계를 거침
   • "new Widget" 을 실행 => shared_ptr 생성자를 호출 => priority() 함수 호출
   • 문제는 3개의 단계의 순서가 컴파일러 마다 다름!
4. 만약 호출 순서가 아래와 같고, priority 에서 예외가 발생했다면?
   • "new Widget" 실행
   • priority() 실행
   • shared_ptr 생성자 호출
5. new Widget으로 할당된 메모리가 해제되지 않아 누수 발생!

2. 해결 방법

1. Widget를 생성해서 RAII에 저장하는 코드를 별도 한 문장으로 만들자!
2. 그리고, 나머지 문장을 실행하자!

std::shared_ptr<Widget> pw(new Widget);
processWidget(pw, priority());

참고

1. Effective C++