[TIL] 2022-11-10(9day)

알고리즘(Algorithm -2)

---

👉 Array(어레이)

https://www.faceprep.in/data-structures/linked-list-vs-array/

- 배열은 크기가 정해진 데이터의 공간 (한 번 정해지면 바꿀 수 없다.)

- O(1) 내에 접근할 수 있다.

- 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다.

- 원소를 추가하기에는 비효율적인 자료구조

---

👉 Linked List(링크드 리스트)

https://www.faceprep.in/data-structures/linked-list-vs-array/

- 리스트는 크기가 정해지지 않은 데이터의 공간 (연결 고리/포인터로 이어주기만 하면, 늘어날 수 있다.)

- 리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 된다.

  (원소 삽입/삭제를 O(1)의 시간 복잡도 안에 할 수 있다.)

 

✍️ 링크드 리스트 구현

class LinkedList:
    def __init__(self, value):
        self.head = Node(value)		# head 에 시작하는 Node 를 연결.

    def append(self, value):		# LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결.
        cur = self.head         
        while cur.next is not None:		# cur의 다음이 끝에 갈 때까지 이동. 
            cur = cur.next          
        cur.next = Node(value)
        
    def print_all(self):		#링크드 리스트 모든 원소 출력 (cur 이 None 이 아닐때까지 반복)
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next
            
	def get_node(self, index):		#링크드 리스트 원소 찾기
        node = self.head	#1. head에 저장되어있는 노드를 node 라는 변수에 담고
        count = 0	#2. count 라는 인덱스를 저장하기 위한 변수를 저장
        while count < index:	#3. count 가 index 가 될 때까지 (1씩 더해주니까 작을때까지)
            node = node.next	#4. node의 next 값을 node 에 대입
            count += 1	#5. count 를 증가
        return node	#node 를 반환


	def add_node(self, index, value):	#링크드 리스트 원소 추가
        new_node = Node(value)
        if index == 0:	#0이 입력될 경우에 대비해 예외처리
            new_node.next = self.head	#1. 새로운 노드의 next 를 현재 가지고 있는 head 에 연결하고
            self.head = new_node	#2. 현재 가지고 있는 head 를 새로운 노드로 교체
            return

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

	def delete_node(self, index):
        if index == 0:	#	#0이 입력될 경우에 대비해 예외처리
            self.head = self.head.next	#1. 현재 head 의 다음 노드를 head 로 만들기
            return
        node = self.get_node(index - 1)
        node.next = node.next.next
		...


linked_list = LinkedList(5)
linked_list.append(12)		# 이렇게 되면 5 -> 12 형태로 노드를 연결!
linked_list.get_node(0) # -> 5를 들고 있는 노드를 반환
linked_list.add_node(0, 3)
linked_list.print_all()

 

---

👉 Class(클래스)

- 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념

class Person:
    def __init__(self, param_name):		#무조건 생성자 이름의 함수는 __init__
        print("hihihi", self)		#self 는 객체 자기 자신
        self.name = param_name

    def talk(self):		#메소드(method)
        print("안녕하세요 저는", self.name, "입니다")


person_1 = Person("조용연")		# hihihi <__main__.Person object at 0x1067e6d60> 이 출력!
print(person_1.name)		# 조용연
person_1.talk()		# 안녕하세요 저는 조용연 입니다

person_2 = Person("일라이")		# hihihi <__main__.Person object at 0x106851550> 이 출력!
print(person_2.name)		# 일라이
person_2.talk()		# 안녕하세요 저는 일라이 입니다.

---

👉 이진 탐색

- ex) UP & DOWN 게임

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		#target보다 작다면 더 큰 값을 뒤지기 위해 +1
        else:
            current_max = current_guess - 1		#target보다 크다면 더 작은 값을 뒤지기 위해 -1
        current_guess = (current_min + current_max) // 2

    return False


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

---

👉 재귀 함수

- 재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

- 간결하고 효율성 있는 코드를 작성할 수 있기

- 반드시 빠져나가는 지점을 명확하게 정해줘야 한다. (안하면 무한루프에 빠짐)

def count_down(number):
    if number < 0:         # 만약 숫자가 0보다 작다면, 빠져나가자!
        return

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


count_down(60)

 

✍️ 팩토리얼

 - 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미

def factorial(n):
    if n == 1:
        return 1		#n이 1일때 탈출(탈출 조건)
    return n * factorial(n - 1)


print(factorial(60))

 

✍️ 회문 검사

 - 회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미

input = "abcba"


def is_palindrome(string):
    if len(string) <= 1:
        return True
    if string[0] != string[-1]:	#회문이 아니므로 거짓(탈출 조건)
        return False
    return is_palindrome(string[1:-1])	#is_palindrome(문자열) → is_palindrome(문자열[1, -1]) 로 문제가 축소


print(is_palindrome(input))

 

---

🙋‍♂️ 소감 : 

알고리즘 너무 어렵다...;;

😈 아는 내용이라고 그냥 넘어가는건 금물! 😈