2025년, 코딩은 선택이 아닌 필수!

2025년 모든 학교에서 코딩이 시작 됩니다. 먼저 준비하는 사람만이 기술을 선도해 갑니다~

강의자료/정보영재

패턴이나 공식 찾는 문제 알고리즘 풀이

원당컴퓨터학원 2019. 2. 6. 10:32

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



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




사업자 정보 표시
원당컴퓨터학원 | 기희경 | 인천 서구 당하동 1028-2 장원프라자 502호 | 사업자 등록번호 : 301-96-83080 | TEL : 032-565-5497 | Mail : icon001@naver.com | 통신판매신고번호 : 호 | 사이버몰의 이용약관 바로가기