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

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

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

문제

풀이

N-Queen 문제는 백트래킹의 가장 대표적인 예제로서, 퀸의 특성상 체스판 한 행당 한 개의 퀸만 존재할 수 있다는 것을 전제로 깔아두고 시작하는 것이 좋다. 즉 이 문제를 풀기 위해서 N*N짜리 배열을 직접 만들 필요 없이,

크기가 N인 일차원 배열을 만든 후, 각 열에 몇번째 행의 퀸이 있는지를 저장하면 된다.

예를 들어  N = 4일때,

일차원 배열 col [] 에 이런식으로 저장하면 된다.

col[0] = 0번째 열에 존재하는건 1행의 퀸이므로 1 저장

col[1] = 1번째 열에 존재하는건 3행의 퀸이므로 3 저장

col[2] = 2번째 열에 존재하는건 0행의 퀸이므로 0 저장

col[3] = 3번째 열에 존재하는건 2행의 퀸이므로 2 저장

그후 한 행씩 퀸을 배치해가면서 총 배치 행수가 N이 되면 조건을 만족하는 경우의 수를 1개씩 늘려주는 방식으로 백트래킹을 진행할 수 있다.

따라서 재귀함수의 매개변수에는 현재 몇번째 행을 채우고 있는지를 기록하는 Level이라는 인자를 사용해야 한다.

먼저 이 문제에서 체크해야하는것은, 임의로 배치한 퀸이 다른 퀸과 같은 행 또는 같은 열에 있는가를 살펴야하며, 대각선에 위치해있는가를 살펴야한다.

이 때, 같은 행과 열에 있는지 확인하는 방법은 매우 간단하지만, 대각선에 위치해있는지를 찾는 방식이 다소 까다로울 수 있다. 먼저 기본적으로 대각선에 존재하는 좌표일 경우, (X, Y)의 대각선에 위치한 좌표 (A, B)에서 반드시 X-A = Y-B를 만족한다.

예를 들어 (0 , 1)을 기준으로 했을때, 대각선에 있는 점들 (1, 2) (2, 3) 은 반드시 (0 - 1) = (1 - 2) = -1, (0 - 2) = (1 - 3) = -2를 만족한다는 것이다. 

따라서 우리가 정의한 col이라는 1차원 배열의 정의에 따라서 X좌표와 Y좌표의 차이가 일정한 값을 가질 경우 해당 퀸과 대각선에 있다고 판단할 수 있다. 

이해가 잘 안간다면 코드를 보면 이해할 수 있을 것이다.

코드

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

int col[MAX];
int N, total = 0;

bool check(int level)
{
    for(int i = 0; i < level; i++)
        if(col[i] == col[level] || abs(col[level] - col[i]) == level - i)// 대각선이거나 같은 라인
            return false;
        //col[i]가 의미하는 것이 X좌표, i가 의미하는것이 Y좌표이므로 차이가 일정하다면 대각선에 있다고 볼 수 있다.
    return true;
}

void nqueen(int x)
{
    if(x == N)
        total++;
    else
    {
        for(int i = 0; i < N; i++)
        {
            col[x] = i; // 해당 위치에 퀸을 배치
            if(check(x)) // 유효하다면 다음행의 퀸 배치, 유효하지않다면 다른 위치로 퀸 배치 변경
                nqueen(x+1);
        }
    }
}
int main() {
    cin >> N;
    nqueen(0);
    cout << total;
}

평가

가장 기본적인 예제이지만 난이도가 쉽지 않은 문제이다.

백트래킹에 대한 충분한 이해가 있어야 풀이가 가능하다.

또한, 대각선을 판별하는 식을 얼마나 효율적으로 작성할 수 있느냐에 따라서 실행시간이 크게 달라지기 때문에, 시간초과가 발생하지 않기 위해서는 2차원배열보다는 단순히 1차원배열을 활용한 진위판별을 하는 것이 필요한 문제이다.

백준 - 단계별로 풀어보기 [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 자료형을 쓰는게 편하다는 사실을 알고 넘어가자.