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

[사고력수학] 규칙을 찾아 문제 해결하기

문제 다음의 문제에서 규칙을 찾아서 다음의 문제를 해결하세요. ONE + TWO = 217460 FOUR - THREE = 4070263 TEN - ONE = 5369 ONE + TEN = 35659 위와 같은 규칙이 있을때 FIVE - FOUR 의 값을 구하세요. 힌트) Z - A = 25 문제풀이 A B C D E F G H I J 1 2 3 4 5 6 7 8 9 10 K L M N O P Q R S T 11 12 13 14 15 16 17 18 19 20 U V W X Y Z 21 22 23 24 25 26 O(15)N(14)E(5) + T(20)W(23)O(15) = 15145 + 202315 = 217460 F(6)O(15)U(21)R(18) - T(20)H(8)R(18)E(5)E(5) = 61..

[컴퓨팅 사고력] 최단경로를 찾아 보자.

길동이는 설을 맞이해서 서울에서 생활하는데 부산에 있는 부모님 댁에 가려고 합니다. 다음과 같이 시간이 주어질때 가장 빨리 부모님 댁에 갈 수 있는 시간은 어떻게 될지 그리고 경로는 어떻게 될지 여러분이 길동이한테 설명을 해 주세요. 문제풀이) 먼저 서울에서 출발을 하는데 서울에서 가장 빨리 갈수 있는 광주를 선택 합니다. 광주에서 빨리 갈 수 있는 대전을 선택 후 대전에서 빨리 갈 수 있는 강릉을 선택후 강릉에서 부산을 선택하는 경로를 생각해 볼 수 있습니다. 이때는 1시간 + 3시간 + 1시간 + 1시간 = 6시간이 걸립니다. 하지만 여기서 가장 빨리 갈 수 있는 방법은 서울에서 대전을 거쳐 강릉-> 부산으로 가는 길이 5시간으로 가장 빠릅니다. 이 것을 찾는 방법으로는 다음과 같이 생각을 해 볼 수..

[컴퓨팅사고력] 길동 형사를 도와 주세요.

길동이는 어려서 부터 꿈이 나쁜사람을 잡는 형사였습니다. 어른이 되어서 이제 막 형사가 된 길동이는 잠복 수사를 하게 되었습니다. 범인의 인상착의와 비슷한 사람이 길동형사 앞을 지나가서 길동형사는 그 사람을 불러 세우고 불심검문을 하였습니다. 하지만 그 사람이 불러준 주민번호를 전산시스템에 입력하여 조회를 하는데 아무리 기다려도 조회가 되지 않습니다. 현재 길동형사가 조회하는 시스템은 다음과 같이 구성이 되어 있습니다. 1) 우리나라 인구 5000만명의 주민등록 번호가 모두 등록이 되어 있습니다. 2) 등록된 정보는 주민번호가 빠른 순서 부터 순서대로 정렬이 되어 등록이 되어 있습니다. 3) 시스템에서 조회되는 속도는 1초에 100건씩을 조회하여 처리 됩니다. 4) 조회되는 순서는 앞에서 부터 순차적으로..

[컴퓨팅 사고력] 컴퓨터 비밀번호를 풀어 보자

길동이는 길순이 집에 과제를 하기 위해 놀러 갔습니다. 과제를 하던 중에 인터넷에서 검색을 해야 되는 문제가 있어서 컴퓨터 전원을 켰습니다. 하지만 컴퓨터에는 비밀번호가 걸려 있었고 모니터 상단에 쪽지로 힌트가 다음과 같이 적혀져 있었습니다. 87,79,78,68,65,78,71,67,79,77 길동이와 길순이에게 비밀번호가 무엇인지 알려 주세요. 정답) WONDANGCOM 이었습니다. 컴퓨터는 이진수체계인 0과 1만을 인식하고 있습니다. 컴퓨터가 정보로 인식하는 최소 단위는 비트(bit) 라고 하며 0과 1로 구성되며 8개의 비트를 한 단위로 묶어서 바이트(byte)라고 하며 이렇게 한 바이트는 정보처리의 기본 단위로 사용합니다. 이렇게 8개의 비트를 사용하면 10진수로 0부터 255까지 표현이 가능합..

[컴퓨팅 사고력] 사이다 와 콜라의 내용물을 바꿔 보자

길동이는 커피숍에서 아르바이트를 하고 있습니다. 손님이 와서 콜라와 사이다를 주문하였는데~ 길동이는 잠깐 다른 생각을 하느라고 콜라잔에 사이다를 채우고 사이다잔에 콜라를 채웠습니다. 이대로 손님에게 드린다고 하면 손님은 항의를 할것 이고~ 이것을 다시 버리고 새로 사이다 콜라를 따르게 되면 길동이의 아르바이트 비용에서 사이다 콜라 값을 변상해야 됩니다. 우리가 길동이의 고민을 풀어 주세요. 문제풀이 1단계) 빈 컵을 가져 와서 콜라잔에 든 사이다를 붓고 콜라잔을 깨끗이 씻는다. 2단계) 사이다잔에 든 콜라를 콜라잔에 붓고 사이다잔을 깨끗이 씻는다. 3단계) 빈컵에 있던 사이다를 사이다잔에 붓는다. 컴퓨팅 사고력 이 문제는 프로그래밍 구현시에 다음과 같이 두개의 변수값을 변경하는 경우에 사용되는 방법입니다..

[컴퓨팅 사고력]해시(Hash)테이블 이해하기

길동이는 주차장에서 일을 하고 있습니다. 주차장은 5개 구역으로 나누어져 있고 1개 구역에는 10대씩을 세워 둘 수 있습니다. 길동이가 하는 일은 손님이 오면 손님의 차를 대신 주차 구역에 주차를 시켜 주고 찾으러 오면 차를 찾아서 전달해 주는 역할을 합니다. 하지만 차가 많아지면서 차를 어디에 두었는지 찾기가 힘들어 졌는데요~ 꾀 많은 길동이는 다음과 같은 아이디어를 생각해 냈습니다. 차의 뒷번호를 확인해서 뒷번호가 1,6 이면 1번 구역에 2,7이면 2번 구역에 3,8 이면 3번 구역에 4,9이면 4번 구역에 5,0 이면 5번 구역에 주차를 해 놓은 후에 손님이 찾는 번호만 확인하여 그 위치를 찾아 주었습니다. 그런데 하루는 50대를 주차 할 수 있는 주차장에 5대 밖에 주차를 하지 않았는데 1번구역..

[컴퓨팅 사고력] 피보나치 수열

피보나치 수열이란? 피보나치 수열의 유래는 피사의 레오나르도로 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대해 연구하기 시작되었으며 다음과 같은 수열을 피보나치 수열이라고 합니다. 1항 2항 3항 4항 5항 6항 7항 8항 9항 10항 1 1 2 3 5 8 13 21 34 55 이 수열의 규칙은 1항과 2항은 각각 1이고 3항 부터는 전항과 전전항의 값을 더한 값이 됩니다. 피보나치 수열에 관한 문제유형 일반적으로 피보나치 수열을 응용한 문제가 정보올림피아드 수학에서 종종 나오고 있으며 특히 알고리즘 분야에서는 동적알고리즘을 배울때 처음 만나게 되는 수열중에 하나 입니다. 그렇다면 정보올림피아드에서 나왔던 기출문제를 풀어 보겠습니다. 정보올림피아드 2003년 초등부 10번 ..

[초등 사고력 풀이비법] 합과 차의 관계를 이용해 해결하기

이러한 유형의 문제는 정보올림피아드 기출문제 유형에서 자주 볼 수 있는 유형인데요. 합과 차에 관한 문제는 크고 작은 두 수의 합을 알고 또 이 두 수의 차이를 알고 있을때 두 수를 구하는 응용 문제입니다. 예를 들면 " 길동이가 가지고 있는 필통에서 연필을 2자루 꺼내니 길순이가 가지고 있는 필통의 연필의 개수가 같습니다." 라고 한다면 길동이는 길순이보다 2개 더 많은 연필을 가지고 있음을 알 수 있습니다. 이러한 원리를 응용하여 풀어 볼 수 있는 문제는 다음과 같습니다. 1. 구슬 111개를 길동이와 길순이가 나누어 가졌습니다. 이때 길동이가 가지고 있는 구슬이 길순이가 가지고 있는 구슬 보다 33개가 더 많다면 길동이가 가지고 있는 구슬은 몇개 이겠습니까? 더보기 길동이가 가지고 있는 구슬을 X개..

[컴퓨팅 사고력]블록쌓기 게임으로 스택 구조 이해하기

두 사람이 각각 하나의 블록을 쌓거나 내려 놓을 수 있는 놀이를 한다고 가정할 때 두 사람이 만들어 낼 수 있는 블록 모양을 생각해 보자. 각 블록에는 수가 쓰여져 있으며 이 수들은 절대 두번 이상 나오니 않는다. 또한 두 사람은 블록에 쓰여진 수에 따라 차례대로 쌓을 수 있으며 한번 쌓여진 블록은 다음 사람에 이해서 내려지면 다시는 사용할 수가 없다. 다음 블록의 모양을 보고 두 사람이 어떻게 블록을 쌓아 올라갔는지 생각해 보자. 가) 의 경우는 두사람이 차례대로 1,2,3,4 를 쌓아 올린 것이다. 나) 의 경우에는 첫번째 사람이 1을 올리고 두번째 사람이 2를 올린것을 첫번째 사람이 2를 내린 후 두번째 사람이 3을 올리고 첫번째 사람이 4를 올렸음을 알 수 있다. 즉 첫번째 사람은 1,4를 올리고..

[컴퓨팅 사고력]카드 마술에서 배우는 이진법

위의 A B C D 4개의 카드가 있습니다. 여러분은 1 ~ 15 까지의 숫자를 생각한 다음 ABCD 의 카드 중에서 자신이 생각한 숫자가 있는 카드를 답하세요. 예를 들어 12를 생각 했다고 하면 AB 와 같이 말해 주시면 됩니다. 만약 여러분이 ABD를 선택 하셨다면 여러분은 13을 생각하셨을 것입니다. 혹은 AB를 선택하셨다면 12를 생각하셨을 것입니다. 위의 게임은 상대방이 생각한 숫자를 맞추는 카드마술인데요. 이 게임에는 컴퓨터 과학에서 가장 필요로 하는 이진법의 원리가 숨어 있습니다. 이진법에는 0과 1 두개의 숫자만을 이용하는 수 체계입니다. 컴퓨터과학에서 왜 이진법이 중요할까요? 왜냐하면 컴퓨터는 전기 신호를 가지고 동작을 할 수 있는 기계이기 때문입니다. 전압이 높으면 1, 전압이 없으면..