1장 연습문제 알기 쉬운 알고리즘 step-by-step으로 알고리즘 완전이해

소개글

알기쉬운 알고리즘 1번부터 15번까지의 풀이입니다.

목차

1. 다음의 괄호 안에 알맞은 단어를 채워 넣어라.
2. 다음에 주어진 숫자들을 순차적으로 검색하여 85와 35를 찾는데 각각 몇 번 을 비교해야 하는가?
3. 다음에 주어진 숫자들 중에서 가장 큰 수와 가장 작은 수를 동시에 찾으려면 최소 몇 번의 숫자 비교가 필요한가?
4. 다음과 같이 숫자들이 정렬되었을 때 이진탐색으로 10을 찾으려면 몇 번의 비교를 해야 10이 숫자들 중에 없는 것을 알 수 있나?
5. 다음과 같은 동전 시스템에 대해 19원을 거슬러 받으려 할 때 가장 작은 동전수는?
6. 다음과 같은 동전 시스템에 대해 19원을 거슬러 받으려 할 때 가장 작은 동전 수는?
7.동전 64개 중에 약간 가벼운 가짜 동전 1개가 섞여 있을 때 양팔 저울로 몇번을 달아야 가짜 동전을 찾을까?
8. 동전6개중 가짜 동전 1개가 섞여 있을 때 저울을 몇번 달아야 가짜 동전을 찾을까?(1.6x)
9.동전 7개ㆍㆍ위에 문제 동일(1.6x)
10. 1.1절에서 설명된 최대 숫자 찾기 문제에 대한 알고리즘과 다른 알고리즘을 생각해 보자.
12. 보간탐색이 어떤 방식의 탐색인지를 조사해보자.
13. 다음의 숫자들에 대해 35를 이진탐색으로 찾는 과정을 보이라.
14. 1024개의 정렬된 데이터에 대해 이진 탐색을 하는 데 필요한 최대 비교 횟수를 구하여라
15. 순차탐색,보간탐색, 이진탐색 중 데이터가 어떻게 주어질때 각각 가장 빨리 찾고,어떤 경우에 가장 늦게 찾는지 알아보자.
24. 1.6절에서 1개의 가짜 동전을 n개의 동전 중으로 찾는데 로그2의 n번 만에 찾는 알고리즘이 설명 되었다.만일 동전의 수가 홀수 개이거나 1/2로 나누다 보니 한쪽이 홀수 개 다른 한쪽이 짝수 개가 되는 경우를 처리하는 방안을 제시하라.

본문내용

1. 다음의 괄호 안에 알맞은 단어를 채워 넣어라.(1) 주어진 순서에 따라 차례로 탐색하는 알고리즘을 ( 순차탐색) (이)라고 한다.(2) 이진탐색은(정렬된) 항목들에 대해서 (중간)에 있는 항목을 비교하여 그 결과에 따라 (같으면) 탐색을 마치고, 다르면작은 항복들이 있는 부분 또는 큰 항목들이 있는 부분을 같은 방식으로 탐색한다.(3) 동전 거스름돈 문제에서는 (액면가가 큰) 동전을 항상 서택 한다. 이는(그리디) 알고리즘의 일종이다.(4) 한붓그리기 문제를 해결하는 알고리즘의 핵심은 현재 점에서 다음으로 이동 가능한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 (사이클)이 존재하여야 한다는 것이다.(5) 가짜 동전 찾기에서 동전 더미를 (반)으로 분할하여 저울에 달고, 가짜 동전이 있는 더미를 계속해서 (반)으로 나누어 저울에 단다.이는(분할정복) 알고리즘의 일종이다. 2. 다음에 주어진 숫자들을 순차적으로 검색하여 85와 35를 찾는데 각각 몇 번 을 비교해야 하는가?

참고 자료

참고 사진: 메인 페이지에 있는 사진http://www.yes24.com/Product/Goods/101875856