1장 알고리즘

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

정답이 아닐 확률이 높습니다 피드백 환영
틀릴 경우 계속 수정
참고용

 
 
 
 
1. 다음의 괄호 안에 알맞은 단어를 채워 넣어라.
 
(1) 주어진 순서에 따라 차례로 탐색하는 알고리즘을 ( 순차탐색) (이)라고 한다.
(2) 이진탐색은(정렬된) 항목들에 대해서 (중간)에 있는 항목을 비교하여 그 결과에 따라 (같으면) 탐색을 마치고, 다르면
작은 항복들이 있는 부분 또는 큰 항목들이 있는 부분을 같은 방식으로 탐색한다.
(3) 동전 거스름돈 문제에서는 (액면가가 큰) 동전을 항상 서택 한다. 이는(그리디) 알고리즘의 일종이다.
(4) 한붓그리기 문제를 해결하는 알고리즘의 핵심은 현재 점에서 다음으로 이동 가능한 점을 선택할 때에는 반드시 현재 점으로 돌아오는 (사이클)이 존재하여야 한다는 것이다.
(5) 가짜 동전 찾기에서 동전 더미를 (반)으로 분할하여 저울에 달고, 가짜 동전이 있는 더미를 계속해서 (반)으로 나누어 저울에 단다.
이는(분할정복) 알고리즘의 일종이다.
 
2. 다음에 주어진 숫자들을 순차적으로 검색하여 85와 35를 찾는데 각각 몇 번 을 비교해야 하는가?
 
답: 3번 6 7
 
풀이 : 순차적 검색은 차례로 하나씩 몇 개 있는지 세어 보는 것인데 85는 6번째 있고 35는 7번째있다.
 
3. 다음에 주어진 숫자들 중에서 가장  큰 수와 가장 작은 수를 동시에 찾으려면 최소 몇 번의 숫자 비교가 필요한가?
 
답: 3번 6
 
풀이: 
45와 66 비교 1번째 45 66 90 20 
66과 90 비교 2번째 45 66 90 20
90과 20 비교 90이 20보다 더크기 때문에 교환 3~4번째 45 66 20 90
20과 66 비교 66이 20보다 더크기 때문에 교환 5번째 45 20 66 90
20과 45 비교 45가 20보다 더크기 때문에 교환 6번째 20 45 66 90
정렬이 됐기 때문에 큰 수와 작은 수를 찾을 수 있다.
 
4. 다음과 같이 숫자들이 정렬되었을 때 이진탐색으로 10을 찾으려면 몇 번의 비교를 해야 10이 숫자들 중에 없는 것을 알 수 있나?
 
답: 2번 4
 
풀이:
15 20 25 30 40 55 65 80
중간 숫자를 40으로 //10이 더 작으니 왼쪽으로
15 20 25 30 
중간 숫자 25 // 25보다 10이 더 작으니 왼쪽으로
15 20 
중간 숫자 20 // 더 작으니 왼쪽으로
15 
10이 아니니 종료
총 4번
 
5. 다음과 같은 동전 시스템에 대해 19원을 거슬러 받으려 할 때 가장 작은 동전수는?
 
답: 4번 4
풀이:
8+8+2+1
 
6. 다음과 같은 동전 시스템에 대해 19원을 거슬러 받으려 할 때 가장 작은 동전 수는?
 
답:1번 2  
풀이:
10+10
(답이 16+1+1+1+1인 줄 알았지만 그리디는 최적의 수를 찾아내는 것이기 때문에 
2번이 맞음)

7.동전 64개 중에 약간 가벼운 가짜 동전 1개가 섞여 있을 때 양팔 저울로 몇번을 달아야 가짜 동전을 찾을까?
단 1.6절에서 설명한대로 문제풀이를 하시오.

답: 2번
1번째 저울 32 32
2번째 저울 16 16
3번째 저울  8 8
4번째 저울 4 4
5번째 저울 2 2
6번째 저울 1 1

8. 동전6개중 가짜 동전 1개가 섞여 있을 때 저울을 몇번 달아야 가짜 동전을 찾을까?(1.6x)

답: 1번2
1번째 저울2  저울2  나머지2
이렇게 두개씩 비교를 했을때 기울거나 기울지 않으면
2개씩만 비교하면 된다
2번째 저울1  1

9.동전 7개ㆍㆍ위에 문제 동일(1.6x)

답: 1번 2
1번째 저울3 저울3 나머지1
2번째 저울1  저울1 나머지1

 
10. 1.1절에서 설명된 최대 숫자 찾기 문제에 대한 알고리즘과 다른 알고리즘을 생각해 보자.
답:
1. 순차 탐색
2. 토너먼트 트리
3. 선택 알고리즘 
 
12. 보간탐색이 어떤 방식의 탐색인지를 조사해보자.
답:
이진 탐색은 정렬된 대상을 기반하여 중앙에 위치한 데이터를 탐색한 후, 이를 기준으로 탐색 기준을 반으로 줄여나가면서 탐색을 진행함.
이러한 방식은, 달라지는 탐색 대상에 관계없이 항상 중앙에 위치한 데이터를 기준으로 탐색을 시작한다.
이러한 방식에서 발생할 수 있는 비효율을 줄이기 위한 보완책으로 보간탐색이 등장하였다.
정렬된 데이터가 배열에 저장되어 있을 때, 선형 보간법 (linear interpolation)으로 탐색 space (배열내의 제일 작은 수에서 제일 큰 수의 집합) 내의 어느 부분쯤에 찾고자하는 숫자가 있을지를 예측하여 그 숫자와 비교한다. 그 결과에 따라서 같은 방법으로 계속 탐색한다.
 
13. 다음의 숫자들에 대해 35를 이진탐색으로 찾는 과정을 보이라.
답:
10,20,25,35,45,55,60,75,80,90,95
중간 숫자인 55를 기준으로 35는 더작기 때문에 왼쪽으로 이동
10 20 25 35 45 
25를 기준으로 35는 크기때문에 오른쪽으로 이동
35 45 
 
14. 1024개의 정렬된 데이터에 대해 이진 탐색을 하는 데 필요한 최대 비교 횟수를 구하여라
 
답:
 log2 1024=10번
 
풀이:
1024를 2씩 계속 나눠서 
0~0을 만들어주면됨 
ex: 0~1024
0~512 ...

 
15. 순차탐색,보간탐색, 이진탐색 중 데이터가 어떻게 주어질때 각각 가장 빨리 찾고,어떤 경우에 가장 늦게 찾는지 알아보자.
순차 탐색은 처음 부분부터 순차적으로 데이터를 비교하는것이다.
빠르게 찾는 방법은 없다 무조건 다비교해봐야 된다.
이진 탐색은 데이터가 정렬되어 있는 배열에서 찾고자 하는 값을 반으로 줄이면서 특정한 값의 위치를 찾는 알고리즘이다.
보간탐색은 예측하여 탐색하는 방법인데 가장 빠르게 찾는방법은 처음 값이 찾으려는 값일때이다.
 
24. 1.6절에서 1개의 가짜 동전을 n개의 동전 중으로 찾는데 로그2의 n번 만에 찾는 알고리즘이 설명 되었다.
만일 동전의 수가 홀수 개이거나 1/2로 나누다 보니 한쪽이 홀수 개 다른 한쪽이 짝수 개가 되는 경우를 처리하는 방안을 제시하라.

풀이: 동전n이 9개라고하면 2의k승
9개를 2분의 1로 나누면 4가 되고
2의4승이니까 16이된다.