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

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

강의자료/알고리즘 수학

[사고력수학] 놀이공원에 간 원당이

원당컴1 2021. 8. 4. 14:05
원당이는 이번 설에 세뱃돈을 받아서 놀이공원에 갔습니다.
세뱃돈을 가지고 한 종류의 놀이 기구만 탄다고 하면 회전목마 50번, 롤러코스트 100번, 바이킹 120번,대관람차 150번,범퍼카 60번을 탈 수 있습니다.
원당이는 5가지의 놀이기구를 똑같은 횟수로 타고 싶어 합니다.(자유이용권은 생각하지 않습니다.)
그렇다면 원당이가 가지고 있는 돈으로 최대한 몇회를 탈 수 있는지 계산을 해주세요.

문제풀이)

이 문제는 최소공배수를 활용해서 문제를 풀수 있습니다.
회전목마 50번,롤러코스트 100번,바이킹 120번,대관람차 150번,범퍼카 60번의 최소공배수는 600 입니다.
만약 600원의 세뱃돈이라고 하면 한번 타는데 회전목마는 12원,롤러코스트는 6원,바이킹은 5원,대관람차는 4원,범퍼카는 10원입니다.
따라서 한번씩 5개를 타는 비용은 12 + 6 + 5 + 4 + 10 = 37 원입니다.

600 / 37 = 16.21... 이므로 최대 16번을 탈 수 있습니다.

정답) 16

 

컴퓨팅 사고력

컴퓨터과학에서는 어떤 문제를 해결 할때 최대공약수와 최소공배수를 활용하여 해결하는 경우가 많습니다.

이때 a와 b의 최대공약수를 구할때 어떤 수를 1부터 a까지 증가 하면서 a와 b를 나누어서 나누어 떨어지는 가장 큰 수를 최대공약수로 선택할 수 있습니다.

for(int i=1;i<=a;i++)
{
	if(a%i==0 && b%i==0) gcd = i;
}

하지만 이 방법은 속도가 느리기 때문에 유클리드 호제법을 사용해서 두 수의 최대공약수를 구하게 됩니다.

2018.11.09 - [강의실/정보영재] - 유클리드 호제법 증명

 

유클리드 호제법 증명

유클리드 호제법은 2개의 자연수 또는 정수의 최대 공약수를 구하는 알고리즘의 하나 입니다. 정보올림피아드에서 2개의 최대 공약수를 구하는 문제가 종종 나오는데... 이때 유클리드 호제법을

wondangcom.com

long long gcd(long long a,long long b)
{
      if(b==0) return a;
      return gcd(b,a%b); //여기서 r = a % b 입니다.
}

최소 공배수를 구하는 방법 역시 a부터 a씩 증가 하면서 a와 b로 나누어 떨어지는 첫번째 수임을 판별 할 수 있습니다.

for(int i=a;;i+=a)
{
	if(i%a==0&&i%b==0) lcm=i,break;
}

하지만 이렇게 구하는 것보다 a 와 b의 두수의 곱이 최대공약수 * 최소공배수 인 것을 이용하여 해결하면 최대공약수를 유클리드호제법을 사용하여 구하는 속도 밖에는 안 걸리기 때문에 훨씬 빠른 속도로 해결 할 수 있습니다.

long long lcm(long long a,long long b)
{
	return a*b/gcd(a,b)
}

 

여러 개의 숫자가 들어 오는 경우 예를 들면 a,b,c 의 최대 공약수(또는 최소공배수)를 구하는 경우 a와 b의 최대공약수(또는 최소공배수)를 구한 후 그 최대공약수(또는 최소공배수)와 나머지 c의 최대공약수(또는 최소공배수)를 구하면 최대공약수(또는 최소공배수)가 됩니다.

//a,b,c의 최대공약수 구하는 법
long long g = a;
g=gcd(g,b)
g=gcd(g,c)

//a,b,c의 최소공배수 구하는법
long long l = a;
l=lcm(l,b)
l=lcm(l,c)

 

 

오늘도 최선을 다하는 우리 학생들을 응원합니다.

인천 서구 검단신도시 원당컴퓨터학원

 

원당컴퓨터학원에서는?

1. 4차 산업 시대의 흐름은 컴퓨터를 얼마나 이해하느냐에 따라 삶의 질이 틀려 질 수 있다는 것을 항상 염두에 두고 있습니다.

2. 알고리즘은 프로그래밍의 근원이 되는 문제해결 능력이며, 머신러닝은 IoT등에 의해 모여진 데이터를 활용하는 기법입니다.

3. 이에 따라 초,중,고 학생들이 알기 쉽게 이해하는 인공지능 부터 알고리즘까지 학생들의 실력에 맞춰 수업을 진행중에 있습니다.

4. 현재 초등학생이 고등학생이 되는 때에는 고교학점제 도입에 따라 자신이 전공하고자 하는 특기가 크게 부각 될것입니다.

5. IT 업체중 규모가 큰 곳에서는 코딩테스트(알고리즘테스트)로 블라인드 면접을 수행하는곳이 늘고 있습니다.

6. 미래 IT를 꿈꾸는 학생들의 산실이 되기 위해 항상 최선을 다하는 원당컴퓨터학원이 되겠습니다.

 

※ 정보영재 혹은 인공지능 관련 수업에 관해 궁금하신 분은 문의(032-565-5497) 주세요.

 

 

원당컴퓨터학원 커리큘럼

- OA : 학교 수행 평가에 꼭 필요한 컴퓨터 활용능력 향상

- IT 자격증 과정 : 취업대비,대학생인증제,승진을 위한 국가공인 자격증 취득과정

- 정보영재 : 정보올림피아드 및 알고리즘 대회/소프트웨어특기자전형/디미고 특별전형 대비/코딩테스트 대비를 위한 알고리즘 과정

- 프로젝트반 : 응용프로그래밍/웹프로그래밍/앱프로그래밍 등을 통해 직접 만들어 보면서 컴퓨터 프로그래밍 이해(소프트웨어 학생부종합전형/특성화고(디미고,선린고등) 특별전형대비)

- 인공지능 : 인공지능의 이해 및 실습을 통해 빅데이터 가공(4차 산업 시대의 축이 되는 인공지능 시대를 대비)

- 과고,영재고,컴퓨터학과(SW) 대학생을 위한 내신대비 : python,java,c++,자료구조,알고리즘,이산수학 

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