[사고력수학] 운동장에서 게임하기

길동이네 학교에서 운동회가 열렸습니다. 운동회중 다음과 같은 게임이 있는데 마지막에 서 있는 사람이 승리하는 게임입니다. 게임의 원리는 다음과 같습니다. 1번부터 100번까지 100명의 학생이 원을 이루어서 서 있습니다. 여기서 시작하는 사람부터 서있는 사람 한명을 건너 뛰고 무조건 앉아야 합니다. 길동이는 반장이라서 시작위치를 정할 수가 있습니다. 길동이가 1번부터 시작을 하도록 정한다고 하면 길동이는 몇번 위치에 서 있으면 길동이가 승리하겠습니까? 여러분이 길동이에게 서 있어야 할 위치를 알려 주세요.

문제풀이)

1번째 돌때는 1번부터 뽑는다고 하면 1,3,... 99 까지 홀수번째는 모두 앉게 되고 남은 수는 50명이 됩니다.

2번째 돌때는 2번부터 2,6,10...98 까지 2부터 시작해서 4 만큼 증가 되면서 모두 앉게 되고 남은 수는 25명이 됩니다.

3번째 돌때는 4번부터 4,12,...100 까지 해서 4부터 시작해서 8 만큼 증가 되면서 모두 앉게 되고 남은 수는 12명이 됩니다.

4번째 돌때는 16번 부터 16,32,48,64,80,96 과 같이 16씩 증가 되면서 모두 앉게 되고 남은수는 6명이다.

남은수(8,24,40,56,72,88)

5번째 돌때는 8,40,72 가 앉게 되고 24,56,88 이 남는다.

6번째 돌때는 24,88 이 앉게 되고 56 이 남는다.

정답) 56

 

컴퓨팅 사고력

컴퓨터 과학에서 요세푸스문제(Josephus problem) 이라는 문제로 유명한 수열인데 이 문제는 다음과 같이 정의 된다.

n과 k가 자연수이고, k < n 이라고 가정하고 n명이 동그랗게 모여 있을 때 임의의 한명 부터 순설르 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을때 까지 계속해서 반복한다. 이 때 모임에서 제외되는 사람의 순서를 (n,k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

이러한 문제를 해결하는 방법으로는 다음과 같이 구할 수 있다.

n이 1이라고 하면 다음과 같이 f(1,k) =1 이라는 초항을 구할 수 있다.

n과 k 사이의 관계식을 구하면 다음과 같다.

f(n,k) = ((f(n-1,k) + k - 1) mod n ) + 1

만약 사람의 순서를 1번째부터가 아닌 0번째 부터라고 하면 다음과 같이 단순화 할 수 있다.

f(1,k) =0;

f(n,k) = ((f(n-1,k) + k - 1) mod n )

이러한 문제는 다음과 같은 코드로 구현이 가능하다.

long long joseph (long long n,long long k) {
    if (n==1LL) return 0LL;
    if (k==1LL) return n-1LL;
    if (k>n) return (joseph(n-1LL,k)+k)%n;
    long long cnt=n/k;
    long long res=joseph(n-cnt,k);
    res-=n%k;
    if (res<0LL) res+=n;
    else res+=res/(k-1LL);
    return res;
}

 

이렇게 사고력 문제를 풀다 보면 컴퓨터 과학에서 필요한 문제들의 해결 원리가 숨어 있는 것을 확인 할 수가 있네요.^^

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

 

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

 

 

 

원당컴퓨터학원에서는?

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

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

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

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

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

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

 

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

 

 

원당컴퓨터학원 커리큘럼

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

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

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

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

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

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