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

[알고리즘 수학] 쪽번호 붙이기

1부터 시작해 순차적으로 쪽번호를 어떤 책에 매기고 있다. 쪽 번호를 붙이는데 숫자를 1581개 썼다면 그 책은 몇쪽짜리 책인가? (예 123 페이지 쪽 번호를 붙였다면 숫자를 1,2,3 세개를 사용한 것이다.) [문제출처] 길벗 - 알고리즘퍼즐 문제풀이) 1~9 까지는 9개의 숫자를 사용한다.(총 9개 - 남은 갯수 1572) 10~99까지는 2개씩 90개의 수이므로 180개를 사용한다.(총 189개 - 남은 갯수 1392) 100~999 까지는 3개씩 900개의 수이므로 2700개를 사용한다. 100 부터 1392개를 사용한 경우이므로 1392를 3으로 나누면 464개가 된다. 100부터 464번째이므로 563 쪽이 된다.(100부터 1번째 쪽수는 100이므로 464번째는 563쪽이다.) 이것을 c언..

[알고리즘 수학] 팬 케이크 만들기

팬 케이크를 한번에 두개만 구울 수 있는 팬으로 1이상 n개의 팬 케이크를 만들어야 한다. 모든 팬 케이크는 양쪽을 모두 구워야 하며 한쪽 면을 굽는데 1분이 걸리는데 한장을 굽든 2장을 굽든 시간은 똑같다. 최단 시간에 팬 케이크를 모두 굽는 알고리즘을 설계해 보자. 문제풀이) n=1 일때는 무조건 2분이 걸린다. n=2 일때도 역시 2분이 걸린다. n=3 일때는 1,2 를 앞면 구운 다음 1의 뒷면과 3의 앞면을 굽는다. 그 다음 2의 뒷면과 3의 뒷면을 굽는다. 따라서 3분이 걸린다. n=4 일때도 4분이 걸린다. n=5 일때 역시 n=2를 먼저 2분에 처리하고 나머지 3개를 같은 방법으로 3분에 굽기 때문에 결국은 n 분이 걸린다. 결국은 n이 1보다 큰 경우에는 모두 n분에 구울 수 있다. c언..

[알고리즘 수학] n일장이 함께 열리는 날짜는 언제일까요?

길동이가 사는 마을은 7일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 8일에 열립니다. 원당이가 사는 마을은 5일에 한번씩 장이 열립니다. 즉 1일에 장이 열렸다면 그 다음 장은 6일에 열립니다. 길동이가 사는 마을과 원당이가 사는 마을에서 오늘 장이 열렸습니다. 그렇다면 몇일 후에 길동이가 사는 마을과 원당이가 사는 마을에서 같은 날짜에 장이 열릴까요? 문제풀이) 이 문제는 5와 7의 최소 공배수를 찾는 문제입니다. 최소 공배수를 찾는 알고리즘은 a * b / 최대공약수(a,b) 입니다. 최대공약수를 찾는 알고리즘은 유클리드 호제법을 이용해서 a와 b의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다고 정의 할 수 있습니다. 따라서 최대공약수를 구하는 알고리즘을 C언..

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

원당이는 자신이 태어난 날짜 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를 추가해서 염기서열을 만들 수가 있습니다. 이렇게 변경하거나 추가하거나 삭제하는 세가..