공부하자 동진아

Spring Framework

Spring Framework에 이해하기 위해서는 먼저 프레임워크가 무엇인지, 라이브러리와의 차이가 어떤건지 알고 가는게 중요하다. 라이브러리는 내가 필요할 때 사용하는 기능이고, 프레임워크는 프레임워크에 정해진 규칙을 따라서 개발을 해야한다.

스프링 프레임워크는 여러 라이브러리는 제공하고, 그것을 활용해서 개발한 프로그램을 동작시킨다.

스프링 프레임워크(Spring Framework)는 자바 플랫폼을 위한 오픈 소스 애플리케이션 프레임워크로서 간단히 스프링(Spring)이라도 한다. 동적인 웹 사이트를 개발하기 위한 여러 가지 서비스를 제공하고 있다.
대한민국 공공기관의 웹 서비스 개발 시 사용을 권장하고 있는 전자정부 표준프레임워크의 기반 기술로서 쓰이고 있다. 

출처 : 위키백과

스프링 프레임워크에서 가장 중요한 특징은 의존성 주입(Dependency Injection)이다.

의존성 주입(DI)은 클래스 사이의 의존관계를 빈(Bean) 설정 정보를 바탕으로 컨테이너가 자동으로 연결해주는 것이다.

DI가 적용되지 않으면 개발자가 직업 인스턴스를 생성해야한다.

HelloService service = new HelloService();

DI를 적용하면 annotiation인 @Component, @Autowired를 이용해서 선언 해주면 된다.

@Component
public class HelloService {
	
}

@RestController
public class HelloController {
	
    @Autowired
    private HelloService service;
    
}

Spring Boot

Spring Boot와 Spring Framework가 전혀 다른 새로운 기술이라고 오해하는 사람들이 있는데 Spring Boot는 Spring Framework를 조금더 편하게 사용할 수 있게 해주는 툴이다.

Spring Boot와 Spring Framework는 차이가 있다.

1. Spring Boot 내부에 Tomcat이 포함되어 있기 때문에 설치를 하거나 매번 버전을 관리해 주어야 할 필요가 없다.

2. Spring Framework에서는 dependency를 일일이 맞추어야 했지만 Spring Boot에서는 starter를 통한 dependency관리를 자동으로 해준다.

간단히 정리하자면 Spring Boot는 간편한 설정, 편리한 의전성 관리 & 자동 버전 관리, 내장 서버로 인한 간단한 배포 서버 구축, 다른 스프링 프레임워크 요소를 쉽게 사용하는 것이라고 생각한다.

트리 (Tree) 구조

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

- 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.

용어

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

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

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

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

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

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

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

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

이진 트리와 이진 탐색 트리 (Binary Search Tree)

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

- 이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리

  • 왼쪽 노드는 해당 노트보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

이진 탐색 트리의 장점과 주요 용도

- 장점 : 탐색 속도를 개선 가능

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

프로그래밍 연습

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

        
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
    
    def search(self, value):
        self.current_node = self.head
        while self.current_node:
            if self.current_node.value == value:
                return True
            elif value < self.current_node.value:
                self.current_node = self.current_node.left
            else:
                self.current_node = self.current_node.right
        return False        
    
    def delete(self, value):
        # 삭제할 노드 탐색
        searched = False
        self.current_node = self.head
        self.parent = self.head
        while self.current_node:
            if self.current_node.value == value:
                searched = True
                break
            elif value < self.current_node.value:
                self.parent = self.current_node
                self.current_node = self.current_node.left
            else:
                self.parent = self.current_node
                self.current_node = self.current_node.right

        if searched == False:
            return False    

        # case 1 : 삭제할 Node가 Leaf Node인 경우
        if  self.current_node.left == None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = None
            else:
                self.parent.right = None
        
        # case 2 : 삭제랄 Node가 Child Node를 한 개 가지고 있을 경우
        elif self.current_node.left != None and self.current_node.right == None:
            if value < self.parent.value:
                self.parent.left = self.current_node.left
            else:
                self.parent.right = self.current_node.left
        elif self.current_node.left == None and self.current_node.right != None:
            if value < self.parent.value:
                self.parent.left = self.current_node.right
            else:
                self.parent.right = self.current_node.right        
        
        # case 3-1 : 삭제할 Node가 Child Node를 두 개 가지고 있을 경우(삭제할 Node가 Parent Node 왼쪽)
        elif self.current_node.left != None and self.current_node.right != None:
            if value < self.parent.value:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.left = self.change_node
                self.change_node.right = self.current_node.right
                self.change_node.left = self.change_node.left
                
            # case 3-2 : 삭제할 Node가 Child Node를 두 개 가지고 있을 경우 (삭제할 Node가 Parent Node 오른쪽)
            else:
                self.change_node = self.current_node.right
                self.change_node_parent = self.current_node.right
                while self.change_node.left != None:
                    self.change_node_parent = self.change_node
                    self.change_node = self.change_node.left
                if self.change_node.right != None:
                    self.change_node_parent.left = self.change_node.right
                else:
                    self.change_node_parent.left = None
                self.parent.right = self.change_node
                self.change_node.left = self.current_node.left
                self.change_node.right = self.current_node.right

        return True

충돌(Collision) 해결 알고리즘 (좋은 해쉬 함수 사용)

- 해쉬 테이블에서 가장 큰 문제는 충돌(Collision)의 경우이다.

① 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)
    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])
    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

print(hash('Dave') % 8)
print(hash('Dd') % 8)
print(hash('Data') % 8)

2
0
1

save_data('Dd', '1201023010')
save_data('Data', '3301023010')
read_data('Dd')

'1201023010'

hash_table

[[[-7654392602558696976, '1201023010']],
 [[-9146221194023993367, '3301023010']],
 0,
 0,
 0,
 0,
 0,
 0]

② Linear Probing 기법

  • 폐쇄 해싱 또는 Close Hashing 기법 : 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법

  • 충돌이 일어나면, 해당 Hash Address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법

      • 저장공간 활용도를 높이기 위한 기법

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

print(hash('dk') % 8)
print(hash('da') % 8)
print(hash('dc') % 8)

3
5
2

save_data('dk', '01200123123')
save_data('da', '3333333333')
read_data('dc')

해쉬 구조

- Hash Table : 키(Key)에 데이터(Value)를 저장하는 데이터 구조

  • 파이썬 딕셔너리 타입이 해쉬 테이블의 예 : Key를 가지고 바로 데이터(Value)를 꺼냄

  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용

알아둘 용어

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

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

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

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

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

해쉬 테이블의 장단점과 주요 용도

- 장점

  • 데이터 저장/읽기 속도가 빠르다. (검색 속도 빠름)

  • 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움   

- 단점

  • 일반적으로 저장공간이 좀더 많이 필요

  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요

- 주요 용도

  • 검색이 많이 필요한 경우

  • 캐쉬 구현시 (중복 확인이 쉽기 때문에)

프로그래밍 연습

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]

save_data('Dave', '0102030200')
save_data('Andy', '01033232200')
read_data('Dave')

'0102030200'

hash_table
['0102030200', 0, 0, 0, 0, 0, 0, '01033232200']