2024 - 11- 01 C++ 코딩테스트 10주완성 D+56

복습

 

복습한 내용은 이러하다!

 

- 백준 11723 집합 문제
- 백준 14391 종이조각 문제

 

복습이라해도 쉽지않았다..!! 도중에 깨달은 것도 주석처리 해놓았다.

 

#include <bits/stdc++.h>

using namespace std;


//#1
int cnt;
int s,x;
char str[11];

int main()
{
    scanf("%d", &cnt);

    for(int i =0; i < cnt; i++)
    {       
        scanf("%s %d", &str, &x);        
        
        if(str[0] == 'a' && str[1] == 'd') s |= (1 << x);

        else if(str[0] == 'r') s &= ~(1 << x);

        else if(str[0] == 'c') printf("%d\n",(s & (1 << x) ? 1 : 0 ));

        else if(str[0] == 't') s ^= (1 << x);

        else if(str[0] == 'a' && str[1] == 'l') s = (1 << 21) - 1;

        else s = 0;           
    }

    return 0;
}
//#1
//코드를 수정하기전에는 cin 과 cout 를 사용하였는데,
//시간초과가 나서 printf 와 scanf 로 바꾸었더니 제대로 동작하였다..! 

//#2
int n,m,ret = -987654321;
int a[8][8];


int main()
{
    scanf("%d %d",&n, &m);

    for(int i =0; i < n; i++)
    {       
        for(int j =0; j < m; j++) scanf("%1d",&a[i][j]);        
    }

    //각 a행렬의 모든 경우의 수
    for(int s =0; s < (1 << (n *m)); s++)
    {
        int sum = 0;
        //가로일때 합계
        for(int i =0; i < n; i++)
        {
            int row = 0;
            for(int j =0; j < m; j++)
            {
                //k의 값은 비트의 순서를 나타냄
                int k = i * m + j;
                if((s & (1 <<k))== 0)  
                {
                  row = row * 10 + a[i][j];
                }
                else
                {
                    sum += row;
                    row = 0;
                }
            }
            sum += row; 
        }            
        for(int j =0; j <m; j++)
        {
           int cur =0;
            for(int i =0; i < n; i++)
            {
                int k = i * m + j;
                if((s & (1<<k)) != 0)
                {
                    cur = cur * 10 + a[i][j];
                }
                else
                {
                    sum += cur;
                    cur = 0;
                }
            }
            sum += cur;
        }
        
        ret = max(ret,sum);
    }
    cout << ret;
    return 0;
}
//#2

 

복습끝 !!!

---

백준 13244 문제 - Tree

 

난이도

 

One of the most important data structures in computer science is the tree. You already dealt with binary trees in the qualification round. This problem is about general trees.

Trees are the subset of graphs that have the following 3 properties:

1. It is connected: for every node you can reach every other node following edges.
2. If an edge is removed, the graph is no longer connected. That is, some nodes cannot be reached anymore.
3. When an edge is added between two existing nodes A and B, a cycle is created. There is a cycle if there is more than one way to go from A to B.

Your task is to decide if a given graph is a tree or not.

 

보아라 눈앞이 까마득해진다.. 무려 영어지문으로 된 문제이다

 

하지만 걱정마라! 우리에겐 무적의 파파고와 구글 번역기가 있으니까!!

 

컴퓨터 과학에서 가장 중요한 데이터 구조 중 하나는 트리(Tree)입니다. 

당신은 이미 예선 라운드에서 이진 트리를 다루었습니다. 이번 문제는 일반 트리에 관한 문제입니다.

트리는 다음 3가지 속성을 가진 그래프의 하위 집합입니다.연결되어 있습니다. 

모든 노드에 대해 가장자리를 따라 다른 모든 노드에 도달할 수 있습니다.

간선이 제거되면 그래프는 더 이상 연결되지 않습니다. 

즉, 일부 노드에 더 이상 접근할 수 없습니다.기존 두 노드 A와 B 사이에 간선이 추가되면 순환이 생성됩니다. 

A에서 B로 가는 길이 여러 개 있으면 순환이 있습니다.

당신의 임무는 주어진 그래프가 트리인지 아닌지를 결정하는 것입니다.

 

 

자 이제 입력과 출력또한 무적의 힘을 빌려보자!

 

입력

 

첫 번째 줄에는 확인할 그래프 수를 나타내는 정수 T가 포함됩니다.

각 테스트 사례에는 최대 10개의 그래프가 있습니다.

각 그래프는 다음과 같이 표현됩니다.

첫 번째 줄에는 그래프의 노드 수와 함께 정수 N이 포함됩니다. (노드 수는 1~1,000개입니다.)

각 노드의 식별자는 1부터 N까지의 정수입니다.

다음 줄에는 그래프의 간선 수와 함께 정수 M이 포함됩니다. (최대 10^6개의 모서리가 있습니다.)

다음 M 줄에는 각각 2개의 정수 A와 B가 포함됩니다.
(이는 가장자리로 연결된 두 개의 노드입니다. 모든 테스트 케이스에서 M의 총합은 최대 10^6입니다.)

 

출력

 

각 그래프에 대해 그래프가 나무를 나타내는 경우 "tree"가 그렇지 않은 경우 "graph"로 출력

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

//변수목록
//테스트 사례의 개수를 입력받을 T
//테스트 케이스마다 그래프의 노드의 개수를 입력받을 정수형 변수 N
//테스트 케이스마다 그래프의 간선 수를 입력받을 정수형 변수 M
int T,N,M,cnt;
vector<int> v[1004];
int visited[1004];

void dfs(int a)
{
    visited[a] = 1;
    
    for(int here : v[a])
    {
        if(!visited[here]) dfs(here);
    }
    return;    
}

int main()
{
    cin >> T;
    
    for(int i=0; i < T; i++)
    {
        for(int i =0; i < 1004; i++) v[i].clear();
        fill(visited,visited + 1004,0);
        cnt = 0;
        cin >> N >> M;
        for(int j=0; j < M; j++)
        {
            int a,b= 0;
            cin >> a >> b;
            v[a].push_back(b);
            v[b].push_back(a);
        }
        for(int i = 1; i <=N; i++)
        {
            if(!visited[i]) 
            {
                dfs(i);
                cnt++;
            }
        }

        if(M == N -1 && cnt == 1) cout << "tree" << endl;

        else cout << "graph" << endl;
    }    
}

 

이 문제의 핵심로직은 트리가 되는 조건이면

 

"모든 노드가 연결되어 있고, 간선의 수 =  (노드의 개수 -1) " 이라는 조건이 성립하여야 트리가 되는 것이다!

 

이 코드의 실행순서를 살펴보자!

 

1. 테스트케이스의 개수 T를 입력받는다.

2. T만큼 반복문을 돌린다.
 ㄴ 2-1. 간선을 담을때 쓰이는 v 와 dfs탐색때 방문한 곳을 체크할 visited 행렬과 전역변수 cnt 를 
             0으로 초기화시켜준다.
 ㄴ 2-2. 간선의 개수 M만큼 반복문을 돌린다.
    ㄴ2-2-1. 내부 정수형 변수 A,B를 입력받고 간선인 경우 둘다 연결되어 있는 것이므로 
                   v[A].push_back(B) 와 v[B].push_back(A) 를 하여준다.
 ㄴ 2-3. 노드의 개수 N만큼 반복문을 돌린다.
     ㄴ2-3-1. 만약 visited[i] 가 아닐 시 dfs(i) 호출
        ㄴ 2-3-1-1. void dfs(int a)
        ㄴ 2-3-1-1. 방문한 곳을 표기해야하므로 visited[a] = 1 을 해준다.
        ㄴ 2-3-1-2. v[a] 안에 저장된 만큼 반복문( int here : v[a] )을 돌린다.
            ㄴ 2-3-1-2-1. 만약 visited[here] = 0이 아닐시 dfs(here) 을 호출한다.
     ㄴ2-3-2. dfs 탐색이 끝난뒤 cnt++ 를 해준다.

ㄴ 2-4. N = M -1 일 경우 트리의 조건을 만족하고, cnt가 1일경우 dfs 탐색을 한번만 돌았다는 것이므로
            모든 노드가 연결되어 있다는 것이므로 tree를 출력시켜준다.
ㄴ 2-5. 아닐경우 트리가 아니므로 graph를 출력시켜준다.

 

솔직히.. 강의실습코드를 봤다. 트리의 조건을 생각지도 못하였다다다..

 

가장 간단한 문제인거 같은데 이걸 놓치다니.. 기본기가 역시 중요하다는걸 세삼 깨닫고 간다!

---

 

백준 5430 문제 - AC

 

난이도

 

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다.

 

AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

 

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다.

 

배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

 

함수는 조합해서 한 번에 사용할 수 있다.

예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.
예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

 

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다.
(p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.)

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

 

출력

 

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다.
(만약, 에러가 발생한 경우에는 error를 출력한다.)

 

실습코드

 

#include <bits/stdc++.h>
using namespace std;

int n, t;

string p,ary;

int main() {

    //1. 테스트 케이스 개수 입력
    cin >> t;

    
    for (int i = 0; i < t; i++)
    {
        deque<int> v;
        //함수, 개수, 배열입력
        cin >> p;
        cin >> n;
        cin >> ary;
        int num = 0;
        bool isreverse = false;
        bool iserror = false;
        bool isnum = false;
        for (int j = 0; j < ary.size(); j++)
        {
            if (ary[j] >= '0' && ary[j] <= '9')
            {
                isnum = true;
                num = num * 10 + (ary[j] - 48);                
            }
            else if(isnum == true)
            { 
                if (num > 0)
                {
                    v.push_back(num);
                    num = 0;
                    isnum = false;
                }
            }           
        }

        for (int d = 0; d < p.size(); d++)
        {
            if (v.size() == 0 && p[d] == 'D')
            {
                iserror = true;
                break;
            }

            //Delete를 입력받았을 때
            //원래 상태일때면 뒤집지않고 맨뒤의 원소를 삭제함
             if (p[d] == 'D' && !isreverse) v.pop_front();

            //뒤집은 상태면 맨뒤의 원소
            else if (p[d] == 'D' && isreverse) v.pop_back();

            //Reverse를 입력받았을 때
            //D연산을 다 한후에 isreverse 가 true면 뒤집어주고 false면 그대로 냅두면 된다.
            else if (p[d] == 'R') isreverse = !isreverse;
        }

        if (isreverse) reverse(v.begin(), v.end());               
        
        //v.size가 0일시..
        if (iserror) cout << "error" << endl;

        else
        {
            cout << "[";
            for (int a = 0; a < v.size(); a++)
            {
                cout << v[a];

                if (a < v.size() - 1) cout << ",";
            }
            cout << "]\n";
        }
    }
    return 0;
}

 

 

이 문제의 핵심로직은

 

1.입력받은 문자열을 숫자만 빼와서 배열안에 집어넣는 것

 

2. 입력받은 수행할 함수 AC중 ' R ' 인 경우일때마다 뒤집으면 시간복잡도가 너무 커지기때문에 bool형 변수를 이용하여

값만 바꿔주다가 마지막에 bool형 변수의 값을 보고 반전여부를 실행하는 것

 

이 두개이다! 

 

첫번째는 나도 생각한 로직인데 두번째는 생각지도 못하였다..!! 이것을 안하면 시간초과가 뜬다고 한다

 

실행순서를 보자!

 

1. 테스트 케이스의 개수 T를 입력받는다.

2. T만큼 반복문을 돌린다.
ㄴ2-1. 수행할 함수를 받을 문자열 p와 배열의 개수 n, 그리고 배열을 문자열인 ary를 입력받는다.
ㄴ2-2. 반전유무를 확인할 bool형 변수 isreverse, 에러를 출력할 유무를 확인할 bool형 변수 iserror,
           숫자유무를 판단할 bool형 변수 isnum, 문자열에서 각 배열의 숫자를 저장할 int형 변수 num을 선언한다.
ㄴ2-3. ary의 사이즈만큼 반복문을 돌린다.
   ㄴ2-3-1. 만약 ary[j] 가 숫자면 num = num * 10 과 ary[j] 를 더해준다.
                 이때 ary[j] 의값은 ASCII코드로 표현되기때문에 '0' 의 값인 48을 빼주어야 해당 숫자가 나온다.
   ㄴ2-3-2. 아닐경우 문자열이 나온것이므로 숫자가 끝난것이기 때문에 v안에 num을 저장시켜주고 num 값을 0으                   로 초기화시켜주고 isnum 을 다시 false로 바꿔준다.
ㄴ2-4. p 사이즈만큼 반복문을 돌린다.
   ㄴ2-4-1. 만약 v.size 가 0 이고 p[d] 가 'D' 일시에는 뺄 배열이 없으므로 iserror 의 값을 true로 해준다.
   ㄴ2-4-2. p[d] 가 'D'이면 isreverse의 값에 따라 dequeue인 v를 false면 앞에서 pop true면 뒤에서 pop 해준다.
ㄴ2-5. 반복문이 끝난뒤 isreverse 가 true이면 v를 뒤집어준다.
ㄴ2-6. iserror가 true면 error 를 출력하고, 아닐 경우 v의 원소를 차례대로 출력하여준다.

 

코드로 따지면 간단한 문제지만, 이 간단한 로직이 생각나야 시간초과가 나지않고, 통과할 수 있다!