[TIL Day1] 어서와! 자료구조와 알고리즘은 처음이지? (1)

'K-Digital Training: 프로그래머스 인공지능 데브코스 2기' 첫 날.
그리고 배움기록 첫 날.
velog도 slack도 모든 것이 서툴고 어색하지만, 언제나 그랬듯 이또한 익숙해질 것이라 믿는다 :>

[1주차-Day1] 어서와! 자료구조와 알고리즘은 처음이지? (1)

선형 배열(Linear Arrays)

python에는 서로 다른 종류의 데이터도 줄세울 수 있는 list 자료형이 있다.

1. 리스트 연산

• 리스트의 길이와 무관하게 상수 시간 O(1)에 실행할 수 있는 연산
  - .append(원소)
  - .pop()
  
• 리스트 길이에 비례해서 선형 시간 O(N)에 실행되는 연산들
  - .insert(인덱스, 원소)
  - .del(인덱스)
  
• 추가 다른 연산
  - .index(원소) : 가장 왼쪽에서 찾은 인덱스를 반환하므로 중복되는 원소가 있는 경우에 해당 원소의 모든 위치를 찾으려면 별도의 구현(슬라이싱 등)이 필요

2. 정렬과 탐색

• 정렬(sort)
  - sorted() : 내장 함수로, 정렬된 새로운 리스트 반환
  - sort() : 리스트의 메서드로, 해당 리스트가 정렬됨
  
• 탐색(search)
  - 선형 탐색 : 순차적으로 모든 원소 탐색, 배열의 길이에 비례하는 실행 시간 O(N)
  - 이진 탐색 : 배열이 이미 정렬되어 있는 경우만 사용 가능하며, 절반씩 탐색 범위를 줄여나가는 방법 O(logN)
  

재귀 알고리즘(Recursive Algorithms)

같은 알고리즘을 반복적으로 적용하여 주어진 문제를 같은 종류의 보다 쉬운 문제의 답을 이용해 풀 수 있다. 재귀 호출의 종결 조건(trivial case)을 꼭 명시해야 한다.

• 재귀 알고리즘의 효율성 측면
  - 재귀 알고리즘으로 풀 수 있는 문제는 순환문을 이용한 반복적(iterative) 알고리즘으로도 풀 수 있음
  - 일반적으로 반복적 알고리즘이 재귀 알고리즘보다 문제 풀이의 시간적 효율이 높음

• 재귀적 방법으로 조합의 수 계산하기
  - 특정 원소 입장에서 볼 때, 이 원소를 포함하는 경우의 수와 그렇지 않은 경우의 수를 따로 계산해서 더함

def combi(n, m):
	if n == m:
    		return 1
	elif m == 0:
    		return 1
	else:
    		return combi(n - 1, m) + combi(n - 1, m - 1)

알고리즘의 시간 복잡도(Time Complexity)

알고리즘을 실행함에 있어 문제의 크기가 커짐에 따라서 얼마나 긴 시간을 요구하느냐를 뜻한다.

• 선형 시간 알고리즘 O(N)
  - 선형 탐색
• 로그 시간 알고리즘 O(logN)
  - 이진 탐색
• 이차 시간 알고리즘 O(N^2)
  - 삽입 정렬
  - 정렬 알고리즘 중 가장 낮은 시간 복잡도는 O(NlogN) (병합 정렬)

연결 리스트(Linked List)

"각 원소들을 줄줄이 엮어서" 관리하는 방식으로, 원소의 삽입/삭제를 빠른 시간 내에 처리할 수 있다.

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

• 노드 클래스, 연결 리스트 클래스

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

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

• pos번째 원소 찾기

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

• 연결 리스트 순회

def traverse(self):
        answer = []
        curr = self.head
        while curr:
            answer.append(curr.data)
            curr = curr.next
        return answer

• 원소의 삽입

def insertAt(self, pos, newNode):
	if pos < 1 or pos > self.nodeCount + 1:
    		return False
	# 맨 앞에 삽입하는 경우
    	if pos == 1:
    		newNode.next = self.head
            	self.head = newNode
	else:
    		# 맨 뒤에 삽입하는 경우
            	if pos == self.nodeCount + 1:
    			prev = self.tail
		# 중간에 삽입하는 경우
        	else:
        		prev = self.getAt(pos - 1)
		newNode.next = prev.next
        	prev.next = newNode             
	if pos == self.nodeCount + 1:
    		self.tail = newNode
        
        self.nodeCount += 1
	return True       

• 원소의 삭제

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

• 두 연결 리스트 합치기

def concat(self, L):
	self.tail.next = L.head
    	# L이 빈 리스트인지 체크
        if L.tail:
    		self.tail = L.tail
	self.nodeCount += L.nodeCount            

• dummy head가 있는 연결 리스트

class Node:

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


class LinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

• 양방향 연결 리스트

class Node:

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


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

스택(Stacks)

후입선출(LIFO: last-in-first-out) 자료 구조, 마지막에 넣은 것이 가장 먼저 꺼내어지는 위에 입구가 하나있는 박스를 생각하면 쉽다.

• 스택에서 발생하는 오류
  - 비어 있는 스택에서 원소를 꺼내려 할 때: stack underflow
  - 꽉 찬 스택에 원소를 넣으려 할 때: stack overflow
  
• 배열로 구현한 스택

class ArrayStack:
	def size(self):
    		return len(self.data)
        
	def isEmpty(self):
    		return self.size == 0
            
	def push(self, item):
    		self.data.append(item)
            
	def pop(self):
    		return self.data.pop()
            
	def peek(self):
    		return self.data[-1]

• 양방향 연결 리스트로 구현한 스택

class LinkedListStack:
	def __init__(self):
    		self.data = DoublyLinkedList()
	
    	def size(self):
    		return self.data.getLength()
	
    	def isEmpty(self):
    		return self.size() == 0
	
    	def push(self, item):
    		node = Node(item)
            	self.data.insertAt(self.size() + 1, node)
    
    	def pop(self):
    		return self.data.popAt(self.size())
	
    	def peek(self):
    		return self.data.getAt(self.size()).data

공부를 마치며
생각보다 학습량이 꽤 많다. 밀리지 않고 들어야 나중에 고생을 안하겠구나...😂