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

[알고리즘 수학] 두 날짜 사이의 기간 구하기

원당이는 자신이 태어난 날짜 2004 년 1월 14일 입니다. 오늘 날짜 2022년 10월 22일까지 원당이는 자신이 몇일을 살았는지 무척 궁금합니다. 네이버에서 날짜 계산기 프로그램이 있지만 원당이는 굳이 계산기 프로그램은 사용하고 싶지 않습니다. 여기서 윤년은 2월이 29일이고 평년은 2월이 28일 입니다. 윤년의 규칙은 연도가 400의 배수이거나 4의 배수이고 100의 배수가 아닌 연도가 윤년이며 그 외의 년도는 평년입니다. 여러분이 원당이에게 어떻게 해결을 할 수 있는 지 알려 주세요. 문제풀이 프로그램의 원리로 설명을 하면 다음과 같습니다. 0년 0월 0일 부터 2022년 10월 22일 까지의 날짜를 계산 후 0년 0월 0일 부터 태어나기 전인 2004년 1월 13일 까지의 날짜를 계산해서 빼 ..

[알고리즘 수학] 등수 구하기

원당이 반 인원은 10명인데 이번에 시험을 보았는데 친구들 성적을 물어 보니 다음과 같았습니다. [ 85, 90,95,75,100,85,70,95,100] 원당이는 점수는 90점입니다. 그렇다면 원당이는 반에서 몇등을 했을까요? 문제풀이 자신보다 높은 점수가 몇명인지 세어 주면 4명입니다. 4명이 원당이보다 잘했기 때문에 원당이의 등수는 5등입니다. 프로그래밍 문제의 기초문제에서 자주 보이는 유형의 문제입니다. 이러한 문제를 해결 하기 위해서 자신의 등수를 알고 싶을 때 전체를 모두 찾아 보면서 자신 보다 높은 점수의 인원을 센 다음 +1 을 해 주면 자신의 등수가 나옵니다. 만약 모든 사람의 등수를 판별하기 위해서는 이중 반복문으로 첫번째 반복문에서는 구하고 싶은 사람을 선택 해 주고 그 다음 반복문에..

[알고리즘 수학] 쇼핑몰의 등급별 할인율을 계산해 주자.

원당 쇼핑몰에서는 회원등급에 따라 할인 서비스를 제공합니다. 회원 등급에 따른 할인율은 다음과 같습니다. 등급 할인율 Silver 5% Gold 10% VIP 20% 원당이는 원당 쇼핑몰에서 점원으로 일을 하고 있습니다. 그런데 원당이는 할인율에 대한 개념을 배우지 못해서 얼마를 계산해야 하는지 모릅니다. 여러분이 원당이를 도와서 다음 손님들에게서 얼마를 받아야 하는지 알려 주세요. 고객등급 물건 정가 Silver 35000 Gold 74000 VIP 154000 문제 풀이 1%는 1/100 을 의미 합니다. 5%는 원래 금액에서 5/100 을 빼 준 금액이므로 원래 금액 - (원래금액 * 0.05) = 원래 금액 * 0.95 와 동일합니다. 따라서 다음과 같이 계산을 하면 됩니다. Silver 고객 :..

[알고리즘 수학] 장갑 짝 찾기

원당이는 장갑을 판매하고 있습니다. 그런데 이번 힌남노 태풍으로 피해를 입고 말았는데요~ 태풍이 지나간 후 장갑을 회수 했는데~ 다음과 같았습니다. 왼쪽 장갑 흰색 1014,파랑색 2022,검정색 2314 오른쪽 장갑 흰색 2486,파랑색 1011,검정색 4327 원당이가 회수한 장갑으로 짝을 맞춰서 다시 판매를 하려고 합니다. 원당이가 팔 수 있는 장갑은 색상별로 각각 몇켤레인가요? 문제풀이) 흰색 장갑이 왼쪽 1014,오른쪽 2486 이므로 1014 켤레를 짝을 맞춰 판매 할 수 있다. 파랑색 장갑이 왼쪽 2022,오른쪽 1011 이므로 1011 켤레를 짝을 맞춰 판매 할 수 있다. 검정색 장갑이 왼쪽 2314,오른쪽 4327 이므로 2314 켤레를 짝을 맟춰 판매 할 수 있다. 프로그램으로 이 문제..

[알고리즘 수학] 가짜동전과 진짜 동전 구별하기

가끔 이러한 뉴스를 확인 할 수 있는데요~ 오늘은 가짜동전 진짜 동전에 대한 퀴즈를 풀어 보도록 하겠습니다. 원당이 친구가 원당이에게 동전 100개씩 들어 있는 동전꾸러미 10개를 들고 와서는 원당이에게 다음과 같이 물어 보았습니다. "이 동전은 모양과 크기가 모두 같은데 한 꾸러미 안에 있는 동전은 가짜야~" "진짜 동전의 무게는 10g 이고 가짜의 무게는 9g 인데 이것을 한번에 판단하는 방법이 있을까?" 원당이에게는 동전의 무게를 정확하게 잴 수 있는 저울이 있습니다. 이 저울을 이용하여 한번에 진짜동전과 가짜 동전을 구별해 낼 수 있을 까요? 풀이 더보기 한번에 찾을 수 있습니다. 10개 꾸러미에 1 부터 10까지 번호를 먼저 매겨 놓습니다. 그리고 나서 1번 꾸러미에서 동전 1개,2번 꾸러미에서..

[알고리즘 수학]강건너기 문제

어떤 사람이 늑대 한마리, 염소 한마리, 양배추 한통을 가지고 강둑에 서 있다. 이 셋을 모두 배로 반대편으로 옮겨야 한다. 하지만 배에는 이 사람 외에는 하나만 실을 수 있다. 그 가 없으면 늑대는 염소를 먹어 버리고 염소는 양배추를 먹어 버린다. 여기서 퀴즈 늑대가 염소를 잡아먹지 못하고 또 염소가 양배추를 먹지 못하게 하면서 모두를 건너편 강가로 데려 갈 수 있을까? 힌트 사소한 예외 하나를 빼면 이 퀴즈는 각 상황에서 옮길 수 있는 유일한 것을 열거하는 방식을 풀 수 있다. 정답 더보기 풀이1) 1. 염소를 데리고 강을 건넌다.(염소/늑대,양배추) 2. 염소를 내려 놓고 다시 건너와서 늑대를 데리고 강을 건넌다. 3. 늑대를 내려 놓고 염소를 데리고 다시 건너온다.(늑대/염소,양배추) 4. 양배추..

[컴퓨팅사고력] DNA 조작 횟수를 최소로 만들어 보자

DNA의 염기서열은 adenine(A),thymine(T),guanine(G),cytosine(C) 와 같이 네가지로 구성되어 있습니다. DNA 염기서열을 연구하고 있는 원당이는 고릴라의 염기서열이 GATACCAGATACCCA 와 같이 이루어져 있고 원숭이의 염기서열이 AAGATTGCCATTATT 와 같이 이루어져 있는 것을 발견했습니다. 원당이는 고릴라와 원숭이의 염기서열을 똑같이 만들어 보고 싶습니다. 가령 GATA 의 염기서열을 AAGT 로 만든다면 GATA에서 3개를 변경해서 만들 수 있습니다. 혹은 AA 와 같이 만든다면 G와 T 두개의 염기서열을 삭제해서 만들 수 있습니다. 또는 GATAT 와 같은 경우는 T를 추가해서 염기서열을 만들 수가 있습니다. 이렇게 변경하거나 추가하거나 삭제하는 세가..

[컴퓨팅사고력] 지워진 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..