[알기쉬운 알고리즘] 1장 연습문제

알기쉬운 알고리즘 1장 연습문제를 공부한 내용을 정리하였습니다. 틀린 점이나 피드백이 있으시다면 언제든지 답글로 달아주시면 감사하겠습니다.

 

1. 최대 숫자 찾기에 대한 알고리즘과 다른 알고리즘을 생각해보자.

- 순차 탐색

모든 숫자에 대해서 처음부터 끝까지 카드의 숫자를 하나씩 비교하면서 가장 큰 숫자를 찾는다.

 

- 정렬

모든 숫자를 오름차순, 내림차순으로 정렬해두면 한쪽 끝에 있는 숫자가 최소 혹은 최대일 것이다.

 

2. 여러 장의 숫자 카드 중에서 가장 큰 수와 가장 작은 수를 동시에 찾기 위한 알고리즘을 생각해보자.

- 순차 탐색

1번과 동일하게 처음부터 끝까지 숫자를 비교하며 가장 큰 수와 작은 수를 찾는다.

 

- 정렬

1번과 동일.

 

3. 보간탐색(Interpolation Search)이 어떤 방식의 탐색인지를 조사해보자.

보간탐색은 이진탐색을 개선한 탐색 알고리즘이다.(값들은 정렬이 되어 있다고 가정함.) 이진 탐색은 무조건 1/2씩 줄여가며 원하는 값을 탐색하지만, 보간 탐색은 인덱스와 값의 비율로 줄이는 범위를 결정한다. 

 

보간탐색의 과정

high와 low인덱스 사이의 있는 값 target을 찾기 위해서 좀 더 범위를 효율적으로 그리고 대략적으로 좁혀나간다. 

high - low : s - low = A(arr[high] - arr[low]) : Q(arr[s] - arr[low]) 라는 비례식을 통해서 s의 값을 구하게 된다. 이 s를 비례식을 통해 대략적으로 구해가면서 이진 탐색보다 더 빠르게 값을 구해갈 수 있다.

 

s = 

4. 다음의 숫자들에 대해 35를 이진탐색으로 찾는 과정을 보이라.

[10, 20, 25, 35, 45, 55, 60, 75, 80, 90, 95]

 

값의 갯수가 11개이므로 가장 가운데에 있는 값은 55라고 할 수 있다.

중간값인 55보다 35가 작으므로 더 큰 값들은 확인할 필요가 없다.

 

[10, 20, 25, 35, 45]

값의 갯수가 5개이므로 가장 가운데에 있는 값은 25이다.

중간값인 25보다 35가 더 크므로 작은 값들은 확인할 필요가 없다.

 

[35, 45]

값의 개수가 2개 이므로 가운데에 있는 값은 35이다.

현재 찾고자 하는 값이 35이므로 탐색을 종료한다.

 

5. 1024개의 정렬된 데이터에 대해 이진탐색을 하는 데 필요한 최대 비교 횟수를 구하라.

비교횟수의 경우 가장 크거나 혹은 가장 작은 값에 대해서 최대이다. 0번째 인덱스를 target으로 생각한다.

인덱스의 범위는 0 ~ 1023 이고, 짝수의 경우 가운데 값을 찾을때 버림을 택한다.

# 이진 탐색의 경우 중간값의 인덱스를 계산하고, 중간값의 값을 target과 비교한다. 

 

1회 : 0 ~ 1023, 인덱스의 가운데 값은 (0 + 1023) / 2 = 511.5 이다. 511번째 인덱스를 비교했을 때 target이 0번째에 있으므로 다음 범위는 0 ~ 510이다.

 

2회 : 0 ~ 510, 인덱스의 가운데 값은 (0 + 510) / 2 = 255 이다. 다음 범위는 0 ~ 254이다.

 

3회 : 0 ~ 254, 인덱스의 가운데 값은 (0 + 254) / 2 = 127 이다. 다음 범위는 0 ~ 126이다.

 

4회 : 0 ~ 126, 인덱스의 가운데 값은 (0 + 126) / 2 = 63 이다. 다음 범위는 0 ~ 62이다.

 

5회 : 0 ~ 62, 인덱스의 가운데 값은 (0 + 62) / 2 = 31 이다. 다음 범위는 0 ~ 30이다.

 

6회 : 0 ~ 30, 인덱스의 가운데 값은 (0 + 30) / 2 = 15 이다. 다음 범위는 0 ~ 14이다.

 

7회 : 0 ~ 14, 인덱스의 가운데 값은 (0 + 14) / 2 = 7 이다. 다음 범위는 0 ~ 6이다.

 

8회 : 0 ~ 6, 인덱스의 가운데 값은 (0 + 6) / 2 = 3 이다. 다음 범위는 0 ~ 2이다.

 

9회 : 0 ~ 2, 인덱스의 가운데 값은 (0 + 2) / 2 = 1 이다. 다음 범위는 0 ~ 0이다.

 

10회 : 0, 0번 인덱스를 확인하고 종료한다.

 

6. 순차탐색, 보간탐색, 이진탐색 중 데이터가 어떻게 주어질 때 각각 가장 빨리 찾고, 어떤 경우에 가장 늦게 찾는지를 알아보자.

순차 탐색

최적 : 우연히 가장 처음 탐색한 데이터가 원하는 데이터일 경우, 즉 원하는 데이터가 가장 처음 탐색하는 위치에 있도록 데이터가 주어질 경우.

최악 : 가장 마지막으로 탐색한 데이터가 원하는 데이터일 경우(모든 데이터를 확인한 경우)

 

이진 탐색

데이터가 정렬되어 있을 때,

최적 : 원하는 데이터가 데이터의 가장 가운데에 위치한 경우

최악 : 원하는 데이터가 가장 큰 값이거나, 가장 작은 값인 경우

 

보간 탐색

s가 target의 인덱스일 경우,

최적 : Q * (high - low) / A + low = s 일때 데이터를 한번에 찾게 된다.

최악 : 원하는 데이터가 가장 큰 값이거나, 가장 작은 값인 경우.

 

10. 1.4절에서 설명된 한붓그리기에 대한 알고리즘에서 현재 점까지 진행된 후의 그래프에서 사이클을 찾아야 한다. 주어진 그래프에서 사이클을 찾는 방법을 설명하라.

그래프에서 DFS 알고리즘을 통해 역행간선(Back_edge)를 탐색한다. 역행간선이 존재한다면 사이클이 존재한다.

 

+ 참고.

https://rain-bow.tistory.com/entry/%EC%98%A4%EC%9D%BC%EB%9F%AC-%EA%B2%BD%EB%A1%9C%EC%99%80-%ED%9A%8C%EB%A1%9CEulerian-trail-circuit

오일러 경로와 회로(Eulerian trail & circuit)

 

 

11. 1.4절에서 설명된 한붓그리기에 대한 알고리즘은 주어진 그래프에서 모든 길(선분) 돌아오기가 가능한지를 검사하는 알고리즘으로도 사용할 수 있다.  모든 길 돌아오기가 가능한지를 검사하는 또 다른 한붓그리기 알고리즘을 조사해보자.

모든 꼭지점이 짝수점이거나 단 두개의 꼭지점만 홀수점인 경우 한붓그리기가 가능하다.

 

12. 한붓그리기 문제를 모든 선분 대신 모든 점을 한 번만 방문하고 시작점으로 돌아오기 문제로 변형시킨다면, 이 새로운 문제는 해밀토니안 사이클(Hamiltonian Cycle)을 찾는 문제가 된다. 이 문제에 대한 알고리즘을 조사 해 보자.

해밀토니안 사이클은 모든 꼭지점을 단 한번만 지나는 회로를 의미하는데, 이 사이클을 찾기 위한 조건은 밝혀지지 않음. 시행착오에 의해서 찾아야 한다.

 

15. 1.6절에서 1개의 가짜 동전을 n개의 동전 중에서 찾는 데 log2n번만에 찾는 알고리즘이 설명되었다. 만일 동전의 수가 홀수 개이거나 1/2로 나누다보니 한쪽이 홀수 개 다른 한쪽이 짝수 개가 되는 경우를 처리하는 방안을 제시하라.

홀수개의 동전을 구분할 경우, 한 개의 동전을 따로 빼 놓고 1.6절의 알고리즘을 적용하면 된다.

이 경우 두 가지 경우가 있을 수 있는데, 

1) 따로 뺀 동전이 가짜 동전일 경우 :

이 경우 나머지 동전을 반으로 나누고 저울에 올려두었을 때 무게에서의 차이가 없다.

 

2) 따로 뺸 동전이 가짜 동전이 아닐 경우 :

이 경우 나머지 동전에 가짜 동전이 있기 때문에, 저울에서 무게의 차이를 확인할 수 있다. 따라서 그대로 1.6절의 과정을 통해 가짜 동전을 파악할 수 있다.

 

16. 1.6절에서 가짜 동전을 찾는 알고리즘이 설명되었다. 이보다 더 빨리 찾는 방법을 찾아보라.[힌트 : 분할되는 더미의 수를 다르게 하여 찾아보라]

 

 

17. 독이 든 술단지 문제에서 단지의 수가 3일 때, 1.7절에서 설명된 알고리즘을 수행한다면, 몇 명의 신하가 필요한가? 또, 단지의 수가 각각 5, 6, 7일 때에는 몇 명의 신하가 필요한가?

단지의 수가 3일 때) 술통의 번호를 00 01 10으로 부여하면, 2명의 신하로 1.7절 알고리즘을 수행할 수 있다.

 

단지의 수가 5일 때) 술통의 번호를 000 001 010 011 100로 부여하고, 3명의 신하로 1.7절 알고리즘을 수행할 수 있다.

단지의 수가 6일 때) 000 001 010 011 100 101, 3명

단지의 수가 7일 때) 000 001 010 011 100 101 110, 3명