알고리즘강의 03. 복습

이 글은 블로그주인장이 여태 공부했던 알고리즘 독학 및 강의들의 내용을 정리하는 포스팅입니다.

순차 탐색

• 리스트의 원소를 하나 하니씩 확인하는 연산

#순차 탐색의 시간복잡도
def is_existing_target_number_sequential(target, array):
    found_count=0 #연산 횟수
    for number in array:
        found_count+=1
        if target == number:
            print("연산 횟수: ",found_count)
            return True
    return False
#시간복잡도: O(N)
#만약 찾고 싶은 원소가 리스트의 끝쪽에 있으면  
#앞에서 부터 하나씩 확인하는 것은 비효율적임 

이진 탐색

• 추측값을 중심으로 반으로 잘라서 탐색

def is_exist_target_number_binary(target, numbers):
    find_count=0
    current_min=0
    current_max=len(finding_numbers)-1
    current_guess=(current_min+current_max)//2
    while current_min <= current_max: #1~N까지
        find_count+=1 #1번 탐색하면 반절이 줄어듬 즉 N/(2^find_count)
        if target == numbers[current_guess]:
            print("연산 횟수",find_count)
            return current_guess
        elif target > numbers[current_guess]:
            current_min=current_guess+1
        else:
            current_max=current_guess-1
        current_guess=(current_min+current_max)//2
        
    return False

# N/(2^find_count) ===> O(logN)

재귀함수

• 재귀란?

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

• 카운트다운

def count_down(number):
    if number <0: #재귀 종료 조건
        return
        
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출

count_down(60)

• 팩토리얼

def factorial(n):
    if n==1: #종료조건
        return 1
    return n*factorial(n-1)

print(factorial(5))

관련 문제
1. 무작위 수 찾기
Q. 다음과 같이 숫자로 이루에진 배열이 있을 때, 2가 존재한다면 참/불로 반환

[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):
    numbers.sort() #이진탐색을 위해 배열정렬
    current_min=0
    current_max=len(numbers)-1
    current_guess=(current_min+current_max)//2
    if current_guess==target:
        return True
    elif target > current_guess:
        current_min=current_guess+1
    else:
        current_max=current_guess-1
    current_guess=(current_max+current_min)//2
return False

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

2. 회문 검사
   Q.다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오

"abcba" # True

답안
맨 앞의 문자와 맨 뒤의 문자, 맨 앞에서 두번째 문자와 맨 뒤에서 두번째 문자 이런식으로 계속 확인하면 된다.

input = "abcb"

def is_palindrome(string):
    n=len(string)

    for i in range(n):
        if string[i]!=string[n-i-1]:
            return False
    return True

print(is_palindrome(input))

input = "abcb"
#재귀 이용

def is_palindrome(string):
    if len(string) <= 1:
        return True
    if string[0] != string[-1]:
        return False
    return is_palindrome(string[1:-1])

print(is_palindrome(input))

참고

• 알고보면 알기 쉬운 알기쉬운 알고리즘 -스파르타 코딩클럽
• 소스코드
  https://github.com/BOLTB0X/Sparta-Algorithm/tree/main/week_2