강의실/정보영재

IOI 또는 기타 대회에서 애드혹 문제로 다음과 같이 패턴이나 공식 찾는 문제가 나올 수 있습니다.


이러한 문제는 문제를 푸는 사람으로 하여금 문제 설명을 주의 깊게 읽고 패턴이나 간략화된 공식을 찾도록 요구하는 문제입니다.

예를 들면 다음과 같은 문제가 있습니다.

S를 모든 정수의 제곱수가 오름차순으로 나열된 집합이라고 합니다.

즉 S={1,4,9,16,25...} 이며 정수 X는 1보다 크거나 같고 10의 17승 보다 작거나 같은 경우의 조건이 주어 졌을때 X보다 작은 것이 몇개인지 구해 보는 문제를 살펴 보면

만약에 X가 10의 17승이 나오는 경우 이 것을 하나하나 세다 보면 분명히 TLE(타임아웃) 판정을 받게 될것입니다.


이러한 문제를 곰곰히 생각해 보면 (X-1) 의 제곱근의 정수형의 갯수 인것을 파악하게 됩니다.

간단하게 26보다 작은 것의 갯수는 25의 제곱근인 5개(1,4,9,16,25) 입니다.


따라서 이러한 문제의 해법은 다음과 같이 간단한 코드로 구현할 수 있습니다.


scanf("%lld",&X);

double res = sqrt(X-1);

printf("%d", (int) res);



이러한 문제들을 풀다 보면 복잡해 보이는 문제도 패턴이나 규칙을 찾아서 쉽게 해결할 수 있는 문제가 많은 만큼 대회를 준비하는 학생들이라면 여러가지 다양한 문제들을 접해 보는 것이 중요합니다.




이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
6 0
  • 공수래공수거 2019.02.06 11:35 신고    

    패턴이나 규칙을 알면 문제 푸는데 큰 도움이 될수 있겠습니다.
    편안한 하루 되시기 바랍니다.

  • 핑구야 날자 2019.02.06 12:53    

    패턴이나 공식을 찾는 알고리즘을 찾는 것은 정말 재미 있는 일이긴 하지만 머리가 빠지는 일이기도 하지요

  • 버블프라이스 2019.02.06 12:55 신고    

    패턴이나 공식 찾는 문제 알고리즘 풀이를 해주셧군요? 학생분들이 다양한 문제를 풀어보시고 경험을 쌓은 일이 중요한 것 같습니다^^
    즐거운 휴일 보내시길 바래요

  • 평강줌마 2019.02.06 12:56 신고    

    규칙 찾기는 좋아하는데 알고리즘은 조금 어렵네요. 학원 다닐 때 열심히 했어야 했는데.....
    편안한 연휴 보내세요.

  • 휴식같은 친구 2019.02.06 15:21 신고    

    알고리즘은 복잡한걸 패턴만 찾아내면 간단하게 풀이가 될것 같습니다.
    잘 보고 갑니다.

  • *저녁노을* 2019.02.07 04:03 신고    

    어렵습니다.ㅎㅎ

    잘 보고 갑니다.
    행복한 목요일 되세요^^