알고리즘 대회 - 규칙찾기(무시하는 힘)

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

 

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

 

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

 

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; }

 

 

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

 

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

 

인천 서구 원당컴퓨터학원