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

[알고리즘 수학] 카드 맞히기 마술

어느 마술사가 한 관객에게 1부터 27까지 쓰여진 27장의 카드 중에서 한 장을 고른 후 그 카드를 마술사에게 보여주지 않은 채 다시 카드 무더기 안에 집어 넣으라고 시켰다. 마술사는 카드를 다시 섞은 다음 한 번에 한 장씩 앞면이 보이도록 세 무더기로 나누기 시작했다.(예 1~27 까지의 카드가 순서대로 있었다면 1,4,7...,25 / 2,5,8 ...,26/3,6,9 ...,27 와 같이 순서대로 하나씩 3 그룹으로 분리한다.) 그런 후 카드를 선택했던 관객에게 아까 골랐던 카드가 어느 무더기에 들어갔는지 물어본다. 관객이 고른 무더기를 다른 두 무더기 사이에 집어 넣은 다음 카드를 섞지 않은 채 아까처럼 세 무더기로 나눠 놓는다.(예를 들어 첫번째 그룹에 들어 있었다면 2,5,8,...26/1,4..

[알고리즘 수학] 막대자르기

길이가 100인 막대를 잘라 길이가 1인 조각 100개를 만들어야 한다. 여러 조각을 한꺼번에 자를 수 있다고 가정할 때 자르는 최소 횟수는 몇번인가? 막대의 길이가 n일때 최소 횟수만에 자르는 알고리즘을 설명하라. 문제출처) 길벗 - 알고리즘 퍼즐 문제풀이) 이 문제는 정보올림피아드 예선 문제에 자주 출제되는 유형으로 다음과 같이 절반씩 잘라 가는 유형으로 생각하면 됩니다. 100 = 50 * 2 50 = 25 * 2 25 = 13 + 12 (여기서 13 크기를 기준으로 생각함) 13 = 7 + 6 (여기서 7 크기를 기준으로 생각함) 7 = 4 + 3 (여기서 4 크기를 기준으로 생각함) 4 = 2*2 2 = 1*1 즉 7번이면 100인 막대를 1 크기로 모두 자를 수 있습니다. 여기서 아이디어는 절..

[알고리즘 수학] 살아있기 좋은 날

세계 과학의 역사라는 책을 준비 중인 편집자가 주요 과학자가 가장 많이 살아 있던 시기를 알아 보려고 한다. 여기서 주요 과학자는 그 책에 출생연도와 사망연도가 모두 기록된 과학자로 정의한다.(그 책에 살아 있는 과학자는 수록되어 있지 않다) 책의 색인을 입력 받아 이 작업을 처리해보자. 만약 A가 사망한 해에 B가 새로 태어났다면 A의 사망시점이 B의 출생 시점보다 앞선다고 가정하자. 문제 출처)길벗출판사- 알고리즘 퍼즐 문제풀이) 이 문제는 자료구조의 count배열을 사용하여 해결이 가능하다. 예를 들어 다음과 같이 (태어난 해,사망한해)의 형태로 데이터가 입력 되었다고 가정해 보자. A(1,9),B(4,7),C(2,10),D(7,11),E(3,12) 태어난 해에는 +1,사망한 해에는 -1로 표기를 ..

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

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 켤레를 짝을 맟춰 판매 할 수 있다. 프로그램으로 이 문제..