알고리즘 / 기술면접 스터디 공부 - 자료구조 이론(2)

1. 알고리즘 복잡도 표현 방법

(1) 알고리즘 복잡도 계산이 필요한 이유 

: 하나의 문제를 푸는 알고리즘은 다양할 수 있음.

따라서, 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산함

 

(2) 알고리즘 복잡도 계산 항목

- 시간복잡도 : 알고리즘 실행 속도 (시간복잡도의 주요 요소는 반복문이 지배함)

- 공간복잡도 : 알고리즘이 사용하는 메모리 사이즈

가장 중요한 시간 복잡도를 꼭 이해하고 계산할 수 있어야 함

 

(3) 알고리즘 성능 표기법

- 최악 ? 최상 ? 평균 ?

Big O (빅-오) 표기법	O(N)	- 알고리즘 최악의 실행 시간을 표기 - 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
Ω(N) (오메가) 표기법	Ω(N)	- 알고리즘 최상의 실행 시간을 표기
Θ(N) (세타) 표기법	Θ(N)	- 오메가 표기법은 알고리즘 평균 실행 시간을 표기

- 주로 빅오 표기법을 많이 사용

• O(1), O(𝑙𝑜𝑔𝑛logn), O(n), O(n𝑙𝑜𝑔𝑛logn), O(𝑛2n2), O(2𝑛2n), O(n!)등으로 표기함

 

 

경우 1 : O(1)

무조건 2회(상수회) 실행한다 : O(1)

if n>10 :
	print(n)

 

 

경우 2 : O(n)

n에 따라 n번, n+10번 또는 3n+10번 등을 실행한다.

variable = 1

for num in range(3) :
	for index in range(n) :
    	print(index)

 

 

경우 3 : O(n^2)

n에 따라 n^2번, n^2 + 1000번 등을 실행한다.

vairable = 1

for num in range(n) :
	for index in range(n) :
    	print(index)

 

데이터 인풋에 따른 시간

 

 

2. 해쉬 테이블 (Hash Table)

(1) 해쉬 구조란 

- Key에 데이터를 저장하는 구조

- 파이썬의 딕셔너리가 해쉬 테이블의 예임 

 

 

해시 구조가 배열보다 유용한 이유

EX) 예를 들어 "MINJU" 라는 값을 찾으려면, 배열의 경우에는 1 ~ 13까지 다 봐야함,

그러나 해쉬는 KEY 값으로 MINJU를 찾을 수 있음

 

 

(2) 알아둘 용어

- 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것

- 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조

- 해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

- 해쉬 값(Hash Value) : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음

- 슬롯(Slot) : 한 개의 데이터를 저장할 수 있는 공간

- 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

 

※ k가 해쉬함수의 입력값임 

 

(3) 간단한 hash 

(3-1) hash table 만들기

hash_table = list([i for i in range(10)])
hash_table


>>> [0,0,0,0,0,0,0,0,0,0]

 

(3-2) hash function 만들기

def hash_func(key) :
	return key%5
    
    
# key 값이 10,1000,10000든 고정된 길이로 나옴

 

(3-3) 해쉬 테이블에 저장하기

data1 = 'Andy'
data2 = 'Dave'
data3 = 'Trump'

## ord() : 문자의 ASCII(아스키) 코드 리턴
print(ord(data1[0]),ord(data1[1]),ord(data1[2]))
>>> 65 68 84

print(ord(data1[0]),hash_function(ord(data1[0])))
>>> 65 0

 

(3-4) 해쉬 테이블에 값 저장 예

def storage_data(data, value) :
	key = ord(data[0])
    hash_address = hash_func(key)
    hash_table[hash_address] = value

 

(3-5) 해쉬 테이블에서 특정 주소의 데이터를 가져오는 함수 만들기

storage_data('Andy', '01055553333')
storage_data('Dave', '01044443333')
storage_data('Trump', '01022223333')


def get_data(data):
    key = ord(data[0])
    hash_address = hash_func(key)
    return hash_table[hash_address]
    
    
get_data('Andy')
>>> '01055553333'

 

(5) 해시 테이블 장단점

- 장점 : 데이터 저장 및 읽기 속도가 빠름, 키에 대한 데이터가 있는지(중복) 확인이 쉬움

- 단점 : 저장공간이 좀 더 많이 필요함, 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함

- 주요용도 : 검색이 많이 필요한 경우, 저장&삭제&읽기가 빈번한 경우, 캐쉬 구현시

 

 

(6) 해쉬테이블 구현

 

(6-1) 리스트 변수를 활용해서 해쉬 테이블 구현해보기

1. 해쉬함수 : key % 8
2. 해쉬 키 생성 : hash(data)

hash_table = list([0 for i in range(8)])

def get_key(data) :
	return hash(data)
    
def hash_function(key) :
	return key%8
    
def save_data(data, value) :
	hash_address = hash_function(get_key(data))
    	hash_table[hash_address] = value
    
def read_data(data) :
	hash_address = hash_function(get_key(data))
    	return hash_table[hash_address]

 

(7) 충돌해결 알고리즘

 

(7-1) Chaining 기법  : 테이블 밖에 자료를 저장

- 개방 해슁 또는 Open hashing 기법 중 하나

- 충돌이 일어나면, 링크드 리스트라는 자료구조를 사용해서, 링크드 리스트로 뒤에 데이터를 추가로 붙임

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)      # index key를 slot에 추가적으로 저장
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:   # 데이터가 들어가 있다는 뜻
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                hash_table[hash_address][index][1] = value
                return
        hash_table[hash_address].append([index_key, value]) #append로 링크드리스트를 구현함
    else:
        hash_table[hash_address] = [[index_key, value]]
    
    
def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)

    if hash_table[hash_address] != 0:
        for index in range(len(hash_table[hash_address])):
            if hash_table[hash_address][index][0] == index_key:
                return hash_table[hash_address][index][1]
        return None
    else:
        return None

 

 

(7-2) Linear Probing 기법

- 폐쇄 해슁 또는 Close hashing 기법 중 하나

- 저장공간의 활용도를 높일 수 있음

hash_table = list([0 for i in range(8)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                hash_table[index] = [index_key, value]
                return
            elif hash_table[index][0] == index_key:
                hash_table[index][1] = value
                return
    else:
        hash_table[hash_address] = [index_key, value]

def read_data(data):
    index_key = get_key(data)
    hash_address = hash_function(index_key)
    
    if hash_table[hash_address] != 0:
        for index in range(hash_address, len(hash_table)):
            if hash_table[index] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

 

 

3. 트리

(1) 트리 구조란 ?

- 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조

- 실제로 어디에 많이 사용되나 ? : 트리 중 이진 트리 형태의 구조로, 탐색 알고리즘 구현에 사용됨

 

(2) 알아둘 용어

- Node : 트리에서 데이터를 저장하는 기본요소

- Root Node : 트리 맨 위에 있는 노드

- Level : 최상위 노드를 Level 0 으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타냄

- Paraent Node : 어떤 노드의 다음 레벨에 연결된 노드

- Child Node : 어떤 노드의 상위 레벨에 연결된 노드

- Leaf Node : Child Node가 하나도 없는 노드

- Sibling : 동일한 Parent Node를 가진 노드

- Depth : 트리에서 Node가 가질 수 있는 최대 Level

 

 

(3) 이진 트리와 이진 탐색 트리

- 이진 트리 : 노드의 최대 Branch가 2인 트리

- 이진 탐색 트리 : 이진 트리에 추가적인 조건이 있음

  -> 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

 

이진탐색트리 예시

 

- 주요 용도 : 데이터 검색(탐색)

- 장점 : 탐색 속도를 계산할 수 있음

 

(4) 파이썬 객체지향 프로그래밍으로 링크드 리스트 구현하기

 

(4-1) 노드 클래스 만들기

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

 

(4-2) 이진 탐색 트리에 데이터 넣기

class NodeMgmt:
    def __init__(self, head):
        self.head = head
    
    def insert(self, value):
        self.current_node = self.head
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break

 

추가 예정 ,,,