문제

총 n개의 팀이 참가 -> 팀은 1번부터 n번까지 번호가 매겨져 있다.

올해는 인터넷 예선 본부에서는 최종 순위를 발표하지 않기로 했다. 그 대신에 작년에 비해서 상대적인 순위가 바뀐 팀의 목록만 발표하려고 한다. (작년에는 순위를 발표했다) 예를 들어, 작년에 팀 13이 팀 6 보다 순위가 높았는데, 올해 팀 6이 팀 13보다 순위가 높다면, (6, 13)을 발표할 것이다.

창영이는 이 정보만을 가지고 올해 최종 순위를 만들어보려고 한다. 하지만, 본부에서 발표한 정보를 가지고 확실한 올해 순위를 만들 수 없는 경우가 있을 수도 있고, 일관성이 없는 잘못된 정보일 수도 있다. 이 두 경우도 모두 찾아내야 한다.

입력

첫째 줄에는 테스트 케이스의 개수 (테스트 개수 ≤ 100)

• 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500)
• n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. -> 작년 순위
• 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000)
• 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이 여러 번 발표되는 경우는 없다.

출력

각 테스트 케이스에 대해 n개의 정수를 한 줄에 출력한다. 출력하는 숫자는 올해 순위이며, 1등팀부터 순서대로 출력한다. 만약, 확실한 순위를 찾을 수 없다면 "?"를 출력한다. 데이터에 일관성이 없어서 순위를 정할 수 없는 경우에는 "IMPOSSIBLE"을 출력한다.

풀이

순서대로 순위를 정렬한다는 점에서 위상정렬을 사용한다. 그러나 보통의 위상정렬과 다른점은 순위가 변동되기 때문에 이를 확인하는 방법이 있어야 한다는 점이다. -> 2차원 배열을 사용해서 작년 순위별로 저장한 후, 순위가 변동될 경우 반대로 바꿔준다. 또한 확실한 순위를 만들 수 없는 경우와 일관성이 없는 잘못된 경우도 찾아내야하는데, 사이클이 생기는 경우와 동일 진입차수가 여러개인 경우를 찾아내면 된다.

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

using namespace std;
int T,N,M;

int main(){
    cin>>T; //테스트 수

    for(int t=0;t < T; t++){
        cin>>N;
        int indegree[501]={0,}; //각 등수에 대한 진입차수 저장
        int arr[501]; //작년 순위 저장
        bool order[501][501]={false, }; //순위가 바뀌는 것을 확인하기 위해 자신보다 낮은 순위의 팀들 저장
        vector<int> result;
        int data;

        for(int i=0;i < N; i++){
            cin>>data;
            arr[i]=data;
            indegree[data]=i; //자신보다 낮은 순위를 모두 가리키도록 -> 1등: 진입차수 0, 2등:진입차수 1 ...
        }

        for(int i=0;i < N-1; i++){
            for(int j=i+1; j < N; j++){
                order[arr[i]][arr[j]]=true; //자신보다 등수가 낮은 팀 true
            }
        }

        cin>>M;
        int a,b;
        //순위 변동
        for(int i=0;i < M; i++){
            cin>>a>>b;
            if(order[a][b]){ //a가 b보다 등수가 높았던 경우
                indegree[a]++;
                indegree[b]--;
                order[a][b]=false;
                order[b][a]=true;
            }else{ //a가 b보다 등수가 낮았던 경우
                indegree[a]--;
                indegree[b]++;
                order[a][b]=true;
                order[b][a]=false;
            }

        }

        queue<int> q;
        for(int i=1;i<=N;i++){
            if(indegree[i]==0){ //진입차수가 0인경우 큐에 넣기
                q.push(i);
            }
        }

        bool cycle=false, check=true;

        for(int i=0;i<N;i++){ //위상정렬
            if(q.empty()){ //사이클이 발생한 경우
                cycle=true;
                break;
            }
            if(q.size()>=2){ //동일한 등수의 팀이 여러개인 경우
                check=false;
                break;
            }

            int cur=q.front();
            result.push_back(cur);
            q.pop();

            for(int j=1;j<=N;j++){
                if(order[cur][j]==true){
                    indegree[j]--;
                    if(indegree[j]==0){
                        q.push(j);
                    }
                }
            }
        }

        if(cycle==true){
            cout<<"IMPOSSIBLE\n";
        }
        else if(check==false){
            cout<<"?\n";
        }else{
            for(int i=0;i<N;i++){
                cout<<result[i]<<" ";
            }
            cout<<"\n";
        }


    }

    return 0;
}

이것이 취업을 위한 코딩테스트다 p.382

설명링크

못생긴 수란 2,3,5만을 소인수로 가지는 수 1은 못생긴 수라 가정 -> {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...}

입력

N 입력 (1<=N<=1000)

출력

N번째 못생긴 수 출력

풀이

DP문제는 아직 풀어도 풀어도 익숙해지지 않는 것 같다ㅠㅠ

이것이 코딩테스트다 p.570쪽 참고 -> C++버전으로 구현 처음에는 2,3,5 각각의 수에 계속해서 2,3,5를 곱하는 방식으로 풀었는데, 알고보니 각각의 index(i2,i3,i5)를 증가시키면서 이전에 배열에 포함된 못생긴 수에 2,3,5를 구해서 작은값 순서대로 넣는 방식으로 구현

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;


    int ugly[1001];
    ugly[0] = 1;

    int i2 = 1, i3 = 1, i5 = 1;
    int two = 2, three = 3, five = 5;

    for(int i=1;i<N;i++){
        //2,3,5의 합성수 중 최솟값 구하기
        int minTemp = min(two, three);
        minTemp = min(minTemp, five);

        ugly[i] = minTemp;

        if (minTemp == two) {
            two=ugly[i2++]*2;
        }
        if (minTemp == three) {
            three = ugly[i3++] * 3;
        }
        if (minTemp == five) {
            five = ugly[i5++] * 5;
        }

    }
    cout << ugly[N-1];

    return 0;
}

풀이

시작점으로부터 BFS탐색하면서 이전 노드까지의 거리+1 양방향 주의해서 양쪽 방향 모두 벡터에 넣기

using namespace std;
#define MAXN 20001

vector<int> v[MAXN];
bool visited[MAXN]={false, };
int dist[MAXN]={0,};
int maxDist=0;

void BFS(int start){
    queue<int> q;
    q.push(start);
    visited[start]=true;
    int count=0;

    while(!q.empty()){
        int n=q.front();
        q.pop();

        for(int i=0;i < v[n].size(); i++){
            if(!visited[v[n][i]]){
                visited[v[n][i]]=true;
                q.push(v[n][i]);
                dist[v[n][i]]=dist[n]+1;
                maxDist=max(maxDist,dist[n]+1);
            }
            else{
                continue;
            }
        }
    }
    return;

}


int solution(int n, vector<vector<int>> edge) {
    int answer = 0;

    for(int i=0;i<edge.size();i++){
        v[edge[i][0]].push_back(edge[i][1]);
        v[edge[i][1]].push_back(edge[i][0]);

    }

    BFS(1);
    for(int i=1;i<=n;i++){
        cout<<dist[i]<<" ";
        if(dist[i]==maxDist){
            answer++;
        }
    }
    return answer;
}

문제

nxm 크기의 금광 채굴자는 첫 번째 열에서부터 금을 캐기 시작 m번에 걸쳐 매번 오른쪽 위, 오른쪽, 오른쪽 아래 방향으로 이동

입력

첫 번째 줄에 테스트 케이스 T (1<=T<=1000) n, m이 공백으로 구분되어 입력 (1<=n,m<=20) nxm개의 금의 개수가 공백으로 입력

출력

테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기

풀이

• 세로 방향으로 진행되는 경로의 최대 크기 문제(백준 1932번 정수 삼각형) 와 비슷하지만 이번에는 가로 방향으로 진행
• 맨 윗줄과 아랫줄의 진행방향은 두 방향만 가능하다는점 유의
• 각 경로에 있어서 최대값으로 갱신

using namespace std;

vector<int> arr;
int main(){
    int test, n,m;
    cin>>test;

    for(int t=0;t < test; t++){
        cin>>n>>m;
        int arr[401]={0, }; //1차원배열로 금의 수 입력됨
        for(int i=0;i < n*m; i++){
            cin>>arr[i];
        }

        int v[21][21];
        int index=0;

        for(int i=0;i<n;i++){ //2차원 배열로 재배열
            for(int j=0;j<m;j++){
                v[i][j]=arr[index++];
            }
        }
        for(int j=1;j<m;j++){
            for(int i=0;i<n;i++){
                if(i==0){ //맨 윗줄인 경우 -> 오른쪽, 오른쪽아래방향
                    v[i][j]+=max(v[i][j-1],v[i+1][j-1]);
                }
                else if(i==n-1){//맨 밑줄 경우 -> 오른쪽, 오른쪽윗방향
                    v[i][j]+=max(v[i][j-1],v[i-1][j-1]);
                }else{ //가운데 -> 3방향으로 갈 수 있는 경우
                    int temp=max(v[i][j-1],v[i+1][j-1]);
                    temp=max(temp,v[i-1][j-1]);
                    v[i][j]+=temp;
                }
            }
        }

        int maxResult=0;
        for(int i=0;i<n;i++){
            maxResult=max(maxResult, v[i][m-1]);
        }
        cout<<maxResult<<"\n";
    }
}

• 결과

전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치

입력

N (1 ≤ N ≤ 2,000) 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수

출력

남아있는 병사의 수가 최대가 되도록 하기 위해서 열외해야 하는 병사의 수를 출력

풀이

남아있는 병사의 수가 최대가 되기 위해서는 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)을 찾기 즉, 증가하는 부분이 가장 크도록 만드는 수를 찾아서 전체 병사의 수(N)-LIS의 값이 열외시켜야 하는 값

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

#define MAXN 2001
int N;

vector<int> arr;
int main(){
    cin>>N;
    int temp;
    for(int i=0;i<N;i++){
        cin>>temp;
        arr.push_back(temp);
    }

    reverse(arr.begin(),arr.end()); //뒤에서부터 증가하는 부분 찾기

    int dp[2000]; //LIS를 찾으면서 증가하는 부분의 수 저장 배열
    fill(dp,dp+2000,1); //배열 1로 초기화

    //LIS 찾기
    for(int i=1;i < N; i++){
        for(int j=0;j < i; j++){
            if(arr[i]>arr[j]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }

    int maxCnt=0;

    for(int i=0;i<N;i++){
        maxCnt=max(maxCnt,dp[i]); //LIS의 최대값 찾기
    }

    cout<<N-maxCnt<<"\n"; //열외시켜야하는 수



    return 0;
}

특정 위치의 집에 특별히 한 개의 안테나를 설치 -> 안테나로부터 모든 집까지의 거리의 총 합이 최소

입력

집의 수 N(1≤N≤200,000) N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수

출력

안테나를 설치할 위치의 값을 출력 (여러 개의 값이 도출될 경우 가장 작은 값을 출력)

풀이

1. 처음에는 이중반복문을 통해 한 집씩 모두 확인한 경우 시간초과 발생
2. 중간집을 선택할 경우가 가장 최소 위치 1) 집의 갯수가 짝수, 홀수인지 확인 2) 짝수인 경우는 house.size()/2-1, house.size()/2가 중간값 -> 비교해서 더 작은 값을 선택

using namespace std;

vector<int> house;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N,temp;
    cin >> N;

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

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

    if (house.size() % 2 == 0) { //집의 수가 짝수인경우
        int f = house[house.size() / 2 - 1];
        int s = house[house.size() / 2];

        int ft = 0, st = 0;

        for (int i = 0; i < N; i++) {
            ft += abs(house[i] - f);
            st += abs(house[i] - s);
        }

        if (ft <= st) {
            cout << f << "\n";
        }
        else {
            cout << s << "\n";
        }
    }
    else { //집의 수가 홀수인경우
        cout << house[house.size()/2] << "\n";
    }

    return 0;
}

N명의 이름과 국어, 영어, 수학 점수가 주어짐 [정렬조건]

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.)

입력

학생의 수 N (1 ≤ N ≤ 100,000) 이름, 국어, 영어, 수학 점수가 공백으로 구분 (점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수)

출력

정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력

풀이

우선 이름, 국어, 영어, 수학이라는 4가지 정보를 담기위해서 구조체 선언 sort 정렬 조건을 위해 따로 정렬 조건을 설정하는 함수(comp) 만들기

int N;

struct score {
    string name;
    int korean, english, math;
};

bool comp(score a, score b) {
    if (a.korean == b.korean && a.english == b.english && a.math == b.math)  //4번조건
        return a.name < b.name;
    if (a.korean == b.korean && a.english == b.english) //3번조건
        return a.math > b.math;
    if (a.korean == b.korean)  //2번조건
        return a.english < b.english;
    return a.korean > b.korean; //1번조건
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> N;
    vector<score> students(N);

    for (int i = 0; i < N; i++) {
        cin >> students[i].name >> students[i].korean >> students[i].english >> students[i].math;
    }
    sort(students.begin(), students.end(), comp);

    for (int i = 0; i < N; i++) {
        cout << students[i].name << "\n";
    }

    return 0;
}

N×N인 도시 도시의 치킨 거리는 모든 집의 치킨 거리의 합 치킨 거리 = (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2| 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하기

입력

N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13) 도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집

출력

도시의 치킨 거리의 최솟값을 출력

풀이

최대 M개의 치킨집을 조합하여 최소 도시의 치킨 거리를 구해야함 -> 치킨집을 M개씩 조합하기 -> M개의 치킨집과의 치킨 거리 구한 후 최소값 찾기

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

#define MAXN 51
int N, M, answer=1e9;
int graph[MAXN][MAXN];

vector<pair<int, int>> house;
vector<pair<int, int>> chicken;
vector<pair<int, int>> cal;

bool chickenCheck[14];
int distanceCalculate()
{
    int sum = 0;
    for (int i = 0; i < house.size(); i++)
    {
        int x = house[i].first;
        int y = house[i].second;
        int d = 1e9;

        for (int j = 0; j < cal.size(); j++)
        {
            int xx = cal[j].first;
            int yy = cal[j].second;
            int Dist = abs(xx - x) + abs(yy - y);

            d = min(d, Dist);
        }
        sum += d;
    }
    return sum;
}


void joinChicken(int index,int cnt) {

    if (cnt == M) { //치킨이 M개가 된 경우 치킨거리 합 구하기
        answer = min(answer, distanceCalculate()); 
        return;
    }

    for (int i = index; i < chicken.size(); i++) { //조합 -> 시작점=index
        if (chickenCheck[i] == true) continue;

        chickenCheck[i] = true;
        cal.push_back(chicken[i]);
        joinChicken(i, cnt +1);
        chickenCheck[i] = false;
        cal.pop_back();
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    int input;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> input;
            graph[i][j] = input;

            if (input == 1) {
                house.push_back({ i,j });
            }
            else if (input == 2) {
                chicken.push_back({ i,j });
            }

        }
    }

    joinChicken(0, 0);
    cout << answer;

    return 0;
}

N종류의 화폐를 이용하여 합이 M이 되도록하는 화폐의 최소 개수 구하기

입력

N, M (1<=N<=100, 1<=M<=10,000) N개의 줄에 화폐의 가치가 주어짐

출력

경우의 수 X 출력, 불가능한 경우 -1 출력

풀이

그리디 알고리즘의 거스름돈 문제와 비슷해보이지만, 매번 가장 큰 화폐부터 처리하는 방법으로 해결할 수 없기 때문에 다이나믹 프로그래밍을 사용해야함.

적은금액부터 순서대로 확인하면서 이전 금액을 만들 수 있는 경우+1과 현재값의 경우의 수를 비교하여 최솟값을 구하기

점화식 예) a2=min(a2, a1+1) 두번째 값의 경우의 수는 바로 이전의 값의 경우의 수 +1과 비교하여 최솟값

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

#define MAXN 101
#define MAXM 10001

using namespace std;

int money[MAXM]; //만들수있는 최소 화폐개수
int bill[MAXN]; //화폐 종류


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

    fill(money, money + MAXN, MAXM); //최대값으로 초기화

    int N, M;
    cin >> N >> M;


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

    money[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = bill[i]; j <= M; j++) {
            money[j] = min(money[j], money[j - bill[i]] + 1);
        }
    }

    if (money[M] == MAXM) {
        cout << -1;
    }
    else {
        cout << money[M];
    }



    return 0;
}

정수 X가 주어졌을 때 사용할 수 있는 연산 4가지

• 5로 나누어떨어지면 5로 나눈다
• 3으로 나누어떨어지면 3으로 나눈다
• 2로 나누어떨어지면 2로 나누다
• 1을 뺀다

연산 4개를 사용하여 1을 만들기 위한 최소 연산 횟수

입력

정수 X (1<=X<=30,000)

출력

연산을 위한 최소 횟수

풀이

2부터 X까지 증가하면서 각각의 연산을 했을때의 회수의 최솟값을 배열에 저장 X-1의 최소 횟수보다 1만큼 크다는 전제하에 비교하기

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

#define MAXN 30001

using namespace std;

int cnt[MAXN] = { 0, };


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

    int N;
    cin >> N;

    for (int i = 2; i <= N; i++) {
        cnt[i] = cnt[i - 1] + 1;

        if (i % 2 == 0) {
            cnt[i] = min(cnt[i], cnt[i / 2] + 1);
        }
        if (i % 3 == 0) {
            cnt[i] = min(cnt[i], cnt[i / 3] + 1);
        }
        if (i % 5 == 0) {
            cnt[i] = min(cnt[i], cnt[i / 5] + 1);
        }
    }

    cout << cnt[N];



    return 0;
}

문제

• 집 N개가 수직선 위(x1, ..., xN)
• 공유기 C개를 설치
• 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치

입력

집의 개수 N (2 ≤ N ≤ 200,000), C (2 ≤ C ≤ N) N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력

풀이

알고리즘참고링크

공유기를 설치할 수 있는 거리 최소 거리 low= 1 최대 거리 high= 마지막 집 - 첫번째 집

이분탐색을 하면서 mid=(low+high)/2의 값을 조정하면서 C개 이상의 공유기를 설치할 수 있는 거리 중 가장 최대값을 구하기

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

using namespace std;

int N, C;
vector<int> house;

//mid값으로 공유기를 C개 이상 설치할 수 있는지 확인
bool chk(int mid) {
    int cnt = 1;
    int prev = house[0];

    for (int i = 0; i < N; i++) {
        if (house[i] - prev >= mid) {
            cnt++;
            prev = house[i];
        }
    }
    if (cnt >= C) {
        return true;
    }
    return false;
}

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

    cin >> N >> C;
    int temp;
    for (int i = 0; i < N; i++) {
        cin >> temp;
        house.push_back(temp);
    }

    sort(house.begin(), house.end()); //집 번호순서대로 오름차순 정렬

    int low = 1, high = house[N - 1] - house[0];
    int maxdistance = 0;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (chk(mid)) {
            maxdistance = max(maxdistance, mid);
            low = mid + 1;

        }
        else {
            high = mid - 1;
        }
    }
    cout << maxdistance << "\n";
    return 0;
}

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|) 터널을 총 N-1개 건설해서 모든 행성이 서로 연결하기 위해 필요한 최소비용

입력

행성의 개수 N(1 ≤ N ≤ 100,000) 각 행성의 x, y, z좌표(-10^9보다 크거나 같고, 10^9보다 작거나 같은 정수)

출력

모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력

풀이

N개의 행성을 N-1개의 터널로 연결하기 위한 최소 비용 구하는 문제이기 때문에 최소 신장 트리(MST) 문제로 풀 수 있다.

FindParent 함수는 각 행성의 부모 노드를 찾는 함수이고, Union 함수는 두 개의 행성의 부모노드가 다른 경우 MST에 추가(합치는)하는 함수

1) 메모리 초과

3차원 좌표로 주어지기 때문에 처음에는 우선 3개의 정보를 담을 수 있도록 구조체로 구현해보았다. 하지만 계속해서 메모리 초과가 되었고, 3개의 정보를 담는 tuple을 이용한 벡터도 사용했지만 마찬가지였다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include <stdlib.h>
#include<tuple>
#define MAXN 100001

using namespace std;

int N;

struct planet {
    int x;
    int y;
    int z;
};

vector<tuple<int, int, int> > cost;


planet planets[MAXN];

int parents[MAXN];


int FindParent(int x) {
    if (parents[x] == x) {
        return x;
    }
    return parents[x] = FindParent(parents[x]);
}

void Union(int x, int y) {
    x = FindParent(x);
    y = FindParent(y);

    parents[x] = y;

    FindParent(x);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> N;

    for (int i = 0; i < N; i++) {
        parents[i] = i;
    }

    int a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        planets[i].x = a;
        planets[i].y = b;
        planets[i].z = c;
        if (i > 0) {
            for (int j = i - 1; j >= 0; j--) {
                int d = min({abs(a - planets[j].x), abs(b - planets[j].y), abs(c - planets[j].z) });
                cost.push_back(make_tuple(d,j,i));
            }
        }
    }

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

    long long result = 0;

    for (int i = 0; i < cost.size(); i++) {
        if (FindParent(get<1>(cost[i])) != FindParent(get<2>(cost[i]))) {
            result += get<0>(cost[i]);
            Union(get<1>(cost[i]), get<2>(cost[i]));
        }
        else {
            continue;
        }
    }

    cout << result << "\n";
    return 0;
}

2) 성공

알고리즘참고링크 다른 풀이들을 참고해보니 한 번에 3개를 저장하여 정렬하는 것이 아닌, X,Y,Z 각각을 따로 저장하여 정렬한 후 앞에서부터 조건을 해당하는 N-1만큼의 터널을 선택하는 것으로 푸니 해결되었다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<tuple>
#include<cmath>

#define MAXN 100001

using namespace std;

int N;

vector<tuple<int, int, int> > cost;

vector<pair<int, int>> X, Y, Z;

int parents[MAXN];


int FindParent(int x) {
    if (parents[x] == x) {
        return x;
    }
    return parents[x] = FindParent(parents[x]);
}

void Union(int x, int y) {
    x = FindParent(x);
    y = FindParent(y);

    parents[x] = y;

    FindParent(x);

    return;
}

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        parents[i] = i; //부모배열 자기자신으로 초기화
    }

    int a, b, c;
    for (int i = 0; i < N; i++) {
        cin >> a >> b >> c;
        X.push_back({ a,i });
        Y.push_back({ b,i });
        Z.push_back({ c,i });
    }

    //X,Y,Z값 각각 오름차순 정렬
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    sort(Z.begin(), Z.end());

    for (int i = 0; i < N - 1; i++) {
        cost.push_back({ X[i + 1].first - X[i].first,X[i].second, X[i + 1].second });
        cost.push_back({ Y[i + 1].first - Y[i].first,Y[i].second,Y[i + 1].second });
        cost.push_back({ Z[i + 1].first - Z[i].first,Z[i].second, Z[i + 1].second });
    }
    sort(cost.begin(), cost.end()); //거리에 따라 오름차순 정렬

    long long result = 0;
    int count = 0; //N-1도로만큼 추가
    for (int i = 0; i < cost.size(); i++) {
        if (FindParent(get<1>(cost[i])) != FindParent(get<2>(cost[i]))) {
            result += get<0>(cost[i]);
            count++;
            Union(get<1>(cost[i]), get<2>(cost[i]));
        }

        if (count == N-1) {
            break;
        }
    }

    cout << result << "\n";
    return 0;
}

문제

• NxN 크기의 복도
• 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행
• 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다
• 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정
• 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력

입력

자연수 N(3 ≤ N ≤ 6) 학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X

출력

첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력

풀이

처음에는 어떻게 접근해야할지 막막했다. 선생님들의 위치에서 학생들의 위치를 빼서 다 찾아봐야했나 싶었는데, 위의 링크를 통해서 N이 X로 되어있는 빈칸에 장애물을 하나씩 두면서 3개가 되었을 때 모든 학생들이 다 가려지는지 확인하는 DFS방법으로 진행

1. 선생님과 빈칸 각각을 T(teacher), B(blank)배열에 저장
2. 빈칸을 dfs 탐색하면서 탐색한 곳에 장애물 표시
3. 장애물 개수가 3개가 되었을 때 선생님들한테 가려지는지 확인하는 함수(checkStudent)로 확인 -> 각 선생님들의 상하좌우로 복도 크기 내에서 장애물 사이에 학생이 있는 경우 false 리턴, 모두 조건을 만족하는 경우 true 리턴

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

#define MAXN 6

using namespace std;

char g[MAXN][MAXN];
vector<pair<int, int>> t,b; //teacher,blank

int N;

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };

bool checkStudent(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x;
        int ny = y;

        while (nx >= 0 && ny >= 0 && nx < N && ny < N) { //한방향으로 계속 이동하면서 체크하기
            if (g[nx][ny] == 'O') break;
            if (g[nx][ny] == 'S') return false;
            nx += dx[i];
            ny += dy[i];
        }
    }

    return true;
}

void DFS(int count, int idx) {

    if (count == 3) {
        for (int i = 0; i < t.size(); i++) {
            if (!checkStudent(t[i].first, t[i].second)) {
                return;
            }
        }
        cout << "YES";
        exit(0);
    }

    for (int i = idx; i < b.size(); i++) {
        g[b[i].first][b[i].second] = 'O';
        DFS(count + 1, i + 1);
        g[b[i].first][b[i].second] = 'X';
    }
    return;
}

int main() {
    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >>g[i][j];
            if (g[i][j] == 'T') {
                t.push_back(make_pair(i, j));
            }
            else if (g[i][j] == 'X') {
                b.push_back(make_pair(i, j));
            }
        }
    }

    DFS(0, 0);

    cout << "NO";

    return 0;
}

문제

• N개의 수로 이루어진 수열 A1, A2, ..., AN과 N-1개의 연산자(덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷))
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행
• 만들 수 있는 식의 결과가 최대인 것과 최소

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어짐 둘째 줄에는 A1, A2, ..., AN 셋째 줄에는 합이 N-1인 4개의 정수 (차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷))

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력 식의 결과는 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

풀이

수열을 앞에서부터 순서대로 진행하면서 넣을 수 있는 연산자의 모든 조합을 알아봐야함. -> DFS로 풀이

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

using namespace std;

int N;
int oper[4] = { 0, }; //연산자 개수 저장
vector<int> nums; //수열 저장

int rmin = 1000000001; //최소값
int rmax = -1000000001; //최대값

void cal(int index, int result) {
    if (index >= N) {
        if (rmin > result) {
            rmin = result; //최소값 갱신
        }
        if (rmax < result) {
            rmax = result; //최대값 갱신
        }
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (oper[i] > 0) {
            oper[i]--; //연산자가 존재하는 경우 -1
            if (i == 0) { //더하기인 경우
                cal(index+1, result+nums[index]);
            }
            else if (i == 1) { //빼기인 경우
                cal(index + 1, result-nums[index]);
            }
            else if (i == 2) { //곱하기인 경우
                cal(index + 1, result * nums[index]);
            }
            else { //나누기인 경우
                cal(index + 1, result / nums[index]);
            }
            oper[i]++; //탐색 종료 후 +1 (원상복귀)
        }
    }
    return;

}

int main() {

    cin >> N;

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

    for (int i = 0; i < 4; i++) {
        cin >> temp;
        oper[i] = temp;
    }

    cal(1, nums[0]); //첫번째값 넣은 후 탐색 시작

    cout << rmax << "\n";
    cout << rmin << "\n";
    return 0;
}

문제

• NxN 크기의 시험관
• 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나
• 1초마다 상, 하, 좌, 우의 방향으로 증식
• 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다
• S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류

입력

1. N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000)
2. N개의 줄에 걸쳐서 시험관의 정보 (해당 위치에 바이러스가 존재하지 않는 경우 0)
3. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)

출력

S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력(만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력)

풀이

우선 각 초마다 바이러스가 있는 위치에서의 BFS 구현 한 번의 BFS는 구현할 수 있지만 각 초마다의 BFS 구현의 반복을 어떻게 구현할지 어려웠다. -> 각 초마다 반복하며 그 순간의 큐의 크기만큼 BFS 실행하여 구현

(몇 번의 런타임에러가 있었는데 그래프 크기를 NxM으로 착각하여 크기를 잘못 설정했음 틀린 경우는 바이러스가 1~K까지 각각 하나인 줄 알고 풀었는데, 같은 번호의 바이러스가 여러개인 경우도 존재 가능)

더 좋은 방법이 있을 것 같지만 이런 유형의 BFS 문제가 처음이었기 때문에 깔끔하지 못한 느낌이다.

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

int N, M, X, Y, S;

#define MAXN 201
#define MAXM 1001

using namespace std;

int g[MAXN][MAXM];
vector<pair<int, int>> virus[MAXM];

int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };


void BFS() {

    queue<pair<int, int>> q; //바이러스 위치 저장 큐
    queue<int> indexq; // 각 바이러스의 번호 저장 큐

    //바이러스의 위치를 큐에 저장
    for (int i = 1; i <= M; i++) {
        for (int j = 0; j < virus[i].size(); j++) {
            q.push(make_pair(virus[i][j].first, virus[i][j].second));
            indexq.push(i);
        }
    }

    for (int i = 0; i < S; i++) { //시간이 S초만큼 반복
        int qsize = q.size(); //각 초에서의 큐의 크기

        while (qsize) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            int index = indexq.front();
            indexq.pop();

            //BFS 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    continue;
                }
                if (g[nx][ny] == 0) {
                    g[nx][ny] = index;
                    q.push(make_pair(nx, ny));
                    indexq.push(index);
                }
            }
            qsize--;
        }
    }

    return;

}

int main() {
    cin >> N >> M;

    int temp;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> temp;
            g[i][j] = temp;
            if (temp > 0) {
                virus[temp].push_back(make_pair(i,j)); //1~K까지의 바이러스 위치 저장
            }
        }
    }

    cin >> S >> X >> Y;

    if (S == 0) { //초가 0인경우는 BFS 실행 X
        cout << g[X - 1][Y - 1];
    }
    else {
        BFS();
        cout << g[X - 1][Y - 1];
    }


    return 0;
}

1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1

입력

도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) M개의 줄에 걸쳐서 두 개의 자연수 A, B - A에서 B로 이동하는 단방향 도로

출력

최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력

풀이

특정 출발점에서부터 다른 도시까지의 최단거리를 찾는 문제이기때문에 다익스트라로 풀이 가능 큐를 이용한 BFS로 풀이 -> 각 도시의 거리는 이전 도시까지의 거리 + 1

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

#define MAXN 300001
using namespace std;

int N, M, K, X; //도시의 수, 도로의 수, 목표거리, 출발도시 
vector<int> v[MAXN]; //그래프 저장
long dist[MAXN]; //거리 저장 
bool visited[MAXN]; //방문 저장
vector<int> result; //거리가 K인 도시 정보

void BFS(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;

    while (!q.empty()) {
        int s = q.front();
        q.pop();

        for (int i = 0; i < v[s].size(); i++) {
            int next = v[s][i];

            if (!visited[next]) { //방문하지 않은 경우
                q.push(next);
                visited[next] = true;
                dist[next] = dist[s] + 1; //이전 도시까지의 거리 + 1

                if (dist[next] == K) { //거리가 K인 경우 result에 저장
                    result.push_back(next);
                }
            }
        }

    }
    return;
}
int main() {
    cin >> N >> M >> K >> X;

    int a,b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        v[a].push_back(b);
    }

    BFS(X);

    if (result.size() > 0) {
        sort(result.begin(), result.end()); //오름차순 정렬

        for (int i = 0; i < result.size(); i++) {
            cout << result[i] << "\n";
        }
    }
    else {
        cout << -1;
    }
    return 0;
}

NxM크기의 미로 (1,1)에서부터 (N,M)까지의 거리

입력

N, M(2 ≤ N, M ≤ 100) N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력

출력

첫째 줄에 지나야 하는 최소의 칸 수 (항상 도착위치로 이동할 수 있는 경우만 입력으로 주어짐)

풀이

목적지까지의 최소 거리를 구하는 문제이기때문에 BFS로 접근 큐를 이용한 BFS코드를 사용하여 풀이하였는데, 거리를 계산하는 과정에서 조금 더 신경써야함

route라는 이차원 배열을 사용하여 첫 시작점은 거리가 1, 그 다음은 이전 값의+1씩 저장되도록 설정 visited 이차원 배열은 각 위치를 방문했는지를 확인

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

#define MAXN 101

using namespace std;

int N, M;
int miro[MAXN][MAXN] = { 0, };

//방향 배열
int dx[4] = { 0,0, - 1,1 };
int dy[4] = { -1,1,0,0 };

int visited[MAXN][MAXN] = { 0, }; //방문 확인
int route[MAXN][MAXN] = { 0, }; //시작점부터의 거리 저장

void BFS(int x, int y) {

    queue<pair<int, int>> q;
    q.push(make_pair(x, y));

    visited[x][y] = 1;
    route[x][y] = 1;     //처음 위치의 경우 거리 1로 설정

    while (!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;

        q.pop();

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                    int ny = cy + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) { //미로 벗어나는 경우
                    continue;
                }
                else {
                    if (miro[nx][ny] == 1 && visited[nx][ny]==0) {
                        q.push(make_pair(nx, ny));
                        visited[nx][ny] = 1; //방문한 경우
                        route[nx][ny] = route[cx][cy] + 1; //이전 위치(큐에서 꺼낸 cx,cy)부터 한 칸 더 온 경우이기 때문에

                    }
                    else {
                        continue;
                    }
                }
            }


    }
    return;

}


int main() {

    cin >> N >> M;

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

        for (int j = 0; j < M; j++) {
            miro[i][j] = (s[j]-'0');//문자열 숫자로 변환
        }
    }

    BFS(0, 0);

    cout << route[N - 1][M - 1];

    return 0;
}

각 자리가 숫자(0~9)로 이루어진 문자열 S 왼쪽부터 순서대로 +,* 연산 이루어짐 만들 수 있는 가장 큰수

예) S = 02984 만들 수 있는 가장 큰 수 = ((((0 + 2) x 9) x 8) x 4) = 576

입력

문자열 S(1<=S<=20)

출력

만들 수 있는 가장 큰 수

풀이

0이나 1은 곱했을 때보다 더했을 때 큰 수를 만들 수 있음 -> 0과 1은 더하고 이외의 수는 곱하기

#include<iostream>
#include<string>

using namespace std;

int main() {
    string s;
    cin >> s;

    int total = 0;
    int first = s[0] - '0';


    if (s.size() >= 2) {
        int second = s[1] - '0';

        //맨 앞 두 숫자 비교해서 더하거나 곱하기
        if (first == 0 || first == 1 || second == 0 || second == 1) {
            total += (first + second);
        }
        else {
            total += (first * second);
        }
        //3번째 숫자부터는 0이나 1인 경우 더하기, 아닌 경우 곱하기
        for (int i = 2; i < s.size(); i ++) {
            int next = (s[i] - '0');
            if (next == 1 || next == 0) {
                total += next;
            }
            else {
                total *= next;
            }
        }
    }
    else {//숫자가 1개만 있는 경우
        total += first;
    }

    cout << total<<"\n";
    return 0;
}

공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야함 몇 명의 모험가는 마을에 그대로 남아 있어도 가능

예) N = 5 2 3 1 2 2

그룹 1 - 1, 2, 3 그룹 2 - 2, 2 ** 결과 - 2**

입력

모험가의 수 N (1<=N<=100,000)

출력

여행을 떠날 수 있는 그룹 수의 최댓값

풀이

오름차순으로 정렬하여 그룹 내에 포함된 인원이 공포심과 같아지는 경우 그룹 수 증가

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

using namespace std;

int main() {
    int N, scare;
    cin >> N;

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

    sort(v.begin(), v.end()); //오름차순 정렬

    int group = 0;
    int count = 0;
    for (int i = 0; i < v.size(); i++) {
        count++;
        if (count == v[i]) { //공포심x와 그룹인원이 같은 경우
            group++;
            count = 0;
        }
    }

    cout << group << "\n";

    return 0;
}