어서와! 자료구조와 알고리즘은 처음이지? | 6강, 7강, 8강

6강 알고리즘 복잡도(Complexity of Algorithms)

시간 복잡도(Time Complexity)

문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계

 

공간 복잡도(Space Complexity)

문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계

 

평균 시간 복잡도(Average Time Complexity)

임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균

 

최악 시간 복잡도(Worst-case Time Complexity)*

가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간

 

Big-O Notation

점근 표기법의 하나, 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현

 

1) 선형 시간 알고리즘 - O(n)

- 선형 탐색 알고리즘

 

2) 로그 시간 알고리즘 - O(logn)

- 이진 탐색 알고리즘

 

3) 이차 시간 알고리즘 - O(n2)

- 삽입 정렬의 Worst case

 

4) n로그 시간 알고리즘 - O(nlogn)

- 병합 정렬

 

7강 연결 리스트 (Linked Lists) - 1

추상적 자료구조

자료구조의 내부 구현은 숨겨두고 외부 구현(데이터, 연산)

 

기본적 연결 리스트

- Node 

1. Data: 문자열, 레코드, 또 다른 연결 리스트 등 다양한 구조로 이루어질 수 있음

2. Link (next)

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

class LinkedList:
	def __intit__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None

 

1. 특정 원소 참조 (k번째)

    def getAt(self, pos):
        if pos <= 0 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

 

	배열	연결 리스트
저장 공간	연속한 위치	임의의 위치
특정 원소 지칭	매우 간편	선형탐색과 유사
	O(1)	O(n)

 

2. 리스트 순회 

    def traverse(self):
        curr = self.head
        result = []
        while curr is not None:  
            result.append(curr.data)
            curr = curr.next
        return result

 

3. 길이 얻어내기

	def getLength(self):
    	return self.NodeCount

 

8강 연결 리스트 (Linked Lists) - 1

 

4. 원소 삽입

1. pos전 노드를 찾아 prev에 저장

2. newNode의 next를 pos로 설정

3. prev노드의 next를 newNode로 설정

4. NodeCount += 1

def insertAt(self, pos, newNode):
    # 성공, 실패에 따라 True/False를 리턴
	if pos < 1 or pos > self.newCount + 1:
    	return False
    
    # 1. 삽입하려는 위치가 리스트 맨 앞일 때
    ## prev 없음
    ## Head 조정 필요
    if pos == 1:
    	newNode.next = self.head
        self.head = newNode
    
    # 일반적인 경우
    # pos가 가리키는 위치에 (1<= pos <= nodeCount + 1)
    else:
    	if pos == self.nodeCount + 1:
        	prev = self.tail
        else:
        	prev = self.getAt(pos-1)

        # newNode를 삽입하고 
        newNode.next = prev.next
        prev.next = newNode
    
    # 2. 삽입하려는 위치가 리스트 맨 끝일 때
    ## Tail 조정 필요
    if pos == self.nodeCount + 1:
    	self.tail = newNode
    
    self.nodeCount += 1
    return True

5. 원소 삭제

1. prev, curr 설정

2. prev.next = curr.next

3. result = curr

4. nodeCount -= 1

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
        
        if pos == 1:
            curr = self.head
            self.head = curr.next
            if self.nodeCount == 1:  
                self.tail = None
        else:
            curr = self.getAt(pos)
            prev = self.getAt(pos-1)
            prev.next = curr.next
            
        result = curr.data
        
        if pos == self.nodeCount:
            if pos == 1:   
                self.tail = None
                self.head = None
            else:
                self.tail = prev 
                
        self.nodeCount -= 1
        return result

 

6. 두 리스트 합치기

연결 리스트 self의 뒤에 또 다른 연결 리스트인 L을 이어 붙임

def concat(self, L):
	self.tail.next = L.head
    if L.tail:
    	self.tail = L.tail
    self.nodeCount += L.nodeCount