'전체 글'에 해당되는 글 186건

백준 - 단계별로 풀어보기 [1427] 

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

문제

풀이

입력받은 N값을 to_string 함수를 통해서 int형에서 string형으로 변환해준뒤,

소팅을 진행한다. 이때 내림차순으로 정렬하라고 하였으므로 compare 함수를 내림차순에 맞게 정의하여 sort의 인자로 전달한다.

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool compare(char a,char b)
{
    return a > b;
}
int main() {
    string a;
    int N;
    cin >> N;
    a = to_string(N);
    sort(a.begin(),a.end(),compare);
    cout << a;
}

평가

sort에서 내림차순을 어떻게 처리해야할지에 대한 스킬과,

숫자를 문자열로 어떻게 받아서 자리수를 처리할건지에 대한 문제이다.

백준 - 단계별로 풀어보기 [2108] 

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

문제

풀이

입력을 받는 시점에 평균을 구할 수 있도록 sum이라는 변수에 값을 더해주고,

-4000~4000의 숫자가 몇번 나왔는지를 저장하는 배열인 numbers[8001]을 활용하여 어떤 숫자가 나오면 해당 인덱스의 값을 증가시켜준다.

그 후, 입력받은 숫자들의 벡터를 sort함수를 통해 정렬해주고, 중앙값을 구한다.

범위의 경우에는 이미 오름차순으로 벡터가 정렬되었으므로, 벡터의 back() 값에서 front()값을 빼면 범위가 완성된다.

최빈값의 경우 만약 나온 횟수가 같으면 두번째로 작은 수를 출력하라고 하였으므로, not_first라는 bool형 플래그값을 줘서 만약 나온 횟수가 같다면 두번째로 작은 값이 저장되도록 한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<int> arr;
int main() {
    int num,tmp,range,middle = 0,most_val,mean = 0;
    int most = -9999;
    int number[8001] = {0,};
    bool not_first = false;
    cin >> num;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp;
        arr.push_back(tmp);
        mean += tmp;
        number[tmp+4000]++;
    }
    sort(arr.begin(),arr.end());
    for(int i = 0; i < 8001; i++)
    {
        if(number[i] == 0)
            continue;
        if(number[i] == most)
        {
            if(not_first)
            {
                most_val = i - 4000;
                not_first = false;
            }
        }
        if(number[i] > most)
        {
            most = number[i];
            most_val = i - 4000;
            not_first = true;
        }
    }
    middle = arr[arr.size()/2];
    mean = round((float)mean / num);
    range = arr.back() - arr.front();
    cout << mean << '\n' << middle << '\n' << most_val << '\n' << range;
}

평가

최빈값이 여러 개 있을 경우 두번쨰로 작은 수를 출력하라는 예외조건때문에 다소 껄그러웠던 문제이다.

정답률은 27.07%로 낮은편이다.

백준 - 단계별로 풀어보기 [10989] 

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

문제

풀이

수의 개수의 최댓값이 10,000,000이기 때문에 시간 제한 2초를 만족시키기가 어렵다.

이 때, 문제에서 주어진 조건에 입력되는 수는 반드시 10000보다 작거나 같다고 하였으므로, 배열 전체를 정렬하기보다는

1부터 10000까지의 숫자가 각각 몇번 나오는지를 체크하고, 각 숫자를 횟수만큼 1부터 10000까지 순서대로 출력해주는 방식을 사용하기로 하였다.

코드

#include <cstdio>
#include <vector>
using namespace std;
int main() {
    int num,tmp;
    int count[10001] = {0,};
    scanf("%d",&num);

    for(int i = 0; i < num; i++)
    {
        scanf("%d",&tmp);
        count[tmp]++;
    }

    for(int i = 0; i < 10001; i++)
        for(int j = 0; j < count[i]; j++)
            printf("%d\n",i);
}

평가

주어진 수의 개수는 많은데, 입력받는 숫자의 경우의 수는 10000개밖에 안된다는 사실을 활용하여 시간을 단축시키는 것이 관건인 문제이다.

백준 - 단계별로 풀어보기 [2751] 

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

문제

풀이

이번 문제에서는 nlogn의 시간복잡도를 가지는 정렬 알고리즘을 사용해야 하기 때문에, 퀵 소트가 구현되어 있는 STL을 사용하면 된다.

sort()함수를 활용하면 오름차순 정렬이 가능하며 헤더파일은 #include <algorithm>을 통해 인클루드 할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int num,tmp;
    vector<int> a;
    cin >> num;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp;
        a.push_back(tmp);
    }
    sort(a.begin(),a.end());
    for(int i = 0; i < num; i++)
        cout << a[i] << '\n';
}

평가

C++에서 제공하는 STL의 sort함수를 활용하는 방법을 배울 수 있는 문제이다.

sort함수가 아닌 직접 구현 방식은 좀 더 난이도가 있을 듯 하다.

백준 - 단계별로 풀어보기 [2750] 

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

문제

풀이

버블 소트를 구현하여 풀이하면 풀 수 있는 문제이다.

코드

#include <iostream>
using namespace std;
int main() {
    int num;
    int arr[1000] = {0,};
    int tmp;
    cin >> num;
    for(int i = 0; i < num; i++)
        cin >> arr[i];
    for(int i = num; i > 1; i--)
        for(int j = 0; j+1 < i; j++)
            if(arr[j] > arr[j+1])
            {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
    for(int i = 0; i < num; i++)
        cout << arr[i] << '\n';
}

평가

버블 소트를 이해하고 있다면 쉽게 풀이가 가능한 문제이다.

백준 - 단계별로 풀어보기 [1436] 

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

문제

영화감독 숌은 작품 시리즈명을 1,2,3 순이 아닌 666, 1666, 2666,... 순으로 한다고 한다.

이 때 N번째 영화의 제목에 들어간 수를 구하는 문제이다.

풀이

숫자를 문자열로 변경시켜주고, 문자열 내에 '6'이 연속으로 3번 나오는 경우를 모두 찾아 N번째 작품의 제목에 들어간 수를 찾으면 되는 문제이다.

단, 많은 사람들이 실수하는 부분이 단순히 루프문 내에 '6'이 3번 연속으로 나오는지만 체크해서는 안된다는것이다.

예를 들어 아래와 같은 루프문이 있다고 했을 때,

    while(1)
    {
        target = to_string(i);
        for(int j = 0; j < target.length()-2; j++)
            if(target[j] == '6' && target[j+1] == '6' && target[j+2] == '6')
            {
                series++;
                if(series == N)
                    return i;
            }
        i++;
    }

for문 안에 break;문이 없기 때문에 문제가 발생할 수 있다.

예를 들어 숫자 '6666'의 경우, target[0],[1],[2]가 '6'이므로 series++;이 호출되고, 

target[1],[2],[3] 도 모두 '6'이므로 series++;이 또 실행되어 series가 2번 증가하게 된다.

'66666'의 경우엔 3번, '666666' 의 경우엔 4번이 증가할것이다.

따라서 루프문 안에 반드시 break 문을 넣어 한번 찾았으면 다음 숫자로 넘어가게끔 해야 한다.

코드

#include <iostream>
#include <string>
using namespace std;
int Findseries(int N)
{
    int i = 666;
    int series = 0;
    string target;
    while(1)
    {
        target = to_string(i);
        for(int j = 0; j < target.length()-2; j++)
            if(target[j] == '6' && target[j+1] == '6' && target[j+2] == '6')
            {
                series++;
                if(series == N)
                    return i;
                break;
            }
        i++;
    }
}
int main() {
    int N;
    cin >> N;
    cout << Findseries(N);
}

평가

6666등의 수에서 문제가 발생할 수 있다는 것을 자각하고, for문안에 break 문만 넣어준다면 쉽게 풀 수 있는 문제이다.

정답률은 46.237%로 다소 낮으며, C++이 아닌 다른 언어를 최적화되지 않은 코드로 사용할 경우 시간초과가 발생할 수도 있는 문제이다.

백준 - 단계별로 풀어보기 [7568] 

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

문제

전체 사람의 수 N과 각 사람의 몸무게와 키를 나타내는 값이 입력됬을 때,

자기보다 몸무게와 키가 크다면 자기보다 등치가 크다고 간주한다.

자신보다 덩치가 큰 사람이 K명이라면 K+1등이라고 할 때, 각 덩치의 등수를 출력하는 프로그램을 작성하는 문제이다.

풀이

몸무게와 키를 함께 저장하는 pair형식의 배열을 활용하여, 자신보다 큰 몸무게와 키를 가진 사람이 있을 경우 등수를 1등씩 밀어나가는 방식으로 풀이한다.

코드

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

int main() {
    int num;
    int rank = 1;
    pair<int,int> arr[50];
    cin >> num;
    for(int i = 0; i < num; i++)
        cin >> arr[i].first >> arr[i].second;
    for(int i = 0; i < num; i++)
    {
        for(int j = 0; j < num; j++)
            if(arr[i].first < arr[j].first && arr[i].second < arr[j].second)
                rank++;
        cout << rank << ' ';
        rank = 1;
    }
}

평가

pair방식을 활용하면 좀 더 풀이가 수월해지는 문제이다.

정답률 60%로 순탄한 문제이다.

백준 - 단계별로 풀어보기 [2231] 

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

문제

245의 분해합은 245+2+4+5 = 256일때, 245는 256의 생성자라고 정의한다.

어떤 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하는 문제이다.

풀이

1부터의 분해합을 구해서 최초로 N과 같은 수가 나오면 출력해주면 되는 문제이다.

이 때, 1부터의 분해합을 모두 구하면 비효율적이므로 조금이나마 연산횟수를 줄일 수 있도록 시작점을 구하는 코드를 추가했다.

N이 3자리 숫자일경우, 최소값인 100을 만족하는 숫자는 86이다. 

따라서 시작점을 N이 i자리 수일때, 10^(i-1) - 9 * (i-1)로 시작하도록 하였다.

N의 값이 커질수록 불필요한 연산의 수를 크게 줄일 수 있다.

코드

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

void numfind(int N)
{
    int tmp = N;
    int start,i,sum,tmp2 = 0;
    for(i = -1; tmp; i++)
        tmp /= 10;
    start = round(pow(10,i)) - 9*i;
    tmp = start;
    while(1)
    {
        sum = tmp;
        tmp2 = tmp;
        while(tmp2)
        {
            sum += tmp2 % 10;
            tmp2 /= 10;
        }
        if(sum == N)
        {
            cout << tmp;
            return;
        }
        if(tmp == N)
        {
            cout << '0';
            return;
        }
        tmp++;
    }
}
int main() {
    int N;
    cin >> N;
    numfind(N);
}

평가

Brute Force 문제는 단순히 모든 경우의수를 고려해주면 되므로,

문제의 코딩 난이도가 어렵지는 않다.

백준 - 단계별로 풀어보기 [2798] 

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

문제

카드의 개수 N과 타겟 값인 M을 첫 줄에 입력 받고,

둘째 줄에는 카드에 쓰여 있는 수가 입력될 때, 합이 M을 넘지 않도록 하는 카드 세장을 구해 이 카드들의 합을 출력하는 문제이다.

풀이

삼중 For문을 통해 카드 세장을 더한 값과 M과의 차이를 구하고, 

가장 차이가 작은 값의 합을 출력해주면 풀이가 가능한 문제이다.

분류가 Brute Force인 만큼, 모든 카드의 조합을 고려한 후 합이 가장 작은 값을 찾아주면 된다.

이 때, 동일한 값을 가지는 카드가 존재할 수 있으므로 DFS를 활용한 조합으로 접근하면 오답이 될 수 있다.

코드

#include <iostream>
#define MAX 100
using namespace std;

int main() {
    int num, target,goal,sum = 0;
    int min = 9999999;
    int arr[MAX] = {0, };
    cin >> num >> target;
    for(int i = 0; i < num; i++)
        cin >> arr[i];

    for(int i = 0; i < num-2; i++)
        for(int j = i+1; j < num-1; j++)
            for(int k = j+1; k < num; k++)
            {
                sum = arr[i]+arr[j]+arr[k];
                if(target - sum < min && target - sum >= 0) {
                    min = target - sum;
                    goal = sum;
                }
            }
    cout << goal;
}

평가

삼중 For문이 워낙 안좋은 풀이 방법이라는 생각 때문에, 다른 방식으로 풀어보려고 하였으나 본 문제에서는 삼중 For문으로 작성했을때 가장 간결한 코드를 가지는 듯하다.

백준 - 단계별로 풀어보기 [11729] 

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

문제

하노이의 탑 문제이다. 1번 장대에 순서대로 쌓여있는 N개의 원판을 어떻게 해야 최소한의 이동을 통해 3번 장대로 모두 이동시킬 수 있는지 최소 횟수와 수행 과정을 출력하는 문제이다.

풀이

정석적인 하노이 탑의 풀이 방법을 따르면 된다.

1번 장대에 있는 원판을 3번 장대로 모두 옮기기 위한 방법은 무조건 동일한 절차를 따른다.

먼저 n-1개의 원판을 3번 장대를 거쳐 2번 장대로 옮기고,

1번 장대에 있는 가장 큰 크기의 원판을 3번 장대로 옮긴 후,

2번 장대에 있는 n-1개의 원판을 1번 장대를 거쳐 3번 장대로 올려 놓는 과정이다. 

이를 그대로 알고리즘화하면 쉽게 풀 수 있다.

또한, 최소 횟수의 경우에는 하노이 탑에서 원판의 개수가 N일때, 

2^N - 1 의 횟수가 최소 횟수이다.

코드

#include <iostream>
using namespace std;
void hanoi(int n, int start, int to, int bypass)
{
    if(n == 1)
        printf("%d %d\n", start, to);
    else
    {
        hanoi(n-1,start,bypass,to);
        printf("%d %d\n",start,to);
        hanoi(n-1,bypass,to,start);
    }
}
int main() {
    int num;
    cin >> num;
    cout << (1<<num) -1 << "\n";
    hanoi(num,1,3,2);
}

1 << num 은 2^num 을 표현한 방식이다.

만약 해당 문제에서 pow(2,num)을 사용하였다면, double형을 활용하는 pow의 특성상 입력 최대값인 20이 입력되면 오차범위가 커져 틀렸습니다. 라는 메세지가 출력된다.

따라서 (int)pow(2,num); 을 활용하던가, 아니면 (1<<num) 같이 시프트 연산을 활용한 표현을 사용해야 한다.

평가

하노이의 탑에서 재귀적인 관계를 바로 찾을 수 있다면 금방 풀 수 있는 문제이다.

또한 함수의 매개변수에 from과 to외에도 어떤 장대를 지나쳐서 가는지에 대한 정보를 담는 bypass를 매개변수에 반드시 포함을 시켜야만 풀 수 있다.