2W-6-2

JUSTICE_DER·2023년 9월 9일
0

⏲ CPP - 코딩테스트

목록 보기
34/41

1. 다음 순열

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

구현

  • 수열의 순서를 생성하는 방법을 알아야만 풀 수 있다.
    실제로 규칙을 찾기엔 굉장히 복잡한데, 암기하는게 맞는 것 같고,
    CPP에는 이미 algorithm에 관련 함수가 구현되어있다.
    next_permutation(v.begin(), v.end()
    prev_permutation(v.begin(), v.end()
    next 작동 방식은, 다음 수열이 있다면 true를 반환하고,
    v에 저장된 1234라는 어떤 순서를 다음 수열인 1243으로 바꾸어준다.
    v 내부의 원소들의 순서가 직접 바뀌게 되고,
    바로 iterator로 출력하면 다음 수열이 된다.

문제점
1. 외우자..
https://guiyum.tistory.com/29
2. 그냥 DFS하려고 하면 안되는 이유가, 10000000개로, 1억을 넘어간다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> my_next_permutation(vector<int> vv, int n);
vector<int> v;
int N;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        v.push_back(num);
    }

    /*
    if(next_permutation(v.begin(), v.end()))
    {
        for(int i=0;i<N;i++)
        {
            cout << v[i] << ' ';
        }
    }
    
    else
    {
        cout << -1;
    }
    */
   
    v = my_next_permutation(v, N);
    for (int i = 0; i < N; i++)
    {
        cout << v[i] << ' ';
    }

    

    return 0;
}

vector<int> my_next_permutation(vector<int> a, int n)
{
    vector<int> vv = a;

    int i = n - 1;                      // 인덱스는 0~n-1이기 때문.
    while (i > 0 && vv[i - 1] >= vv[i]) // 5 4 3 2 1 이렇게 내림차순인걸 확인
    {
        i -= 1;
    }
    if (i <= 0)
    {
        // return false;
    }

    int j = n - 1;
    while (vv[i - 1] >= vv[j]) // 내림차순 바로 이전 수보다 첫 큰 j를 찾기
    {
        j -= 1;
    }

    swap(vv[i - 1], vv[j]); // 그 둘을 swap하면 다음 순서가 됨

    j = n - 1;
    while (i < j)
    {
        swap(vv[i], vv[j]);
        i += 1;
        j -= 1;
    }

    return vv;
}

2. 이전 순열

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

구현

3. 모든 순열

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

구현

  • N이 주어졌을 때, N까지의 수로 가능한 수열들을 만드는 문제
  • NM문제에서 N과 M이 동일한 수로 주어졌다는 것 외에
    NM과 알고리즘상 다를게 전혀 없었다.

문제점

  • 없.
int arr[9];
bool visited[9];

void DFS(int n)
{
    if(n==N)
    {
        for(int i=0;i<N;i++)
        {
            cout << arr[i] << " ";
        }
        cout << "\n";
    }
    else
    {
        for(int i=1;i<=N;i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                arr[n] = i;
                DFS(n+1);
                visited[i] = false;
            }
        }
    }
}

4. 차이를 최대로

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

구현

  • NM문제와 비슷하다.
  • 이번에는 결과에 arr[N]을 사용하는 것이 아니라,
    vector를 사용하여 진행해보았다.
    vector를 사용하므로 int n이라는 매개변수가 필요없었다.

문제점
1. 구현하기 헷갈렸다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int result = 0;
vector<int> v;
int arr[9];
bool visited[9] = {
    0,
};

void DFS() // int n을 받지 않을거면 vector를 사용하면 편리
{
    // 모든 원소를 다 채웠으면, 합을 확인, 최대면 갱신
    if (v.size() == N)
    {
        int tmp = 0;
        for (int i = 0; i < N - 1; i++)
        {
            tmp += abs(v[i + 1] - v[i]);
        }
        result = max(result, tmp);
        return;
    }
    else
    {
        for (int i = 0; i < N; i++)
        { 
            if (!visited[i])
            {
                visited[i] = true;
                v.push_back(arr[i]);
                DFS();
                v.pop_back();       // vector를 사용한 dfs는 이렇게 한다.
                visited[i] = false;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }

    DFS();

    cout << result; //result를 여기에 적어야만 한다.

    return 0;
}

5. 외판원 순회2

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

구현

  • NM 문제처럼 DFS를 돌려고 했고,
    vector를 이용하여, DFS에 매개변수가 없도록 하였다.
  • v가 N개의 모든 도시를 방문했을 경우,
    마지막 v[N-1]인덱스의 값에서 v[0]인덱스의 값으로 가는
    거리를 더하여
    해당 값이 최소인 것을 구하려고 하였다.
  • 이 과정에서 거리의 값이 0인 것을 처리하는 것이 미숙했는지,
    예제는 맞는데 자꾸 틀렸다고 나왔다.

문제점
1. 거리 0에 주목하고, 내 아이디어대로 다시 구현해본다.

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

int N;
int w[10][10];
bool visited[10];
vector<int> v;
int result = 100000000;

void DFS()
{
    if(v.size() == N)
    {
        //v.push_back(v[0]);  // 순회해야 하므로 처음 값 추가

        int tmp = 0;
        
        cout << v[0] << " : ";
        for(int i=0;i<N-1;i++)
        {
            cout << v[i+1] << " : ";
            if(w[v[i]][v[i+1]] != 0)    // 경로가 있다면,
            {
                tmp += w[v[i]][v[i+1]];
            }
            else
            {
                return; // 경로가 없다면, result를 갱신하지 않고 바로 return
            }            
        }
        
        // 순회해야 하므로 
        if(w[N-1][v[0]]!=0)
        {
            tmp+=w[v[N-1]][v[0]];
        }
        else
        {
            return;
        }

        cout << "= " << tmp << " \n ";
        result = min(result, tmp);
        return;
    }
    else
    {
        for(int i=0;i<N;i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                v.push_back(i);
                DFS();
                v.pop_back();
                visited[i] = false;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            cin >> w[i][j];
        }
    }

    DFS();

    cout << result;

    return 0;   
}

6. 로또

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

구현

  • 랜덤길이의 수열을 주고, 6개만 뽑으면 되는 문제,
    오름차순이고, 순서가 중요했다.
  • NM문제에서 순서가 필요할 시 int num을 추가한 방법을 사용.
  • vector는 입력값인 arr, DFS 답 저장용인 v를 사용하였다.
  • v는 인덱스 값을 저장하는 용도이다.

문제점
1. % 올라가는 것 없이 내자마자 맞았다고 뜨는 경우는 처음봤다.

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

int N;
vector<int> arr;
vector<int> v;
bool visited[13] = {0, };

void DFS(int num)
{
    if(v.size()==6)
    {
        for(int i=0;i<6;i++)
        {
            cout << arr[v[i]] << " "; 
        }
        cout << "\n";
    }
    else
    {
        for(int i=num;i<N;i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                v.push_back(i);
                DFS(i);
                v.pop_back();
                visited[i] = false;
            }
        } 
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    while(true)
    {
        cin >> N;
        arr.clear();

        if(N==0)
        {
            break;
        }

        for(int i=0;i<N;i++)
        {
            int num;
            cin >> num;

            arr.push_back(num);
        }
        
        DFS(0);

        cout << "\n";
    }
    

    return 0;   
}

7. 암호만들기

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

구현

  • 주어진 글자에서 글자 순서대로 비밀번호를 만든다.
  • NM문제에 int n을 추가하여 순서를 고정시키는 유형이었고,
  • 모음1, 자음2 이상이 있어야만 한다는 규칙을 위해서,
    checkmoza라는 함수로 확인하고 true/false를 리턴하도록 하였다.
  • 추가 조건 외에는 NM문제+순서 문제라고 봐도 무방

문제점
1. 집중력이 떨어졌는지 이상한 실수를 했다.
for (int i = num; i < M; i++)
왜 M대신에 6을 적었던 걸까

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

int N, M;

vector<int> v;
vector<char> arr;
bool visited[16];

// 모음 자음 조건이 맞는지 체크
bool checkmoza()
{
    int mo = 0, ja = 0;
    for (int i = 0; i < N; i++)
    {
        char ch = arr[v[i]];

        if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u')
        {
            mo++;
        }
        else
        {
            ja++;
        }
    }
    if (mo >= 1 && ja >= 2)
    {
        return true;
    }
    else
    {
        return false;
    }
}

void DFS(int num)
{               
    if (v.size() == N)
    {
        if (checkmoza())
        {
            for (int i = 0; i < N; i++)
            {
                cout << arr[v[i]];
            }
            cout << "\n";
        }
        else
        {
            return;
        }
    }
    else
    {
        for (int i = num; i < M; i++)   // M까지인데 6으로 써놨어서..
        {
            if (!visited[i])
            {
                visited[i] = true;
                v.push_back(i);
                DFS(i);
                v.pop_back();
                visited[i] = false;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    for (int i = 0; i < M; i++)
    {
        char c;
        cin >> c;
        arr.push_back(c);
    }

    sort(arr.begin(), arr.end());

    /*
    for (auto i : arr)
    {
        cout << i << " ";
    }
    cout << "\n";
    */

    DFS(0);

    return 0;
}

8. 퇴사 - 풀었던거 찾아보기

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

구현

  • 골드에서 똑같은 문제를 풀었었던 문제고,
    똑같이 time을 사용하여 역순으로 ++ 했었는데,
    그 방법을 사용하면 매우 복잡해진다.
  • 역순은 맞고, 아래의 식을 사용하는게 베스트.
    d[i] = max(d[i+1], p[i] + d[i+t[i]])

문제점
1. 퇴사 문제 유형은 역순으로 하여 time을 쓸 생각을 하지 말고,
역순으로 d[i]를 구해나가는 것을 생각하자.

#include <iostream>
using namespace std;

    // 초기화 및 선언
    int t[16] = {
        0,
    };
    int p[16] = {
        0,
    };
    int d[16] = {
        0,
    };

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;


    // 입력값
    for (int i = 1; i <= N; i++)
    {
        cin >> t[i];
        cin >> p[i];
    }

    // 핵심
    for (int i = N; i >= 1; i--)
    {   
        if(i+t[i] > N+1)    // 시간 상 할 수 없는 일이라면,
        {
            d[i] = d[i+1];  // 다음날의 일을 하도록 함.
        }
        else
        {
            d[i] = max(d[i+1], p[i] + d[i+t[i]]);   
            // 다음날의 일과, 다음시간의 일을 더한 값 중 큰 값을 현재 값으로 둠.
        }
    }

    cout << d[1];
    return 0;
}
profile
JUSTICE_DER
Time Waits for No One
이전 포스트

2W-6

다음 포스트

2W-8

0개의 댓글