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

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

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

문제

풀이

15651번 N과 M (3)에서의 코드에다가  15650번 N과 M (2)에서 사용했던 for문의 i값을 재귀함수의 매개변수로 넘겨주는 방식을  합치면 풀이가 가능하다.

잘 이해가 안갈 경우, 이전 글과의 코드 차이점을 보면 이해가 가능할 것이다.

코드

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int num, int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = num; i <= n; i++)
    {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i,cnt+1);
            visited[i] = false;
    }
}

int main() {
    cin >> n >> m;
    dfs(1,0);
}

평가

N과 M 4문제는 각각 순열, 조합을 dfs를 활용하여 푸는 방법을 배울 수 있는 문제이다.

백트래킹의 기본인 재귀 설계에 대해 짚고 넘어가면 좋을 것 같다.

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

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

문제

풀이

순열을 구했던 15649번 문제에서 dfs에서 for문안에 if(!visited[i])를 넣어뒀던것만 제거하면 15651번 문제의 조건을 만족하는 출력값을 얻을 수 있다.

코드

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt+1);
            visited[i] = false;
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

평가

사실상 N과 M(1)에서 자기 자신을 다시 뽑을 수 있도록하는 규칙만 추가된 문제이다.

if(!visited[i])를 통해, 만약 1이라는 숫자가 뽑혀있다면 다음 원소로 1을 뽑지 않도록 했던 조건문을 제거해주면 15651번의 해답을 얻을 수 있다.

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

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

문제

풀이

dfs를 활용한 조합문제이다.

조합문제를 풀기 위해서는 간단하다. 

재귀 호출에서, 현재 뽑은 원소의 이전값들은 고려하지 않게끔, for문의 i값을 함께 넘겨주면 된다.

예를 들어, 1 2 3 4 5에서 3개를 뽑을 경우,

1 2 3

1 2 4 

1 2 5

1 3 4

1 3 5

1 4 5

이런식으로, 두번째 숫자는 반드시 첫번째 숫자보다 크도록, 세번째 숫자는 반드시 두번째 숫자보다 크도록 하면 된다.

이해가 잘 안된다면 코드를 보자.

코드

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int num, int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = num; i <= n; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i+1,cnt+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(1,0);
}

평가

15649번이 dfs를 통한 순열 구하기였다면, 이번 문제는 dfs를 통한 조합 구하기라고 할 수 있다.

for문의 index값을 함께 재귀함수의 인자로 넘겨주면 앞에서 이미 찾은 조합은 다시 뽑지 않도록 만들 수 있다.

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

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

문제

풀이

조합의 개수를 구하는 문제이므로, dfs를 활용하여 풀이가 가능하다.

각 숫자는 순열에서 딱 한번만 사용되므로, 각 숫자를 인덱스로 가지는 bool형 배열인 visited를 선언하고,

해당 숫자를 뽑았는지 유무를 저장한다. 

숫자를 앞에서부터 한개씩 뽑아가면서 visited가 M개만큼 true가 되면, 출력을 해주는 재귀함수를 활용하면 된다.

코드

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

평가

dfs를 활용하여 순열을 구할 수 있다는 것을 알아두고 dfs를 통한 백트래킹 방식을 이해해두면 좋을 것 같다.

또한 재귀적으로 함수를 어떻게 작성해야 백트래킹이 가능한지를 충분히 고려해야 풀이가 가능한 문제이다.

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

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

문제

풀이

if문으로 가장 싼 버거와 가장 싼 음료를 선택한 후 합친값에서 50을 빼주면 되는 문제이다.

최초 min값을 9999로 설정하고, min보다 작은 값이 들어오면 변경해주는 식으로 최소값을 찾으면 된다.

코드

#include <iostream>
using namespace std;

int main() {
    int burgers[3];
    int beverages[2];
    int cheapest_burger = 9999;
    int cheapest_beverage = 9999;
    for(int i = 0; i < 3; i++) {
        cin >> burgers[i];
        if(burgers[i] < cheapest_burger)
            cheapest_burger = burgers[i];
    }
    for(int i = 0; i < 2; i++)
    {
        cin >> beverages[i];
        if(beverages[i] < cheapest_beverage)
            cheapest_beverage = beverages[i];
    }
    cout << cheapest_beverage+ cheapest_burger - 50;
}

평가

if문 단계별로 풀어보기에 새로 추가된 문제이다.

if문을 활용하면 간단히 해결할 수 있다.

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

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

문제

풀이

원래의 순서를 손상시키지 않으면서 정렬하는것을 stable sort라고 한다.

본 문제는 C++의 sort처럼 algorithm 헤더에 들어있는 stable_sort를 통해서 풀이가 가능하다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int,string> a, pair<int,string> b)
{
    return a.first < b.first;
}
int main() {
    int num;
    cin >> num;
    pair<int,string> tmp;
    vector<pair<int,string>> arr;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }
    stable_sort(arr.begin(),arr.end(),compare);
    for(int i = 0; i < num; i++)
        cout << arr[i].first << ' ' << arr[i].second << '\n';
}

평가

stable_sort라는 STL 함수가 있다는것을 알고 있다면 간단히 풀이가 가능하다.

만약 직접구현하려고하면 버블소트나 힙소트등의 stable sort류 정렬 알고리즘을 사용하면 된다.

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

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

문제

풀이

string 벡터를 선언하고, string의 비교 조건을 str.length() 순으로, 만약 같을 경우엔 사전순으로 비교하게끔 하는 compare 함수를 만들어서 sort함수로 정렬하면 풀이가 가능하다.

또한, 출력부에서 만약 동일한값이 이미 출력됬을경우엔 출력하지 않도록 설정해주면 풀이가 가능하다.

코드

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(string a, string b) {
    int i = 0;
    if(a.length() == b.length())
    {
        for(int i = 0; i < a.length(); i++)
        {
            if(a[i] != b[i])
                return a[i] < b[i];
        }
    }
    return a.length() < b.length();
}
int main() {
    int num;
    string tmp;
    cin >> num;
    vector<string> arr;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(),arr.end(),compare);
    cout << arr[0] << '\n';
    for(int i = 1; i < num; i++)
    {
        if(arr[i-1] == arr[i])
            continue;
        cout << arr[i] << '\n';
    }
}

평가

STL Sort를 사용하되, compare함수를 얼마나 자유자재로 사용할 수 있는가를 묻는 문제인 듯하다.

compare함수를 필요에 맞게 바꾸는 연습을 하고 넘어가도록 하자.

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

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

문제

풀이

이번에는 페어에서 second를 기준으로 정렬하는 문제이다.

이런 경우에는 기본 sort를 쓰지 않고 compare함수를 정의해서 풀이하면 된다.

코드

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;
bool compare(pair<long,long> a, pair<long,long> b)
{

    if(a.second == b.second)
        return a.first < b.first;
    else
        return a.second < b.second;
}
int main() {
    int num;
    cin >> num;
    vector<pair<long,long>> arr;
    pair<long,long> tmp;
    for(int i = 0; i < num; i++)
    {
        cin >> tmp.first >> tmp.second;
        arr.push_back(tmp);
    }
    sort(arr.begin(),arr.end(),compare);
    for(int i = 0; i < num; i++)
        cout << arr[i].first << ' ' << arr[i].second << '\n';
}

평가

STL의 sort함수는 compare라는 비교 함수를 직접 인자로 전달할 수 있기 때문에, 

필요에 따라서 수정하여 sort를 진행할 수 있다는 사실을 짚고 넘어가면 될 것 같다.

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

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

문제

풀이

utility 헤더파일에 존재하는 pair 자료형을 활용하여 sort를 진행하면 되는 문제이다.

페어의 경우 first가 같으면 second로 비교하게끔 이미 sort함수에서 구현이 되어 있기 때문에 STL의 sort를 활용하면 된다.

코드

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

평가

STL의 sort함수가 pair 자료형에서 완벽하게 동작한다는 사실을 알면 매우 금방 풀 수 있는 문제이다.

좌표의 경우 무조건 pair 자료형을 쓰는게 편하다는 사실을 알고 넘어가자.

백준 - 단계별로 풀어보기 [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에서 내림차순을 어떻게 처리해야할지에 대한 스킬과,

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