글 읽기 - 문제는 맞았지만 궁금한 점이 있습니다

dreamian 6년 전 0

문제는 다음과 같이 접근하였습니다.

1) connected의 bool 타입 배열을 선언하여 노드 '1'과 연결 상태인지 확인하도록 하였습니다.

2) 일단 표준 입력에서 두 노드를 입력받아 둘 중 하나가 이미 연결되어 있는 경우, 해당 노드의 connected 값을 true로 바꾸는 방식으로 접근했습니다.

3) 만약, 두 노드 모두 연결되어 있지 않다면 spare의 pair형 벡터에 담아두었습니다.

4) 모든 입력값을 처리한 후에 spare 벡터를 순차적으로 탐색합니다.

5) spare 벡터 내에서 해당 원소값 중 하나가 연결된 상태라면 나머지 한 짝도 connected 시키는 방식으로 구현했습니다. 이때 해당 원소는 벡터에서 삭제 처리합니다.

6) 5)의 과정을 spare 벡터의 size값의 변함이 없을 때까지 반복합니다.

많은 분들의 코드를 보면 vector의 erase 연산을 사용하는 경우가 거의 없어 제가 접근하는 방식이 효율적인 방식인지 궁금합니다.

해당 vector의 size를 0으로 시작해서 size값을 계속 높여나가는 방식이 좋은 것일까요?

원소의 삽입 삭제가 빈번히 일어나는데 이러한 방식이 과연 효율적일지 갈피를 못 잡겠어서 고수님들의 의견을 듣고싶습니다.

다행히 해당 문제는 n값이 100이하로 제한이 되어 0ms로 AC받긴 했지만, n값이 커지는 경우에는 과연 효율적인 것일지 궁금합니다.

#include <bits/stdc++.h>
using namespace std;
bool connected[101];

int main(){
    int n;
    int conn;
    scanf("%d",&n);
    scanf("%d",&conn);
    vector< pair<int,int> > spare(0);
    int sz=0;
    int cnt=0;
    connected[1]=true;
    for(int i=0;i<conn;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        if(connected[a] && connected[b]) continue;
        else if(connected[a]){
            connected[b]=true; cnt++;
        }
        else if(connected[b]){
            connected[a]=true; cnt++;
        }
        else{
            sz++;
            spare.resize(sz);
            spare[sz-1].first=a;
            spare[sz-1].second=b;
        }
    }
    while(1){
        sz=spare.size();
        int cont=0;
        for(int i=0;i<sz;i++){
            if(connected[spare[i].first] && connected[spare[i].second]) cont++;
            else if(connected[spare[i].first]){
                connected[spare[i].second]=true; cnt++;
                spare.erase(spare.begin()+i);
            }
            else if(connected[spare[i].second]){
                connected[spare[i].first]=true; cnt++;
                spare.erase(spare.begin()+i);
            }
            else cont++;
        }
        if(cont==sz) break;
    }
    printf("%d\n",cnt);
}

doju 6년 전 1

굉장히 비효율적입니다. 이 문제는 BFS 또는 DFS를 이용하여 모든 간선을 두 번 이하로 방문하고 답을 구할 수 있으며, 이렇게 해결할 경우 정점과 간선이 10만 개씩 되더라도 빠르게 답을 구할 수 있습니다.
그러나 이 풀이에서는 최악의 경우 하나의 간선을 n번에 가깝게 방문하게 됩니다. 아래와 같은 예시에서 프로그램이 어떻게 동작할지 생각해 보세요.

또한 vector의 erase 연산 역시 비효율적입니다. vector의 중간에 있는 값을 지울 경우 그 뒤에 있는 값들을 전부 한 칸씩 앞으로 당겨 와야 하므로, vector에 들어 있는 원소의 개수에 비례하는 시간이 걸립니다.

dreamian 6년 전 0

답변 달아주셔서 정말 감사합니다.

듣고보니 정말 비효율적이네요 ㅠㅠ

입력 예시까지 들어주셔서 이해하는데 정말 도움이 되었습니다.

조금 멍청한 질문일 수 있겠지만,

혹시, doju님께서는 원소의 삽입이나 삭제를 부득이하게 해야한다면 어떤 컨테이너로 구현하시는지 궁금합니다.

문제에 따라 다르고 구현에 따라 다르겠지만, stack이나 queue와 같은 방식으로 구현하기 복잡하다는 생각이 든다면

어떻게 구현하시나요?

당연히 문제에 따라 크게 달라서 답변을 하기가 힘드네요. 배열, set, map, segment tree, binary indexed tree 등 굉장히 다양한 자료구조를 사용합니다.
문제를 풀 때 어떤 연산이 필요한지 명확하게 정리하면 어떤 자료구조를 선택해야 할지 좀 더 쉽게 감을 잡을 수 있습니다. 물론 그 전에 다양한 자료구조들의 특징을 파악하고 있어야겠죠.

예시:

이 문제를 풀기 위해서는 임의로 원소를 삽입 혹은 삭제할 수 있어야 하고, 원소는 크기순으로 정렬되어 있어야 하며, n번째 원소를 찾을 수 있어야 함
set은 원소의 삽입과 삭제를 O(log n)에 할 수 있고, 원소를 크기순으로 정렬하여 저장하지만 n번째 원소를 찾을 수 없음
그러므로 set은 이 문제를 풀기에 적합한 자료구조가 아님

팁을 하나 드리자면, 지금 작성하신 코드와 같이 한 번 원소들을 전부 삽입한 뒤에는 원소의 삭제만 일어나고 원소의 순서가 섞여도 별 상관 없는 경우 vector로 관리하면서 삭제할 원소와 마지막 원소를 swap하고 크기를 1 줄여 버리면 빠르게 삭제할 수 있습니다.

dreamian 6년 전 0

답변 정말 감사드립니다!

많은 도움이 되었습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제는 맞았지만 궁금한 점이 있습니다

dreamian 6년 전 0

doju 6년 전 1

dreamian 6년 전 0

doju 6년 전 1

dreamian 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말