221114_TIL

이진 탐색

• 숫자 내림하는 방법

  // 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있음. (하나만 하면 나누기임. /)

• 이진 탐색 방법

1. 최대값과 최소값을 비교해 시도값 출력 (최소값 + 최대값) / 2
2. 범위 내 (최소값 + 최대값) / 2 실행

• 조건
  - 이진탐색은 항상 일정한 규칙으로 정렬되어 있는 데이터일때만 가능하다.
  

# 이진 탐색
# 숫자 내림 하는 방법 ) // 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있음.

# 예시
print((4+5)/2) # 4.5
print((4+5) // 2) # 4

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):
    curr_min = 0
    curr_max = len(array)-1
    curr_guess = (curr_min + curr_max) // 2
    
    while curr_min <= curr_max:
        if array[curr_guess] == target:
            return True
        elif array[curr_guess] < target:
            curr_min = curr_guess + 1
        else:
            curr_max = curr_guess - 1
        curr_guess = (curr_min + curr_max) // 2
    return False


result = is_existing_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):
    for num in numbers:
        if num == target:
            return True    


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

재귀함수

• 자기 자신을 호출함으로써 코드를 계속 실행.
• 탈출 조건 명시 필수

  설정 안 해주면 RecursionError: maximum recursion depth exceeded 라는 에러를 자주 볼 것임.

• 재귀함수의 목적은 문제를 점점 좁혀가는 것이다.

# 재귀함수의 목적은 '문제를 점점 좁혀가는 것'

# Count Down

def count_down(number):
    if number < 0: 
        return number
    print(number) # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)

Factorial(!)

# 팩토리얼(!)

def factorial(n): # 5
    if n == 1: # 5 == 1 X
        return 1
    return n * factorial(n - 1) # RecursionError: maximum recursion depth exceeded << 해당 에러코드를 보면 탈출조건 명시해야함.
# 5 * (5 - 1)! >> 5 * 4! >> 5 * 4 * 3 * 2 * 1


print(factorial(5)) # 120

회문 검사 (Palindrome)

# 회문 검사 palindrome n. 회문

input = "소주만병만주소"


# def is_palindrome(string):
#     n = len(string) # 1. 문자열의 길이를 n이라고 저장
#     for i in range(n): # 2. for문으로 인덱스를 한 번 돌아가면서 조회한다. 즉, i는 0부터 n-1까지 반복될 것.
#         if string[i] != string[n - 1 - i]: # 인덱스이기 때문에 맨 마지막에 있는 것이 n -1 이다. 따라서, 맨 마지막 인덱스에서 -i를 다시 빼줌. i는 맨 첫번째 인덱스임. [0]
#             # 요약하자면 맨 뒤에 인덱스랑[n-1] 맨 앞 인덱스[i]를 빼줌
#             return False
#     return True

def is_palindrome(string):
    if len(string) <= 1: # 문자열의 길이가 1과 같거나 그 이하인가?
        return True
    if string[0] != string[-1]:
        return False
    
    return  is_palindrome(string[1:-1])


print(is_palindrome(input))

문자열 슬라이스

Q. 0번째 인덱스에서 뒤에서 n번째 인덱스까지 자르고 싶으면?
A. [0:-n] 마이너스를 붙히면 끝에서부터 얼마나 떨어진 문자열을 자를 것인지. 라는 의미임.

정렬

• 정의
  - 데이터를 순서대로 나열하는 방법을 의미한다.
  - 정렬의 특징
  1. 이진 탐색을 가능하게 하고,
  2. 데이터를 효율적으로 탐색할 수 있게 만들어준다.
     
     

정렬 종류

1. 버블 정렬

첫번째 자료와 두번째 자료를, 두번째 자료와 세번째 자료를, 세번째 자료와 네번째 자료를...

이런식으로 (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식.

• 작은 숫자, 큰 숫자 순서로 있으면 PASS.
• 큰 숫자, 작은 숫자 순서로 있으면 Change.

# 버블 정렬
input = [4, 6, 2, 9, 1]


def bubble_sort(array):
    n = len(array)
    for i in range(n - 1): # 네 번 돌면 되니까 하나 빼줌, 시간 복잡도 : n의 길이
        for j in range(n - i - 1): # n의 길이
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
    return
    

bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!
# 시간 복잡도 : n^2제곱의 시간 복잡도를 가짐.

2. 선택 정렬

각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 실행해야 한다.

# 삽입 정렬
input = [4, 6, 2, 9, 1]


def selection_sort(array):
    n = len(array)
    for i in range(n - 1): # i = 0
        min_index = i
        for j in range(n - i): # j = 0
            if array[i + j] < array[min_index]: # [ i + j ]가 현재 시도해보고 있는 인덱스
                print(i + j) # 0
        array[i], array[min_index] = array[min_index], array[i]
    return


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
# 시간 복잡도 : n^2제곱의 시간 복잡도를 가짐.

3. 삽입 정렬

1. 선택 정렬은 전체에서 '최소값'을 '선택'하는 것이었다면,
   삽입 정렬은 전체에서 하나씩 올바른 위치에 "삽입"하는 방식.
2. 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이다.

# 선택 정렬
input = [4, 6, 2, 9, 1]


def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break # break, continue는 비교문에서만 사용가능. 반복문에 사용하는 일 없게 혼동하지 말기.
            print(i - j)
    
    return

insertion_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!
# 시간 복잡도 : n^2제곱의 시간 복잡도를 가짐.
# * 삽입 정렬의 버블, 선택 정렬과 다른 차이 *
# ㄴ break문의 차이. 버블 정렬과 선택 정렬은 무조건 O(N^2)의 시간복잡도를 가지게 되어있지만, 선택 정렬은 더 이상 비교할 게 없다면 바로 break문으로 코드를 끝내버림.
# 따라서, 최선의 경우에는 O(N) 시간복잡도를 가질 수도 있다.

금일 느낀점
진도를 거의 못 나갔다. 코드 이해도 별로 안 되었다.
어제 쓰러진 것 때문인지 몸상태도 별로 좋지 않다. 일단 화요일까지 알고리즘 수업을 들어보고 이런 개념이 있다는 것 정도로만 알고있자.

나에게 지금 중요한건 자바스크립트의 자료구조 이해와 코드 구성 이해, 그리고 프로그래머스 코딩테스트 문제들을 많이 풀어보고, 학습하는 것이 중요할 것 같다.