알고리즘 2주차 - 이진탐색, 재귀

이진탐색과 재귀함수

이진탐색은 반을 쪼개고 탐색하는 방식

순차탐색은 하나하나 탐색하는 방식

이진탐색을 항상 사용할 수 있는 것은 아니므로 어떨 때 사용 가능한지 배워야함

이진탐색 vs 순차탐색

이진탐색: 1~100 숫자 맞추기 놀이를 한다고 했을 때 "범위의 절반인 50"을 시도하는 방식.

50을 말한다.

대답이 up이라면 1~49는 후보에서 없어진다.

대답이 down이라면 51~100은 후보에서 없어진다.

............

# 예제 코드. 14를 찾는 코드
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2
    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

순차탐색: 위 게임과 동일할 시 1~100을 순차적으로 시도하는 방식

1을 말한다

2를 말한다.

.............

# 예제 코드. 14를 찾는 코드
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_sequential(target, array):
    for number in array:
        if target == number:
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

비교

이진탐색: 3번 째에 찾음 → O(log n)

순차탐색: 14번 째에 찾음 → O(N)

이진탐색:

총 숫자가 1~N 까지라고 한다면, 1번 탐색하면 반절이 줄어드니 N/2 개가 남습니다. 2번 탐색하면 반절이 줄어드니 N/4 = N/2^2 개가 남습니다. 3번 탐색하면 반절이 줄어드니 N/8 = N/2^3 개가 남습니다. .... k번 탐색하면 반절이 줄어드니 N/2^k 개가 남습니다. 이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다. 이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = \log_2{N} 횟수를 시도하면 정답을 찾을 수 있습니다!

무작위 수 찾기

❓

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 2이 존재한다면 True 존재하지 않는다면 False 를 반환하시오.

[0, 3, 5, 6, 1, 2, 4]

# 코드 스니펫
finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]

def is_exist_target_number_binary(target, numbers):
    # 이 부분을 채워보세요!
    return 1

result = is_exist_target_number_binary(finding_target, finding_numbers)
print(result)

finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]

def is_exist_target_number_binary(target, numbers):
    numbers.sort() # [0, 1, 2, 3, 4, 5, 6]
    current_min = 0
    current_max = len(numbers) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if numbers[current_guess] == target:
            return True
        elif numbers[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2
    return False

result = is_exist_target_number_binary(finding_target, finding_numbers)
print(result)

이진탐색을 하려면 순차적으로 오름차순으로 정렬되어 있어야 함

재귀 함수

재귀란? 어떠한 것을 정의할 때 자기 자신을 참조하는 것

재귀 함수란 바로 자기 자신을 호출하는 함수

👨‍🏫

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

그렇다면 재귀 함수를 왜 사용할까?
- 간결하고 효율성 있는 코드를 자기 반복을 함으로써 작성 가능
- 예) 카운트 다운 - 60부터 0까지 사람들이 숫자를 외친다면 어떻게 재귀를 이용할까?
```
def count_down(number):
    print(number)          # number를 출력하고
    if number == 0: # number가 0일 때는 스톱, 이것이 없으면 RecursionError 남(무한루프)
        return
    else:
        count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)
```
- 재귀 함수를 쓰기 전에는 탈출 조건 을 미리 생각하자!
- 재귀 함수는 자기 자신을 호출함으로써 코드를 간결하고 명확하게 할 수 있음
재귀 - 팩토리얼
- 팩토리얼: 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미
  - 3! = 3*2*1 = 6
  - Factorial(n) = n * Factorial(n-1)
```
# 코드
def factorial(n):
    # 이 부분을 채워보세요!
    if n == 1:
        return 1
    return n * factorial(n-1)


print(factorial(5))
```
- 회문 문제: 회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미
  - 토마토, 아시아, 오디오 등
  - is_palindrome("토마토") = True
  소주만병만주소가 회문인지 알기 위해서는, 아래와 같은 검사들이 필요합니다. ↓ ↓ 소주만병만주소 첫 번째 글자와 맨 뒤에서 첫번째 글자가 같아야 합니다. ↓ ↓ 소주만병만주소 두 번째 글자와 맨 뒤에서 두번째 글자가 같아야 합니다. ↓ ↓ 소주만병만주소 세 번째 글자와 맨 뒤에서 세번째 글자가 같아야 합니다. ↓ 소주만병만주소 마지막 남은 가운데 글자는 뭐가 오든 상관 없습니다!
```
# 일반적인 방법
input = "abcba"


def is_palindrome(string):
    n = len(string)
    for i in range(n):
        if string[i] != string[n-1-i]: #인덱스기 때문에 -1 해주는 것
            return False
    return True


print(is_palindrome(input))
```
```
# 재귀를 이용한 방법
input = "소주만병만주소"

# is_palindrom(string) -> 조건에 맞다면 -> is_palindrom(string[1:-1]
def is_palindrome(string):
    if string[0] != string[-1]:
        return False
    if len(string) <= 1:
        return True
    return is_palindrome(string[1:-1])


print(is_palindrome(input))
```
- 글자가 1개만 남는다면 회문이라고 치는 것임!

알고리즘 3주차 - 개요, 정렬(버블, 선택, 삽입) (0)	2021.01.25
알고리즘 2주차 - 숙제 (0)	2021.01.19
알고리즘 2주차 - 링크드리스트 (0)	2021.01.14
알고리즘 1주차 - 숙제 (0)	2021.01.13
알고리즘 1주차 - 점근표기법, 연습문제 (0)	2021.01.12

우기의 알