[TIL] 알고리즘 기초학습

오늘은 알고리즘 요리를 위한 재료와 양념에 대해 배우는 시간이었다.

오늘의 메뉴
재료: 스택, 큐
양념: 이진탐색, 재귀함수, 정렬(버블, 선택, 삽입, 병합)

---

Today I Learned

1. 이진탐색과 순차탐색

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)

이진탐색 문제 풀이를 위해서 개인적으로 ' len(array) // 2 '를 사용하여 코드를 작성했었는데,
답변 코드에서는 ' current_min, max '값을 활용하여 풀었다는 점이 인상깊었다.
++ 무작위로 정렬되어 있는 배열에서는 이진탐색을 활용할 수 없다는 점을 배웠다.

이진탐색이 항상 빠른 선택지가 아님을 배웠다.
상황에 맞게 '탐색법'과 '자료형'을 선택하여 사용해야한다.

2. 재귀함수

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


count_down(60)

카운트다운 함수를 구현하며 재귀함수를 처음으로 사용하며 Recursion 에러와도 첫 인사를 나누었다.

'카운트다운이니 당연히 0에서 멈추겠지?'라는 일반적인 생각과 다르게, 컴퓨터는 그런거 없다.
탈출조건을 만들어줘야한다. (if number <0: return)

Call by Object Reference(관련링크)에 대해 실습을 통해 배울 수 있었다.

• 함수에서 파라미터로 배열을 넘기면 그 내부에 원소를 추가하거나 할 수 있는데,
  int, str 타입의 변수를 넘기면 그 값이 복제되어 새로운 값을 생성한다.
  이런 경우, 함수 외부의 변수를 사용하기 위해 '글로벌 변수'를 사용함으로 해결할 수 있다.

3. 정렬

• 버블, 선택, 삽입 정렬의 경우 O(N^2) 시간복잡도가 걸린다.
  (물론 선택, 삽입정렬의 경우 break문을 활용하여 $Ω(N)$의 결과를 얻을 수 있다는 차이는 있다.)

• Divide and Conquer(분할 정복)과 재귀함수를 활용하여 병합 정렬 코드를 구현했다.

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = array[:mid]
    right_array = array[mid:]
    print(array)
    print('left_arary', left_array)
    print('right_arary', right_array)
    return merge(merge_sort(left_array), merge_sort(right_array))


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result

다른 정렬 방법들이 O(N^2) 시간복잡도를 가지는 것에 비해, 병합정렬은 O(NlogN) 시간복잡도를 가진다는 장점이 있다.

4. 스택

• 스택의 기능목록
  push(data) : 맨 앞에 데이터 넣기
  pop() : 맨 앞의 데이터 뽑기
  peek() : 맨 앞의 데이터 보기
  isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

• 스택 수열문제(백준 1874번)

  문제를 이해하는게 푸는 것보다 어려운 문제였다.

어딘가 '하노이의 탑(링크)'가 떠오르는 문제를 풀어보며 스택의 한계점..?을 체감할 수 있었다.
(물론 실제로 스택 하나만 가지고 저런 업무를 하는 일이 있겠냐마는..)

5. 큐

• 롤쟁이라 그런지, 늘 쓰던 말인 "큐 돌린다, 큐 잡혔다'가 생각났다.
  근데 실제로 FIFO 구조이기도 해서, 맞게 쓴 말인 것 같기도 하다.

• 큐의 기능목록
  enqueue(data) : 맨 뒤에 데이터 추가하기
  dequeue() : 맨 앞의 데이터 뽑기
  peek() : 맨 앞의 데이터 보기
  isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기

		def enqueue(self, value):              
        new_node = Node(value)             
				if self.is_empty():                # 만약 비어있다면,
            self.head = new_node           # head 에 new_node를
            self.tail = new_node           # tail 에 new_node를 넣어준다.
            return

        self.tail.next = new_node          
        self.tail = new_node		           

스택과 다르게 큐에서는 tail도 생각하고, 신경써줘야 한다.

		def dequeue(self):
        if self.is_empty():
            return "Queue is empty!"        # 만약 비어있다면 에러!

        delete_head = self.head             # 제거할 node 를 변수에 잡습니다.
        self.head = self.head.next          # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.

        return delete_head.data             # 그리고 제거할 node 반환

---