[TIL] #DAY - 016 - 자료구조, 알고리즘 (2) (내일배움캠프AI 3기)

Sparta Coding Club/Today I Learned [TIL]

[TIL] #DAY - 016 - 자료구조, 알고리즘 (2) (내일배움캠프AI 3기)

양한마리 2022. 9. 21. 20:34

728x90

다들 쟝고하는데 나는 알고리즘....

그냥 포기하고 쟝고 가야하나..?

뭔가 너무 자기주도학습이라서 갈피를 못잡겠네

그냥 하라는거 하는거같긴한데 제대로 하고있는거 맞나

뭔가 그냥 혼자 공부하는 기분인데

이해안가고 몰라야 누군가한테 물어볼텐데

그냥 대충은 다알겠어서 하긴하겠는데

모르겠다 이걸 이해했다고해야하나

아니겠지 모르는거겠지

부트캠프 단점인가(?)

[목차]

01. array와 Linked List

02. class

03. Linked List 구현 - 1

04. Linked List 구현 - 2

05. Linked List 문제

06. 이진 탐색

07. 재귀 함수 - 1

08. 재귀 함수 - 2

01. array와 Linked List

Arrays와 Lists의 공통점

아이템들의 컬렉션
아이템들의 순서 존재

Array와 Linked List의 차이점

Array
- 배열은 인덱스가 존재
- 데이터의 위치에 대해 직접적인 접근 가능
- 반드시 할당된 공간은 연속적 => 조회가 빠름, cache hit 가능성 ↑
- 미리 배열의 크기를 지정해야하고, 고정되어있는 배열의 크기때문에 데이터의 추가 및 삭제가 불편
Linked List
- 인덱스를 갖지만, 몇번째 데이터인지 정도를 의미
- 메모리 주소가 연속적이 아닐 수도 있음
- 포인터를 통해 다음 데이터의 위치를 가리키고 있어 삽입, 삭제가 쉬움
- 동적이므로, 배열과 다르게 크기가 정해져 있지 X
- 검색 성능이 좋지 않음, 직접적인 접근이 불가능하고, 처음부터 찾아야한다 => 확실하게 정해져 있는 데이터는 배열이 효율적

02. class

1) 클래스란?

클래스는 분류. 집합. 같은 속성과 기능을 가진 객체를 총칭하는 개념입니다.
객체는 세상에 존재하는 유일무이한 사물입니다.

예시)

클래스가 사람이라면, 객체는 유재석이 될수도 있고, 박명수가 될 수도 있습니다.
클래스가 동물이라면, 객체는 강아지가 될수도 있고, 고양이가 될 수도 있습니다.

class Person:
    def __init__(self, param_name):# 생성자로 클래스 생성시 호출되는 함수
        print("hihihi", self)
        self.name = param_name

    def talk(self): # 메소드
        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()  # 안녕하세요 저는 박명수 입니다

03. Linked List 구현 - 1

1) 링크드 리스트로 append 함수 만들기

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)


linked_list = LinkedList(5)
linked_list.append(12)
# 이렇게 되면 5 -> 12 형태로 노드를 연결한 겁니다!
linked_list.append(8)
# 이렇게 되면 5 -> 12 -> 8 형태로 노드를 연결한 겁니다!

2) 링크드 리스트로 모든 원소 출력

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


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.print_all()

자세한 내용은 추가로 공부하기로!

04. Linked List 구현 - 2

1) 링크드 리스트 원소 찾기

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를 들고 있는 노드를 반환해야 합니다!

2) 링크드 리스트 원소 추가

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

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

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


linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()

3) 링크드 리스트 원소 삭제

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

    def add_node(self, index, value):
        new_node = Node(value)
        if index == 0:
            new_node.next = self.head
            self.head = new_node
            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:
            self.head = self.head.next
            return
        node = self.get_node(index - 1)
        node.next = node.next.next



linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0, 3)
linked_list.print_all()

05. Linked List 문제

두 링크드 리스트의 합 계산

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 get_linked_list_sum(linked_list_1, linked_list_2):
    sum_1 = _get_linked_list_sum(linked_list_1)
    sum_2 = _get_linked_list_sum(linked_list_2)

    return sum_1 + sum_2


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


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))

06. 이진 탐색

이진 탐색 개념

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)

07. 재귀 함수 - 1

1) 재귀란?

재귀(Recursion)은 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다. [위키백과]

Q. 60에서 0까지 숫자를 출력하시오.

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

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


count_down(60)

08. 재귀 함수 - 2

1) 팩토리얼

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미합니다.
- 3! 은 3 * 2 * 1 = 6,
- 4! 는 4 * 3 * 2 * 1 = 4 * 3! = 24
즉, Factorial(n) = n * Factorial(n - 1) Factorial(n - 1) = (n - 1) * Factorial(n - 2) .... Factorial(1) = 1 의 구조입니다!

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

# 출력 : 120

2) 회문 검사

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])


print(is_palindrome(input))

728x90

'Sparta Coding Club > Today I Learned [TIL]' 카테고리의 다른 글

[TIL] #DAY - 018 - 파이썬 장고 실무 기초 (2) (내일배움캠프AI 3기) (1)	2022.09.24
[TIL] #DAY - 017 - 파이썬 장고 실무 기초 (1) (내일배움캠프AI 3기) (0)	2022.09.22
[TIL] #DAY - 015 - 자료구조, 알고리즘 (1) (내일배움캠프AI 3기) (1)	2022.09.20
[TIL] #DAY - 014 - 파이썬 기초 복습하기!(2) (내일배움캠프AI 3기) (1)	2022.09.20

현재글[TIL] #DAY - 016 - 자료구조, 알고리즘 (2) (내일배움캠프AI 3기)

250x250

Coding Farm

AI, 알고리즘, 머신러닝, 비전공자, 내일배움캠프AI3기, 부트캠프, 장고, Python, 개발일지, 코딩테스트, Wil, 문제풀이, 스파르타코딩클럽, django, 반복문, 백엔드, 개발자, 파이썬, 백준, Til,

Today :
Yesterday :

Coding Farm