강의자료/알고리즘 수학 61

[컴퓨팅사고력]컨테이너 적재하기

한 항구에 적재 되어야 할 많은 컨테이너가 있습니다. 이 컨테이너들은 색상을 가지며 이 색상에 의해 컨테이너의 종류가 구분되어 집니다. 각 색상은 컨테이너 종류를 나타내기 위한것입니다. 다음과 같이 10개 색상의 컨테이너가 있고 준비된 컨테이너들 중 2개의 컨테이너를 타이타닉호에 적재해야 됩니다. (빨,빨,빨,파,파,노,노,노,주,검) 원당이는 이것을 적재하는 경우의 수가 몇가지인지 궁금합니다. 원당이를 위해 모든 경우의 수가 몇가지인지 구해 주세요. 정답) 13가지 경우의 수) 빨,빨 빨,파 빨,노 빨,주 빨,검 파,파 파,노 파,주 파,검 노,노 노,주 노,검 주,검 문제풀이) 이러한 문제는 조합론에 기본을 둔 문제로 다양한 방법의 경우의 수를 구하는 문제입니다. 각각 중복이 가능하면서 순서가 없는 ..

[컴퓨팅 사고력] 스도쿠

에서 스도쿠를 검색하면 다음과 같이 설명을 하고 있다. 스도쿠는 18세기 스위스 수학자 레온하르트 오일러가 창안한 Latin Square 를 기반으로 하여 1979년 당시 74세의 건축가였던 미국의 Howard Garns가 현재의 모습으로 변형하여 1979년 5월 미국의 '델 매거진즈'(Dell Magazines)가 잡지 《Dell Pencil Puzzles & Word Games》에 "Number Place"로 소개된 것이 시초이나, 1984년 4월 일본의 출판사인 '니코리'(ニコリ, Nikoli)가 출판한 잡지 《퍼즐 통신 니코리》(パズル通信ニコリ)[2]에 '스도쿠'라는 이름을 붙여 수록하면서 대중에게 보급되기 시작하여 2005년 무렵에 이르러 온 세계로 퍼져 나갔다. 이러한 스도쿠는 다음과 같은 규..

[컴퓨팅 사고력] 투명띠를 반씩 접어서 한개의 사각형 만들기

원당이는 다음과 같이 1 부터 32까지 적힌 투명띠를 가지고 있다. 이 투명띠를 왼쪽으로 절반씩 접어서 한개짜리 사각형으로 만들려고 한다. 즉 한번을 접게 되면 1~16이 아래에 있고 32~17이 위에 있게 된다. 이 투명띠는 고무줄과 같이 탄성이 좋아서 접히는 위치는 접히는 횟수의 높이에 관계 없이 정확히 접힌다고 가정하자. 1) 몇번만 접으면 한개의 사각형으로 만들 수 있겠는가? 2) 맨 위에 적힌 번호는 무엇인가? [문제풀이] 맨아래/ 맨위 로 표현을 해 보면 다음과 같은 순서로 나타날 것이다. 1단계) 1~16/32~17 2단계) 1~8/16~9 3단계) 1~4/8~5 4단계) 1~2/4~3 5단계) 1~1/2~2 즉 5번이면 한개의 사각형을 만들 수 있고 맨 위에 적힌 번호는 2이다. 컴퓨팅 사..

[컴퓨팅 사고력] 2 * 10 크기의 벽을 채우는 경우의 수를 구해 보자.

다음과 같이 2 * 10 크기의 벽이 있는데 원당이는 1*2 짜리 타일 10개를 벽에 붙여야 합니다. 원당이는 갑자기 이 타일을 동일한 모양이 아니고 세우거나 눕히거나 해서 붙이는 경우의 수가 궁금해 졌습니다. 만약 2 * 1 짜리 벽이라면 다음과 같이 세워서 붙이는 경우 한가지 밖에 없습니다. 하지만 2*2짜리 벽이라면 다음과 같이 2가지 경우의 수가 생깁니다. 두개를 세로로 세우는 경우와 가로로 눕히는 경우 그렇다면 원당이를 도와서 2*10크기의 벽에 1*2짜리 타일 10개를 벽에 붙이는 경우의 수를 여러분이 구해 주세요. [문제풀이] 1단계) 2*1짜리 벽이라고 하면 세로로 세울 수 있는 경우의 수 1가지 2단계) 2*2짜리 벽이라고 하면 2*1짜리 벽에 2*1짜리 벽이 더 추가 되는 개념이므로 2..

[컴퓨팅사고력] 논리추론 문제

A,B,C 세 사람은 10문제의 쪽지 시험을 보았다. 쪽지 시험은 O 또는 X 중에서 하나를 답으로 고르는 것으로, 반드시 둘 중 하나가 정답이다. 다음과 같은 답안지를 채점한 결과 다음과 같을때 답이 X인 것을 모두 고르시오. 1 2 3 4 5 6 7 8 9 10 점수 A의 답안지 O X O X O O X X O X 70 B의 답안지 X X O O O X O O X X 70 C의 답안지 X O O O X O O X O O 70 문제풀이) A와 B의 답안을 살펴 보면 A와 B가 같은 답안이 4개 다른것이 6개이다. 여기서 세명이 모두 7개씩 맞혔으므로 맞은 문제는 4개이고 나머지 6개 중에서 3개씩 맞았다는 것이 된다. A와 C의 답안을 살펴 보면 A와 C가 같은 답안이 4개 다른것이 6개이다. 동일하게..

[사고력수학] 거꾸로 생각해 보기

정보올림피아드 또는 수학 올림피아드에서 거꾸로 생각하는 방법은 자주 사용되는 방법입니다. 응용문제나 문장의 결과를 서술하는 것에서 시작하여 이미 알고 있는 조건을 이용하여 한발자국 한발자국 거꾸로 분석하고 추리하면서 문제를 해결하는 방법입니다. 거꾸로 생각하여 푸는 방법 1. 문제를 읽고 조건을 순서대로 정리합니다. 2. 문제의 조건을 식 또는 그림으로 간단히 나타냅니다. 3. 마지막 결과에서부터 거꾸로 계산합니다. 4. 더하기빼기, 곱하기나누기 문제유형 살펴보기 수학 시험을 본 후 미혜는 선희에게 몇점이냐고 물었습니다. 선희는 "내가 맞은 점수에 8점을 뺀 후 10을 더하고 그 수를 7로 나눈 후 4를 곱하면 56이 된다." 라고 대답했습니다. 선희의 수학점수는 몇점입니까? 문제풀이) 마지막 이 56인..

[컴퓨팅사고력] 무인도에 갇힌 원당이를 위해 조난 신호를 만들어 주세요.

원당이는 배를 타고 낚시를 하다가 갑자기 풍랑을 만나 무인도에 떠 밀려 가게 되었습니다. 배는 다시 수리가 불가능 할 정도로 파손이 되어 있어서 배를 수리해서 빠져 나가는 것은 무리가 있습니다. 무전기 역시 망가져서 무전을 했는데~ 잡음이 너무 심해서 상대방과 통화를 할 수가 없습니다. 하지만 다행스럽게도 통화는 할 수 없지만 신호를 보내는 것은 가능합니다. 짧게 누르거나 길게 누르는 것으로 조난 구조 신호를 보내고 싶습니다. 국제 모스 부호는 다음과 같습니다. 무전기를 이용해서 점과 선으로 만들어진 모스 부호를 짧게 누르면 점, 길게 누르면 선을 표현 할 수 있습니다. 상대방이 SOS 구조 신호를 받을 수 있도록 여러분이 도와 주세요. 문제풀이) S 는 점점점 O 는 선선선 입니다. 따라서 SOS 는 ..

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

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

[컴퓨팅사고력] 간장 공장 공장장~ 문장 압축해 보기

원당이가 컴퓨터 시간에 수업을 듣는데 선생님이 다음과 같은 숙제를 내 주셨습니다. "간장 공장 공장장은 강 공장장이고 된장 공장 공장장은 공 공장장이다" 를 이진수를 이용해서 표현해 볼 수 있도록 나타내되 그 길이가 가장 짧게 표현을 해 보라고 하셨습니다. 원당이를 위해 이 문제를 어떻게 해결할지 고민해 주세요. 문제풀이) 이러한 문제는 허프만 코드라고 하는 압축 알고리즘을 사용하면 됩니다. 허프만 알고리즘의 특징은 발생빈도가 적은 문자를 많은 비트를 사용하고 발생빈도가 많은 문자를 적은 비트를 사용하게 되면 가장 최소의 비트로 어떤 텍스트 파일을 압축할 수 있는 알고리즘입니다. 먼저 허프만 알고리즘의 원리에 대해 알아 보겠습니다. 1) 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리를 생성..

[컴퓨팅 사고력] 시저 암호로 암호화 하기

시저암호란? 카이사르암호(Caesar cipher) 또는 시저암호는 암호학에서 다루는 간단한 치환 암호의 일종이다. 위와 같이 암호화 하고자 하는 내용을 알파벳별로 일정한 거리만큼 밀어서 다른 알파벳으로 치환하는 방식이다. 2개의 회전 디스크를 구성하여 코드를 암호화 하거나 암호 해독 할 수 있다. 위와 같이 회전디스크를 이용하여 회전을 시킨후에 WONDANGCOM 을 암호화 한다고 하면 ZRQGDQJFRP 로 암호화 할 수가 있게 된다. 이렇게 3칸씩 뒤에 있는 값으로 암호화 하는 방식이므로 for(i=0;i