📚 LECTURE

▶ 순차탐색 & 이진 탐색

• 순차탐색 (sequential search)
  - 처음부터 1~100을 순차적으로 탐색
  - 예: [1, 2, 3, 4, 5, ..., 100]인 경우, 1부터 100까지 차례대로 탐색

• 이진탐색 (binary search)
  - 처음부터 1~100 중에서 반씩 후보를 줄이면서 탐색
  (데이터를 절반으로 잘라서 중앙이라면 값을 리턴하고, 아니면 앞뒤로 절반씩 탐색 범위를 좁힌다)
  - 단, 데이터가 미리 정렬되어 있어야 한다
    예) 데이터 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

  단계	최솟값	시도값	최댓값
  1단계	1	8	16
  2단계	9	12	16
  3단계	13	14	16

• 비교
  - 빅오 표기: 순차탐색 O(N) > 이진탐색 O(logN)
  - 속도: 순차탐색 > 이진탐색

  ∴ 이진탐색 사용 시, 시간복잡도 ↓
  

▶ 함수

• 재귀 함수
  - 자기 자신을 호출하는 함수
  재귀(recursion): 어떠한 것을 정의할 때 자기 자신을 참조하는 것
  - 재귀함수 사용 시, 꼭 끝나는 시점을 알려줘야 한다.
    (안 그러면 무한 반복)
  - 재귀함수 비유 설명인데 왜 웃기지;
  

• .sort()
  - 배열 정렬 함수
  - 이분탐색 사용 시 유용

📑 FEEDBACK

▶ TROUBLE SHOOTING 🎯

• 어제 3 5 5 로 출력되던 문제 해결됐다!
  팀원분이 도와주셔서 잘못된 부분을 찾았다.
  def append 내에 append를 두 번을 하고 있었다... 🤦‍
  self.head = Node(data)를 써놓고 아래에 왜 또 self.head.next = Node(data)를 넣은 걸까ㅠㅠ
  (그리고 몇 번을 읽어봤는데도 못 찾은 것도 소름)
  틀린 부분 주석 처리를 하니까 3 4 5 가 제대로 출력되었다.

# [3] -> [4]
# data, next

class Node:
    def __init__(self, data):
        self.data = data;
        self.next = None


node = Node(3)
first_node = Node(4)
node.next = first_node


# print(node.next.data)


class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def append(self, data):
        if self.head is None:  # self.head 값이 None인 경우,
            self.head = Node(data)  # self.head에 Node의 data를 담아 대입해주고,
            return  # 그리고 나서, 함수 중단

        # self.head.next = Node(data)
        cur = self.head  # cur의 위치를 head로 지정 = [3]
        while cur.next is not None:  # cur의 next가 Node가 아닐 때까지
            cur = cur.next  # cur.next를 이용하여 cur의 위치를 한 칸씩 이동
        cur.next = Node(data)  # 끝에 도달했을 때, cur.next에 Node의 데이터를 담아서 대입

    def print_all(self):
        if self.head is None:
            return

        cur = self.head  # cur에 self.head 저장
        while cur is not None:  # cur이 None이 아닐 때까지
            print(cur.data)
            cur = cur.next  # cut을 next로 한 칸씩 이동


# head -> -> -> -> -> -> -> ->
# [3] -> [4] -> [5] -> [6] -> [new] (이 자리가 None임)
# [3] = cur인 경우, [4] = cur.next / [4] = cur인 경우, [5] = cur.next이다.
# 끝의 자리인 None까지 가려면, while cur.next == None: 사용.

linked_list = LinkedList(3)
linked_list.append(4)
linked_list.append(5)
linked_list.print_all()

▼ TODAY'S MEMO

• 오늘따라 집중이 안 돼서 애 먹었다ㅠㅠ 확실히 몸이 둔해지는 게 느껴져서 운동의 필요성을 느끼는 중... (그리고 모르는 척하는 중)

• 내일 알바 가기 전 운동 좀 할까 생각했는데, 생각해보니 알바 내내 서서 하루 종일 말을 해야된다는 걸 깨닫고 깔끔하게 포기! 역시 운동은 한 주의 시작일부터 하는 거지! 월요일부터 하자 하하!

• 주말 목표:
  1. '혼자 공부하는 파이썬' 1/2 읽기
    (현재 진도 75/413 = 18%)
  2. 스파르타 알고리즘 인강 3주차 완강 (과연...)
  3. WIL 작성