강의실/정보영재

알고리즘 대회에서는 어떤 문제를 이해하고 그문제에서 어떤 규칙을 찾아 프로그래밍을 얼마나 빨리 하는가 하는 대회입니다.

 

이때 문제를 읽고 이해하는데 독서를 많이 한 학생일 수록 더 빨리 이해하는 것을 알 수 있는데요.

 

이러한 규칙을 찾을때 어떤 문제에서 핵심을 찾는 능력이 중요합니다.

 

2019년 중등부 2번 개구리점프 같은 문제는 다음과 같이 나왔는데요.

 

여기서 y축을 생각하느라고 고민을 많이 하고 시간을 허비할 수가 있는데요.

 

실제로 이 문제에서는 개구리가 y축으로는 어느 높이나 뛰어 올라 갈 수 있기 때문에 개구리가 점프 하지 않고 걸어가는 문제의 수직선 문제로 변환하면 생각하는 것이 단순화 됩니다.

 

이때 이러한 부분을 얼마나 빨리 깨닫는가 하는 부분은 실제로 대회에서 등수를 가르는 문제이기도 합니다.

 

이때 입력이 다음과 같이 들어온 경우를 보겠습니다.

 

이것을 단순화 시켜 보면

(1,5)(3,7)(7,9)(10,13)

의 선이 연결되어 있는지 안되어 있는지만 살펴 보면 됩니다.

이때 1,2,3 은 연결이 되어 있고 4는 연결 되어 있지 않은것을 알 수 있습니다.

 

x1을 기준으로 정렬을 한 후에 그룹 번호를 매겨 준 다음 1번과 3번이 같은 그룹 번호인지 아닌지, 1번과 4번이 같은 그룹번호인지 아닌지만 체크하면 됩니다.

 

위의 문제를 단순화 시키고 문제를 풀어 보면 다음과 같이 풀어 주면 됩니다.

그룹번호 = 1

처음 시작 1, 끝나는 점 5 : 그룹번호 1

그 다음 나오는 3,7 이므로 시작과 끝점 사이에 있으므로 연결 되는 선이다.

따라서 처음 시작 1, 끝나는 점 7 로 연결 되면서 : 그룹번호 1

그 다음 7,9 이므로 그 이전 선과 연결 되므로 끝점만 연장하면서 그룹번호 1을 매긴다.

그리고 10,13 이 나오므로 끝나는 점과 연결이 되지 않는 것을 알 수 있습니다.

 

이렇게 단순화 시키면 그리디 알고리즘인 것을 알 수 있네요.

 

이렇게 대회에서 규칙을 찾아내서 어떤 알고리즘을 사용할 것인지 찾아 내면 문제를 해결 한 것이나 다름이 없는데요.

 

이러한 문제를 코딩 해 보면 다음과 같습니다.

 

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <cstring>

 

using namespace std;

struct line{

    int x1,x2,y;

    int num;

}Log[101000];

 

int group[101000];

 

int n,q;

 

bool cmp(line a,line b)

{

    return a.x1 < b.x1;

}

 

 

int main()

{

    int gnum=1;

    int f_l;

    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++)

    {

        scanf("%d %d %d",&Log[i].x1,&Log[i].x2,&Log[i].y);

        Log[i].num = i;

    }

    sort(Log+1,Log+n+1,cmp); //x1으로 정렬한다.

 

    group[Log[1].num] =  gnum; //처음에 나오는 통나무에 그룹번호를 매겨준다.

    f_l = Log[1].x2;

    for(int i=2;i<=n;i++)

    {

        if(Log[i].x1 <= f_l)

        {

            group[Log[i].num] = gnum; //연결이 된다고 하면 그 전의 그룹번호를 매겨 준다.

            f_l=max(f_l,Log[i].x2);          //끝나는 점을 둘중 큰걸로 연결해 준다.

        }

        else

        {

            group[Log[i].num] = ++gnum;  //연결이 안된다고 하면 그룹번호를 증가 시켜 준다.

 

            f_l=Log[i].x2;

        }

    }

    for(int i=1;i<=q;i++)

    {

        int a,b;

        scanf("%d %d",&a,&b);

        printf("%d\n",group[a]==group[b]); //그룹번호가 같은지 아닌지만 출력하면 된다.

    }

    return 0;

}

 

 

 

알고리즘 대회를 준비하는 학생들이라면 이렇게 문제에서 필요없는 부분을 무시 할 줄 아는 힘을 키우는 것도 한 방법이겠네요.

 

오늘도 열심히 공부하는 우리 학생들을 응원합니다.

 

인천 서구 원당컴퓨터학원

 

'강의실 > 정보영재' 카테고리의 다른 글

대회에서 문제풀이 팁  (10) 2020.03.04
알고리즘 대회 - 규칙찾기(무시하는 힘)  (11) 2020.02.14
AI 발전의 역사  (13) 2020.02.03
순열과 조합의 개념  (12) 2020.01.24
변수명 짓기 사이트  (11) 2020.01.15
오토마타란  (12) 2020.01.13
  • 드래곤포토 2020.02.14 11:59 신고    

    저도 학생들을 응원합니다.
    즐거운 주말 되세요

  • 청결원 2020.02.14 15:07 신고    

    오늘 불금 마무리 잘 하시고
    즐거운 하루 보내세요~
    포스팅 잘 보고 갑니다

  • 유하v 2020.02.14 23:21 신고    

    단순한 문제인것 같기도한데 해설이 없었다면 굉장히 어렵게 느꼈을것 같습니다ㅜ

  • 핑구야날자 2020.02.15 06:57    

    규칙을 찾는 것은 재미있기도 하지만 스트레스 받는 일이기도 하지요.

  • 잉여토기 2020.02.15 07:43 신고    

    알고리즘 코딩 프로그래밍도 어렵지만 문제를 이해하는 것도 어려운 과정이네요.
    와이축을 생각지 않고 엑스축만 보는 것이 핵심이군요.

  • 평강줌마 2020.02.15 21:39 신고    

    너무 어렵네요.
    저는 알고리즘과는 거리가 먼 것 같네요.

  • 휴식같은 친구 2020.02.15 23:36 신고    

    문제의 이해도가 빨라야 해결이 되겧군요.
    잘 보고 갑니다.

  • GOFAM 2020.02.15 23:48 신고    

    포스팅 잘보고 갑니당ㅎㅎ

  • 공수래공수거 2020.02.16 15:16 신고    

    알고리즘 대회의 규칙도 알아 놓는게 좋죠.
    핵심을 빨리 찾아야 합니다.

  • 버블프라이스 2020.02.17 04:53 신고    

    알고리즘 대회 - 규칙을 아는것 매우 중요한것 같습니다.
    오늘도 도움이 되는 글을 잘 읽고 꾹 누르고 갑니다.^^

  • 조아하자 2020.02.22 14:18 신고    

    우왕... 저는 현업 출신인데도 이 문제는 쉽게 다가오지 않네요. 역시 배워야 할 게 많네요.