알고리즘 강의 2일차: 시간 복잡도, 배열, 링크드리스트(Class, append, get_node, add_node)

오늘 알고리즘 특강에서는 시간복잡도와 배열, 링크드리스트에 대해 배우고,

링크드리스트의 클래스, 데이터 추가, 원소 찾기, 원소 추가 실습을 해보았다.

 

1. 시간 복잡도

시간복잡도는 문제를 해결하는 데 걸리는 시간과 입력의 함수 관게로, 최악의 경우를 기준으로 O()값을 계산한다.

아래 함수들의 시간 복잡도를 비교해보자

#사례1
input = [3, 5, 6, 1, 2, 4]


def find_max_num(array):
    for num in array: #배열의 길이만큼 연산이 실행된다.배열의 원소갯수 = N
        for compare_num in array: #배열의 길이만큼 연산이 실행된다.N
            if num < compare_num: #비교 연산이 1번 실행된다
                break
        else:
            return num
# 총 N*N*1 = N^2의 시간복잡도를 갖는다 -> O(N^2)

#사례2
def find_max_num(array):
    max_num = array[0] #연산이 1번 실행된다  
    for num in array:  #배열의 길이만큼 연산이 실행된다. N    
        if num > max_num:  #비교 연산이 1번 실행된다
            max_num = num #대입 연산이 1번 실행된다
    return max_num
# 총 1+N*(1+1) = 2N+1의 시간복잡도를 갖는다 -> O(N)

 

2. 배열

배열은 연관된 데이터를 하나의 변수에 묶어서 관리한다.

O(1)의 조회시간을 가진다는 장점이 있다. 인덱스 값을 받으면 해당하는 배열의 값을 바로 리턴하기 때문이다.

하지만 원소 삭제 및 삽입은 O(N)이므로 비효율적이다. 정렬이 되어있는 배열이면 O(logN)이다.

배열의 단점을 보완해서 쓰는 것이 바로 링크드리스트다.

 

3. 링크드리스트

링크드리스트는 유동적으로 연결고리를 떼었다가 붙였다가 할 수 있는 자료구조이다.

노드와 포인터로 구성되어 있다. 원소의 삽입 및 삭제가 편리하다.

 

1)노드를 클래스로 정의하기 (data(노드 값)과 next(포인터) 정의)

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

2)링크드리스트 자료구조를 클래스로 정의하기 (head 정의)

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

3)링크드리스트 끝에 새로운 노드를 추가하는 append 함수 작성해보기

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

4)원하는 위치의 노드를 찾아내는 get_node 함수 작성해보기

    def get(self, index):
        #예외처리: index가 링크드리스트 길이보다 클 땐 거짓값 리턴
        #cur = self.head
        #if cur.next is None:
        #    last_node = cur.next

        #if index > last_node:
        #    return False

        count = 0 # head부터 시작해서 index만큼 이동하는 숫자 세는 변수
        node = self.head # head를 노드로 저장

        while count < index: # count가 index보다 작을 땐 계속 뒤로 움직인다, 같아 질 때 반복문 빠져나온다
            node = node.next
            count += 1
        return node

얘는 예외처리 하는 법을 몰라서 일단 패스...

 

5) 원하는 위치에 새로운 노드를 추가하는 add_node 함수 작성해보기 (get_node 함수 사용)

    def add(self, index, data): # 몇 번째인지, 무슨 값을 넣었는지 알기
        new_node = Node(data) #추가하는 노드를 new_node라는 이름으로 저장

        # 예외처리
        if index == 0:
            new_node.next = self.head #head에 추가하기 전에 이전 head를 next로 임시저장한다
            self.head = new_node #head에 추가한다
        return

        node = self.get(index - 1) #추가하려는 index 앞에서 고려해야 함
        next.node = node.next #원래 index번째 있었던 것은 next.node라는 이름으로 임시저장
        node.next = new_node #새로 추가되는 노드를 node의 다음으로 위치함
        new_node.next = next_node #임시저장한 것을 새로 추가되는 노드 뒤에 위치함