TIL 8일차: 배열, 링크드리스트, 노드, 클래스, 원소 출력/찾기/추가/삭제, 이진탐색, 재귀함수

오늘은 자료구조, 알고리즘 2주차 강의를 들었다. 숙제는 문제가 3개나 되길래 내일 해야겠다고 다짐만 했다.

자기 전에 오늘 배운 내용을 간단히 살펴보자.

 

1. 배열 Array

배열이란 순차적으로 데이터를 저장하는 공간이다. 크기가 정해져있기 때문에 한 번 정해지면 바꿀 수 없다.

배열에서는 각 원소에 즉시 접근 가능하다. 즉, 상수시간 내에 접근할 수 있다. O(1)

배열에서 원소를 중간에 삽입하거나 삭제하려면 모든 원소를 다 옮겨야 한다는 문제가 있다.

배열의 모든 공간이 차있을 땐 새로운 공간을 할당해야 하므로 비효율적인 자료구조이다.

 

2. (링크드)리스트 Linked List

링크드리스트는 크기가 정해지지 않은 데이터 공간이다.

특정 원소에 접근하려면 연결 고리를 따라 탐색해야 한다. 즉 O(N)의 시간 복잡도를 갖는다.

리스트 안에는 노드(화물칸)와 포인터(연결고리)가 있다.

원소를 중간에 삽입하거나 삭제하려면 앞 뒤의 포인터만 변경하면 된다. 즉 O(1)의 시간 복잡도를 갖는다.

이를 표로 정리하면,

	배열 Array	링크드리스트 LinkedList
특정 원소 조회	O(1)	O(N)
중간에 삽입 삭제	O(N)	O(1)
데이터 추가	모든 공간이 다 차버렸다면 새로운 메모리 공간을 할당 받아야 한다.	맨 뒤의 노드만 동적으로 추가한다. bc of dynamic array (크기가 고정되지 않은 배열)

따라서 데이터 접근은 배열이, 데이터 삽입 삭제는 링크드리스트가 유리하다.

좋은 소식은, 내가 배우고 있는 파이썬에서 배열은 리스트와 배열 둘 다 쓸 수 있는 효율적인 구조라는 점이다.

 

3. 클래스, 객체, 메소드

클래스는 분류, 집합 같이 속성과 기능을 가진 객체를 말한다.

클래스로 객체들을 묶어서 정리할 수 있다.

class Person:

 person_1 = Person("")

 person_2 = Person("")

괄호 안은 생성자 Constructor로, 객체를 생성할 때 쓰는 함수이다.

 

메소드 Method는 클래스 내부의 함수로, 객체의 변수를 사용해서 구현한다.

class Person:
    def __init__(self, param_name):
				print("I'm created!", self)
        self.name = param_name


person_1 = Person("유재석")
print(person_1.name)

 

self.name을 변수로 만들어서 param_name을 내용으로 저장하겠다.

그럼 self에 name이 주입되고, 그 주입된 걸 보려면 print(person_1.name)

 

Person()이라는 Constructor를 통해 param_name이 클래스 내부의 self.name의 내용으로 저장되고,

그 self.name을 호출했기 때문에 유재석을 볼 수 있다.

 

4. 클래스

클래스 내부에 다른 함수 추가하기

class Person:
    def __init__(self, param_name):
        print("hihihi", self)
        self.name = param_name

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


person_1 = Person("유재석") 
print(person_1.name)  # 유재석
person_1.talk()  # 안녕하세요 저는 유재석 입니다

여기서 talk은 클래스 내부의 함수 = 메소드이다.

이처럼 클래스를 이용하면 유사한 행동/데이터를 쌓을 수 있는 구조를 만들 수 있다.

즉 클래스를 통해 다양한 객체를 쉽게 생성할 수 있다.

 

5. 링크드리스트의 노드

노드에는 1)칸에 있는 데이터 2)다음 칸이 무엇인지 가리키는 포인터 이 두 가지 데이터가 필요하다.

따라서 클래스를 사용한다.

class Node:
    def __init__(self, data):
        self.data = data # 오른쪽 data는 클래스 내부에 저장되는 값이고, 왼쪽 data는 변수이다.
        self.next = None # 포인터가 아무것도 가리키지 않는다.

node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]

# 연결하기
first_node = Node(5) # 현재는 next 가 없이 하나의 노드만 있습니다. [5]
second_node = Node(12) # [12] 를 들고 있는 노드를 만듭니다.
first_node.next = second_node # 그리고, [5]의 next 를 [12]로 지정합니다. [5] -> [12]

하지만 노드를 일일이 연결하기에는 힘이 든다. 따라서 클래스를 만든다.

이때 LinkedList는 self.head라는 head 노드만 갖는다.

그리곤 각 노드의 next를 조회해서 찾아낸다.

 

6. 링크드리스트 클래스 만들기

class LinkedList:
    def __init__(self, data):
        self.head = Node(data)  # head에 해당 data를 갖는 Node를 생성하여 넣어준다


linked_list = LinkedList(5)
print(linked_list.head.data) # 5 출력

 

7. append() 함수 만들기

append() 함수를 쓰면 뒤에 data가 노드로 생성되어 붙는다.

주의할 점은, 모든 노드의 뒤에다 새로운 data를 넣은 노드를 붙인다는 점에 착안하여

맨 뒤에 있는 노드까지 이동해야 한다는 점이다.

따라서 head 노드를 따라서 한 칸씩 이동하면서 맨 뒤로 가야 한다.

그리곤 head.next에 Node(new)를 넣는다.

 

이때 head를 변경시킬 순 없으니 cur이라는 변수를 이용한다.

cur에 self.head를 넣은 후 cur = cur.next로 대입한다.

cur이 맨 끝까지 이동한 것을 확인하는 방법은 while문을 써서 cur.next = None일때까지 반복하는 것이다.

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

    def append(self, data):     # LinkedList 가장 끝에 있는 노드에 새로운 노드를 연결합니다.
        cur = self.head         
        while cur.next is not None: # cur의 다음이 끝에 갈 때까지 이동합니다. 
            cur = cur.next          
        cur.next = Node(data)


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

주의해야 할 점으로는 언제나 예외 처리!

head가 비어있는 값일 땐

if self.head is None:

 self.head = Node(data)

 return

 

8. 링크드리스트 모든 원소 출력

    def print_all(self): # 새로운 함수를 생성한다
        cur = self.head
        while cur is not None:
            print(cur.data)
            cur = cur.next

 

9. 링크드 리스트 원소 찾기

핵심은 index번째 노드를 반환하는 것이다.

즉 head부터 시작해서 index만큼 이동해야 한다.

이를 세기 위해 count라는 변수를 지정해준다.

    def get_node(self, index):
        node = self.head #첫 노드를 node라는 이름으로 저장
        count = 0 #index만큼 옮긴 횟수를 세는 변수
        while count < index: #계속해서 움직여야 하니까
            node = node.next
            count += 1 #한번 이동할 때마다 카운트 세어주기
        return node #원하는 노드값 반환

 

10. 링크드리스트 새로운 원소값 추가하기

index번째에 새로운 원소값 추가하기

이 함수에는 1)몇번째인지 2)무슨 값을 넣을지 알아야 한다. 다라서 두 가지 데이터가 들어간다.

핵심은 index.next = new_node 이고

new_node.next = next_node 이라고 지정해 주는 것이다.

또한 클래스 내부에 있는 다른 함수를 호출할 때는 self.함수이름()으로 적어준다.

    def add_node(self, index, value):
        new_node = Node(value)
        
        #예외 처리: index = 0일때
        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

 

11. 링크드리스트 원소 삭제

    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

 

12. 이진탐색 Binary Search (비교: 순차 탐색 Sequential Search)

퀴즈를 풀면서 새로 알게된 점들

1) // 연산자를 사용해 소수점 이하의 수를 버리고 몫만 나타낼 수 있다.

2) guess와 target이 맞지 않았을 때 +- 1을 해줘야 한다는 점.

guess < target : current_min = current_guess + 1

guess > target : current_max = current_guess - 1

그리고선 while문 돌 때 current_guess = (min + max) // 2 로 치환해 줄 것.

 

3) 시간 복잡도 Time Complexity에서 순차탐색은 O(N), 이분탐색은 O(logN)이 걸리므로 이진탐색이 효율적이다.

4) 무작위 수의 배열은 정렬이 필요하다. 즉 일정한 규칙으로 정렬되어 있는 데이터만이 이진탐색이 가능하다.

 

13. 재귀함수 recursive functions

재귀함수는 자기 자신을 호출하는 함수로, 간결하고 효율성 있는 코드를 작성할 수 있다.

특정 구조가 반복되는 양상을 띌 때 재귀함수를 쓰면서 문제를 축소하며 푸는 접근이 필요하다.

재귀함수를 쓸 때 주의할 점은 빠져나가는 지점은 명확하게 해주어야 한다는 점이다.

 

문자열 슬라이싱하는 법을 배웠다. 문자열[시작인덱스:끝인덱스]

연습문제로 회문검사

input = "abcba"


def is_palindrome(string):
	# 예외처리: string의 길이가 1보다 작거나 같을 때 참값 리턴
    if len(string) <= 1:
        return True
        
    # 탈출조건: 앞뒤가 같지 않으면 거짓값 리턴
    if string[0] != string[-1]:
        return False
    # 문자열 슬라이싱: 재귀함수로 문제를 축소하며 접근
    return is_palindrome(string[1:-1])


print(is_palindrome(input))

 

숙제는 내일 하는 걸로.... 내일은 2주차를 한 번 더 코딩하면서 복습하고 내 것으로 익힌 다음에 숙제를 해야겠다.