[11.10] 내일배움캠프[Spring] TIL-9

[11.09] 내일배움캠프[Spring] TIL-8

1. 파이썬 알고리즘

• 문자열 뒤집기 최소 값 구하기
  👉 ex) input = "011110"
  👉 모든 것을 0으로 만들기 -> 1111을 한번 뒤집기
  👉 모든 것을 1로 만들기 -> 0을 1로 뒤집기 두번

• 튜터님의 코드( 혼자 구현 실패.. )

input = "011110"


def find_count_to_turn_out_to_all_zero_or_all_one(string):
 
        count_to_all_zero = 0
        count_to_all_one = 0

        if string[0] == '0':
            count_to_all_one += 1
        elif string[0] == '1':
            count_to_all_zero += 1

        for i in range(len(string) - 1):
            if string[i] != string[i + 1]:
                if string[i + 1] == '0':
                    count_to_all_one += 1
                if string[i + 1] == '1':
                    count_to_all_zero += 1

        return min(count_to_all_one, count_to_all_zero)

result = find_count_to_turn_out_to_all_zero_or_all_one(input)
print(result)

• Array, LinkedList , 순차탐색, 이진탐색

👉 Array : 순차적 구조
👉 LinkedList : 노드에 데이터와 다음 데이터가있는 포인터가 들어있음
👉 순차탐색 : 순차적으로 탐색
👉 이진탐색 : 반씩 쪼개서 탐색

• Array
  👉 새로운 원소를 추가하기 위해서는 새로운 공간을 할당해야 하기 때문에 매우 비효율적..
  👉 조회할 때는 index로 접근하기 때문에 효율적( ex. array[1] )

• LinkedList
  👉 크기가 정해지지 않은 데이터의 공간
  👉 리스트는 탐색시 연결고리를 따라 탐색해야함 -> 최악의 경우 전부 탐색해야함
  👉 원소 중간 삽입 삭제 하기 위해 앞 뒤 포인터를 변경하기만 하면 됨
  👉 파이썬의 []는 array + LinkedList

• Class

class Person:
    def __init__(self,  param_name): --> 생성자!!
        print("i am created",self)
        self.name = param_name -- > java와 달리 class 상단부에 멤버 변수를 선언하지 않아도 주입이 된다... 신기..!

    def talk(self):
        print(f"안녕하세요 제 이름은 {self.name}입니다.")

person1 = Person('유재석')
print(person1.talk())
person2 = Person('박명수')
print(person2.talk())

• LinkedList 구현하기
  👉 링크드리스트는 data와 다음 노드의 주소를 갖고 있어야 하므로 class타입이 좋겠다...!!
  👉 링크드리스트는 self.head에 시작하는 노드를 저장한다.
  👉 다음 노드를 보기 위해서는 각 노드의 next를 조회해서 찾아간다.

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


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

    def append(self, data):

        if self.head is None:
            self.head = Node(data)
            return

        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(data)

    def prin_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next


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

• LinkedList에서 특정 index 값 반환하기

• 내가 짠 코드

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


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

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

    def get_node(self, index):
        cur = self.head
        while index > 0:
            if index == 0:
                return cur
            cur = cur.next
            index-=1

        return cur.data
        
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(20)
print(linked_list.get_node(0)) # -> 5를 들고 있는 노드를 반환해야 합니다!

• 튜터님 코드

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


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

    def append(self, value):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(value)

    def print_all(self):
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

   def get_node(self, index):
        node = self.head
        count = 0
        while count < index:
            node = node.next
            count += 1
        return node

linked_list = LinkedList(5)
linked_list.append(12)
linked_list.get_node(0) # -> 5를 들고 있는 노드를 반환해야 합니다!

• 특정 index에 특정 값 추가하기

• 튜터님의 코드 ( 혼자 구현 실패... )

def add_node(self, index, value):

      if index == 0:
          new_node = Node(value)
          new_node.next = self.head
          self.head = new_node
          return

      new_node = Node(value)
      node = self.get_node(index-1)
      next_node = node.next
      node.next = new_node
      new_node.next = next_node



linked_list = LinkedList(5) # 0
linked_list.append(12) # 1
linked_list.append(20) # 2
# print(linked_list.get_node(0)) # -> 5를 들고 있는 노드를 반환해야 합니다!
linked_list.add_node(0, 7)
linked_list.print_all()

• 특정 index 노드삭제

• 내가 짠 코드

 def delete_node(self , index):

        if index ==0:
            self.head = self.head.next
            return
        node = self.get_node(index-1)
        node.next = node.next.next

• 두개의 LinkedList의 합 구하기

• 내가 짠 코드

def get_linked_list_sum(linked_list_1,linked_list_2):
    cur1 = linked_list_1.head
    cur2 = linked_list_2.head

    str1 =''
    str2 =''

    while cur1 is not None:
        str1+=str(cur1.data)
        cur1 = cur1.next

    while cur2 is not None:
        str2+=str(cur2.data)
        cur2 = cur2.next


    return int(str1)+int(str2)


linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)

linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2))

• 튜터님 코드 - 함수화 전

def get_linked_list_sum(linked_list_1,linked_list_2):

    sum_1 = 0
    head_1 = linked_list_1.head
    while head_1 is not None:
        sum_1 = sum_1 * 10 + head_1.data
        head_1 = head_1.next

    sum_2 = 0
    head_2 = linked_list_2.head
    while head_2 is not None:
        sum_2 = sum_2 * 10 + head_2.data
        head_2 = head_2.next

    return sum_1+sum_2

👉 튜터님 코드에서 어떤 로직이 반복된 것이 보인다! -> 함수화 하자!

• 튜터님 코드 - 함수화 후

def get_linked_list_sum(linked_list_1, linked_list_2):
    sum1 = _get_linked_list_sum(linked_list_1)
    sum2 = _get_linked_list_sum(linked_list_2)


    return sum1 + sum2


def _get_linked_list_sum(linked_list):
    sum = 0
    head = linked_list.head
    while head is not None:
        sum = sum * 10 + head.data
        head = head.next

    return sum

• 이진 검색(ex. 업 다운 게임)

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_max + current_min) //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_max + current_min)//2
    return False
    # return


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

👉 만약 이 예제를 순차 탐색했다 -> 최악(빅오) = O(N)
👉 이진 탐색 -> 빅오 = log N

• 이진 탐색의 잘못된 사용 경우

finding_numbers = [0, 3, 5, 6, 1, 2, 4] -> 
이 경우에는 정렬되지 않아서 이진탐색을 진행하지 못함..

2. 느낀점⭐

1) 개념은 알고 있다고 생각한 LinkedList가 구현 해보니 어렵다..
2) 조금 더 익숙해지고 연습하자!