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

[컴퓨팅사고력] 지워진 ISBN 번호를 찾아 보자.

원당이는 한빛도서에서 책을 하나 구매했는데 홈페이지에 ISBN 코드를 인증 받으면 포인트를 준다고 합니다. 그런데 어린 동생이 ISBN의 가장 마지막 자리를 사인펜으로 낙서를 해 놓는 것 때문에 ISBN 코드로 인증을 받지 못하게 되었는데 인터넷으로 ISBN 에 대해 검색을 하니 ISBN 에 대해 다음과 같이 설명이 되어 있습니다. ISBN(International Standard Book Number)는 국제적으로 책에 붙이는 고유한 식별자이다. ISBN체계는 원래 1966년 영국에서 "표준 도서 번호"(SBN)라는 이름으로 만들어졌고, 1970년 국제 표준화 기구에 의해 ISO 2108이라는 표준으로 채택되었다. 본래 ISBN은 10자리였지만 2007년 1월 1일 이후부터는 유럽상품번호(EAN)에 맞..

[컴퓨팅사고력] 염기서열의 공통 부분 서열을 찾아 보자.

원당이는 생명공학의 DNA 에 대해 연구 하고 있습니다. DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다. 고릴라의 염기서열을 분석해 보니 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열을 분석해 보니 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다. 원당이는 이 두개의 염기서열에서 공통부분 서열 중에 최대로 긴 부분 서열을 구하고 싶습니다. 여기서 부분서열이란 원래 문자열에서 임의적으로 몇개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열을 말합니다. 즉 ATGC 와 ATCT 의 가장긴 부분수열은 ATC 3개 입니다. ATGC 에서 G를 제거 하고 ..

[컴퓨팅사고력] 약수물을 뜨는 시간을 최소화 해보자

원당이가 사는 원당동 금정산에는 약수터가 있습니다. 약수터의 물은 1초에 1리터씩을 담을 수 있습니다. 원당이가 약수터에 올라가 보니 사람들이 약수통을 들고 가장 최소한의 시간을 대기해서 물을 받으려면 어떤 순서대로 받는것이 가장 좋을지 논의 하고 있었습니다. 지금 약수터에 물을 받고 싶어하는 사람은 네명이며 첫번째 사람은 3리터, 두번째 사람은 5리터, 세번째 사람은 2리터, 네번째 사람은 1리터 들이 물통을 가지고 있습니다. 이때 첫번째,두번째,세번째,네번째 순으로 물을 받는다면 대기한 시간은 첫번째 사람은 자신의 물을 받는 시간 3초 + 두번째 사람은 3초 대기후 자신의 물을 받는 시간 5초 이므로 8초 + 세번째 사람은 8초 대기후 자신의 물을 받는 시간 2초 이므로 10초 + 네번째 사람은 10..

[컴퓨팅사고력] 이집트 분수

이집트 분수(Egyptian fraction)는 다음과 같은 별개의 단위분수의 유한개의 합의 형태를 가리킵니다. 예를 들어 5/7 을 이집트 분수로 표현하면 다음과 같이 표현합니다. 5/7 = 1/2 + 1/5 + 1/70 이러한 이집트 분수는 이집트에서 기원전부터 사용한 역사적인 사실 외에도 분수의 또 다른 표현에서 몇가지 실질적인 잇점이 있습니다. 예를 들어 이집트 분수는 많은 개체를 동일한 공유로 나누는데 도움을 줄 수가 있는데 8명이 식사를 하는데 5개의 피자를 똑같이 나누고 싶습니다. 이것을 이집트 분수로 표현하면 다음과 같이 됩니다. 5/8 = 1/2 + 1/8 이것은 피자 4개를 절반으로 나누어서 8명에게 1/2 씩 주고 나머지 한개를 8조각으로 나누어서 1/8로 나누어 줄 수 있다는 의미가..

[컴퓨팅사고력] 회의실을 최대 몇팀에게 배정을 해 줄 수 있을까요?

원당이 아빠는 회사에서 회의실을 관리하는 관리자 입니다. 아빠가 회사에서 회의실을 사용하겠다는 회의실 신청서를 가져 왔는데~ 신청 한 사람이 많아서 누군가의 신청서는 반려해야 합니다. 아빠는 최대한 많은 팀이 회의실을 사용하기를 원하고 최소의 팀에게 신청서를 반려 하고 싶습니다. 신청서가 다음과 같다면 몇팀을 배정하고 몇팀을 반려하는 것이 최선인지 찾아 주세요. 단 끝나는 시간에 딱 맞춰 다른 팀이 들어 갈 수 있다고 가정 합니다. 회의팀 시작시간 끝나는시간 1 3 5 2 1 4 3 2 13 4 5 9 5 5 7 6 1 6 7 8 11 8 8 12 9 12 14 문제풀이) 맨 처음 2번 팀을 배정 하면 4시에 끝납니다. 그 다음 5번 팀을 배정 하면 7시에 끝납니다. 그 다음 7번 팀을 배정 하면 11시..

[컴퓨팅사고력] 1.4kg을 채울 수 있는 가방에 최대 가치를 찾아 보자.

원당이는 동생과 같이 숨바꼭질을 하다가 창고에서 보물지도를 발견하였습니다. 원당이는 동생과 함께 자신의 가방을 가지고 보물찾기에 나섰습니다. 원당이의 가방은 최대 1400g을 채울 수 있는 가방입니다. 무게를 초과하면 가방의 끈이 떨어져서 가방을 사용 할 수 없게 됩니다. 이때 가방이 자유자재로 늘어나는 소재라서 부피는 관계가 없이 담을 수 있습니다. 보물이 있는 동굴에 들어서니 다음과 같은 보석들이 있습니다. 한덩어리가 200g 인 루비는 가치가 40만원입니다. 한덩어리가 500g 인 비취는 가치가 110만원입니다. 한덩어리가 1kg인 다이아몬드는 가치가 200만원입니다. 한덩어리가 300g 인 금은 가치가 50만원입니다. 위와 같은 보석들이 쌓여 있는데 원당이는 어떤 조합으로 가지고 나올때 최대가치는..

[컴퓨팅 사고력] 논에 물을 공급하기

다음 그림과 같이 강에서 부터 각 마을까지는 파이프로 연결이 되어 있는데 각 연결 되어 있는 파이프의 굵기가 서로 다릅니다. 위의 그림에서 각 숫자는 1시간에 밸브를 최대로 열었을때 흘려 보낼 수 있는 파이프의 용량입니다. 원당이는 가뭄에 대비하기 위해 강으로 부터 여러 마을을 거쳐 논까지 물을 공급할때 한시간에 최대로 보낼수 있는 물의 양을 알고 싶습니다. 여러분이 위의 그림을 보고 1시간에 흘려 보낼 수 있는 최대 양을 구해 주세요. 문제풀이) 더보기 먼저 강에서 A,B,C 마을에 각각 물을 흘려 보내 봅니다. 그 다음 A,B,C 마을에서 통로로 보낼 수 있는 양의 물을 흘려 보내 봅니다. E에서 논으로 750을 흘려 보내고 남은 10을 D로 흘려 보낸 후 D에서 논으로 340을 흘려 보낼 수 있습니..

[컴퓨팅 사고력] 네트워크 연결

원당이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려고 합니다. 하지만 아쉽게도 허브가 없어서 컴퓨터와 컴퓨터를 직접 연결해야 합니다. 그런데 모든 컴퓨터가 자료를 공유하기 위해서는 모든 컴퓨터가 연결되어 있어야 합니다. 이때 네트워크 연결 비용을 책정해야 되는데 기왕이면 가장 작은 금액으로 연결을 하고 싶습니다. 다음과 같이 컴퓨터와 컴퓨터의 연결하는 비용이 주어졌을때 최소로 모든 컴퓨터를 연결하는 비용은 얼마인지 구해 주세요. 6대의 컴퓨터가 있으며 연결비용은 다음과 같습니다. 컴퓨터번호,컴퓨터번호- 연결비용 1,2 - 5 1,3 - 4 2,3 - 2 2,4 - 7 3,4 - 6 3,5 - 11 4,5 - 3 4,6 - 8 5,6 - 8 문제풀이) 더보기 그림으로 그려보면 위와 같습니다. 여기..

[컴퓨팅사고력]공 가져가기 게임

원당이와 길동이가 다음과 같은 게임을 하려고 합니다. 게임의 규칙은 다음과 같습니다. 규칙1) 맨 처음 게임을 시작하는 사람은 모든 공을 한번에 가져가는 것을 제외하고 임의의 수 만큼 공을 가져 갈 수 있습니다. 규칙2) 두번째 가져가는 사람 부터는 한개 이상의 공을 가져가며 상대편이 바로 전에 가져간 공의 2배 이하로만 공을 가져갈 수 있습니다. 즉 첫번째 사람이 1개를 가져갔다면 두번째는 1개 또는 2개 를 가져 갑니다. 규칙3) 마지막 공을 가져가는 사람이 이깁니다. 그렇다면 공이 현재 10개가 있습니다. 원당이가 먼저 시작하려고 하는데 원당이가 이길수 있는 방법이 있는지 궁금합니다. 만약 이길수 있다면 원당이는 처음에 몇개를 가져가야 이길 수 있을까요? 여러분이 원당이에게 알려 주세요. 정답) 더..

[컴퓨팅사고력] 프레겔 강의 7개의 다리로 배우는 그래프

18세기 초 프러시아의 옛 지점 쾨니히베르크의 중심을 흐르는 프레겔 강에 7개의 다리가 놓여있었습니다. 당시 시민들 사이에서 같은 다리를 두 번 이상 지나지 않고 이들 7개의 다리 를 꼭 한 번씩 모두 건널 수 있을지 없을지에 대한 논의가 많았는데요 만일 한 번만 다리를 지나는 것이 가능하다면 어떤 방법으로 다리를 건너야만 할까? 라는 문제입니다. 여러분이라면 이 문제를 어떻게 말할 수 있을까요? 이 문제를 해결하기 위해 오일러라는 수학자는 이 문제를 쉽고 단순하게 표현하기 위해 다리와 섬들의 사이 관계를 평면상의 점과 선분으로 표현하였습니다. 이렇게 여러 관계를 점과 선분으로 표현한 모양을 그래프라고 합니다. 즉, 위 문제를 점과 선분으로 표기 하면 다음과 같은 그림이 된다. 이처럼 그래프는 문제를 해..