0621 - 0627

0621

테스트 2차 준비 6일차

오늘부터 다시 한 주가 시작되었다.
자료구조를 어떻게 학습해야 내 것으로 만들지 고민해본 결과, 기본 인터넷강의를 듣고 그와 관련된 코딩 문제를 풀어보려고 한다.
오늘은 배열과 큐, 스택에 대해 학습하였다.
가장 익숙하기도 한 것들이지만, 파이썬에서는 이것들을 어떻게 구현하는지 알아보았다.

배열, 큐, 스택

자료구조

• 자료구조, 데이터 구조, data structure
• 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조
• 어떤 데이터 구조를 사용하느냐에 따라 효율이 달라짐

대표적인 자료구조

• 배열, 큐, 스택, 링크드리스트, 해쉬테이블, 힙

알고리즘

• 어떤 문제를 풀기 위한 절차 / 방법
• 어떤 자료구조, 알고리즘을 쓰느냐에 따라 성능이 천지차

배열

• 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조
• 파이썬에서는 리스트 타입이 배열 기능을 제공함

배열을 사용하는 이유

• 같은 종류의 데이터를 효율적으로 관리하기 위해 사용
• 같은 종류의 데이터를 순차적으로 저장
• 장점 : 빠른 접근 가능
  • 첫 데이터의 위치에서 상대적인 위치로 데이터 접근 (인덱스 번호로 접근)
• 단점 : 데이터 추가/삭제의 어려움
  • 미리 최대 길이를 지정해야 함

큐

• 가장 먼저 넣는 데이터를 가장 먼저 꺼낼 수 있는 구조
• FIFO 또는 LILO 방식으로 스택과 꺼내는 순서가 반대
• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능

파이썬 queue 라이브러리 활용해서 큐 자료구조 사용

• queue 라이브러리에는 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
• 프로그램을 작성할 때 프로그램에 따라 적합한 자료 구조를 사용
  • Queue() : 가장 일반적인 큐 자료 구조
  • LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조 (스택 구조라고 보면 됨)
  • PriorityQueue() : 데이터마다 우선순위를 넣어서 ,우선순위가 높은 순으로 데이터 출력
• 일반적인 큐 외에 다양한 정책이 적용된 큐들이 있음
• 큐는 주로 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨
• 큐의 경우 특별히 언급되는 장단점이 없다.

import queue

data_queue = queue.Queue()

data_queue.put("funcoding")
data_queue.put(1)

print(data_queue.get())
print(data_queue.qsize())

# 결과
"funcoding"
1

스택

• 데이터를 제한적으로 접근할 수 있는 구조
  • 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
• 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
• 스택은 LIFO또는 FILO 데이터 관리 방식을 따름
• 대표적인 스택의 활용 방법으로는 컴퓨터 내부의 프로세스 구조의 함수 동작 방식
• push() : 데이터를 스택에 넣기
• pop() : 데이터를 스택에서 꺼내기

스택의 장단점

장점

• 구조가 단순해서, 구현이 쉽다.
• 데이터 저장/읽기 속도가 빠르다.

단점 (일반적인 스택 구현시)

• 데이터 최대 갯수를 미리 정해야 한다.
  • 파이썬의 경우 재귀 함수는 1000번까지만 호출이 가능함
• 저장 공간의 낭비가 발생할 수 있음
  • 미리 최대 갯수만큼 저장 공간을 확보해야 함
• 스택은 단순하고 빠른 성능을 위해 사용되므로, 보통 배열 구조를 활용해서 구현하는 것이 일반적. 이 경우, 열거한 단점이 있을 수 있음

파이썬 리스트 기능에서 제공하는 메서드로 스택 사용

data_stack = list()

data_stack.append(1)
data_stack.append(2)

print(data_stack.pop())

# 결과
2

0622

테스트 2차 준비 7일차

오늘은 링크드 리스트에 대해 학습하였다.
확실히 어제에 비해 난이도가 있었다.
또 문제를 제출한 뒤 3분 뒤에 문제를 풀어서 너무 아쉬웠다.
실력 부족이라 생각하고 내일은 더 열심히 공부해야겠다.

링크드 리스트

• 연결 리스트라고도 함
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조이지만, 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조이다.
• 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원한다.
• 노드 : 데이터 저장 단위(데이터값, 포인터)로 구성
• 포인터 : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간

Node 구현

• 보통 파이썬에서 링크드 리스트 구현시, 파이썬 클래스를 활용

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

링크드 리스트의 장단점

• 장점
  • 미리 데이터 공간을 할당하지 않아도 됨
• 단점
  • 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음
  • 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림
  • 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요

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

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

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

    def add(self, data):
        if self.head == '':
            self.head = Node(data)
        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self):
        node = self.head
        while node:
            print (node.data)
            node = node.next

• NodeMgmt class는 생성할 때 받은 데이터로 Node를 생성하며 head로 지정한다.
• add 메소드는 데이터를 리스트 끝에 추가한다.
• desc 메소드는 리스트 목록을 출력한다.

특정 노드를 삭제하는 메서드

    def delete(self, data):
        if self.head == '':
            print("해당 값을 가진 노드가 없습니다.")
            return

        if self.head.data == data:
            tmp = self.head
            self.head = self.head.next
            del tmp
        else:
            node = self.head
            while node.next:
                if node.next.data == data:
                    tmp = node.next
                    node.next = node.next.next
                    del tmp
                    return
                else:
                    node = node.next

테스트 2차 준비 8일차

시간 복잡도 - 알고리즘 복잡도

• 하나의 문제를 푸는 알고리즘은 다양할 수 있다.
• 다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산

알고리즘 복잡도 계산 항목

1. 시간 복잡도: 알고리즘 실행 속도
2. 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

• 가장 중요한 시간 복잡도를 이해하고 계산할 수 있어야 한다.
• 알고리즘 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문이다.

알고리즘 성능 표기법

• Big O (빅-오) 표기법
  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적으로 사용
  • 아무리 최악의 상황이라도, 이정도 성능은 보장한다는 의미
• 오메가 표기법
  • 알고리즘 최상의 실행 시간을 표기
• 세타 표기법
  • 세타 표기법은 알고리즘 평균 실행 시간을 표기

빅 오 표기법

• O(입력)
  • 입력 n에 따라 결정되는 시간 복잡도 함수
  • 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어남
    • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O (n!)
• 단순하게 입력 n에 따라, 몇 번 실행이 되는지를 계산하면 된다.
  • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기

해쉬 테이블

해쉬 구조

• Hash Table : 키 에 데이터를 저장하는 데이터 구조
  • Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐
  • 파이썬 딕셔너리 타입이 해쉬 테이블의 예
  • 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 밪바꾸는 기법)
  • 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입 사용
• 해쉬 : 임의 값을 고정 길이로 변환하는 것
• 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
• 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값 또는 해쉬 주소 : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음
• 슬롯 : 한 개의 데이터를 저장할 수 있는 공간
• 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음

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

• 장점
  • 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  • 해쉬는 키에 데이터가 있는지(중복) 확인이 쉽다.
• 단점
  • 일반적으로 저장공간이 좀 더 많이 필요하다.
  • 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요
• 주요 용도
  • 검색이 많이 필요한 경우
  • 저장, 삭제, 읽기가 빈번한 경우
  • 캐쉬 구현시

파이썬에서 리스트 변수를 활용해서 해쉬 테이블 구현

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')
print(read_data('Andy'))

# 결과
01033232200

충돌(Collision) 해결 알고리즘

• 해쉬 테이블의 가장 큰 문제는 충돌의 경우이다.
• 이 문제를 충돌 또는 해쉬 충돌이라고 부른다.

Chaining 기법

• 개방 해슁 또는 Open Hashing 기법 중 하나
• 해쉬 테이블 저장공간 외의 공간을 활용하는 기법
• 충돌이 일어나면, 링크드 리스트라는 자료 구조를 사용해서, 링크드 리스트로 데이터를 추가로 뒤에 연결시켜서 저장하는 기법

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]
            else:
                return None
    else:
        return None

• save_data와 read_data만 변경
• 데이터의 키 값을 따로 저장하기 위해 index_key 변수를 선언해서 저장
• 데이터 저장 시, 해시 테이블에서 해쉬 주소에 데이터가 없다면 리스트를 선언하고 index_key값과 value를 저장
• 데이터가 있다면, 해당 해시 주소에 있는 데이터의 개수만큼 반복문을 실행하여 왼쪽에 저장한 값들과 index_key를 비교
• 왼쪽 값과 index_key 값이 같다면 기존의 것을 수정
• 같은 값이 없다면 리스트에 새로운 데이터를 추가
• 데이터 검색 시, 해시 테이블에서 해쉬 주소에 데이터가 없다면 None을 반환
• 데이터가 있다면, 해당 해시 주소에 있는 데이터의 개수만큼 반복문을 실행하여 왼쪽에 저장한 값들과 index_key를 비교
• 왼쪽 값과 index_key 값이 같다면 오른쪽에 저장된 value를 반환
• 같은 값이 없다면 해당하는 키가 없으므로 None 반환

Linear Probing 기법

• 혜쇄 해슁 또는 Closing Hashing 기법 중 하나
• 해쉬 테이블 저장공간 안에서 충돌 문제를 해결하는 기법
• 충돌이 일어나면, 해당 hash address의 다음 address부터 맨 처음 나오는 빈공간에 저장하는 기법
• 저장공간 활용도를 높이기 위한 기법

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] == 0:
                return None
            elif hash_table[index][0] == index_key:
                return hash_table[index][1]
    else:
        return None

• 데이터 저장 시, 해시 테이블에서 해시 주소에 해당하는 값이 없다면 index_key와 value를 저장한다.
• 해시 주소에 해당하는 값이 있다면, hash_address부터 hash_table의 개수만큼 인덱스를 이용해 반복문을 실행한다.
• hash_table에서 값이 없는 index를 발견한다면, 해당 인덱스에 index_key와 value를 저장한다.
• 혹은 index 왼쪽 값이 index_key와 같은 값이 있다면 해당 value를 수정한다.
• 검색의 경우도 마찬가지로 반복문을 활용하여, 인덱스의 왼쪽 값이 0이거나 해당 주소에 맞는 값이 없다면 None을 반환한다.
• 인덱스의 왼쪽 값이 index_key와 같다면 해당 인덱스의 오른쪽 값을 반환해준다.

빈번한 충돌을 개선하는 방법

• 해쉬 함수를 재정의 및 해쉬 테이블 저장공간을 확대

hash_table = list([None for i in range(16)])

def hash_function(key):
    return key % 16

해쉬 함수와 키 생성 함수

• 파이썬의 hash() 함수는 실행할 때마다 값이 달라질 수 있음
• 유명한 해쉬 함수들이 있는데 제일 대표적으로 SHA 함수가 있다.
  • 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능하다.

시간 복잡도

• 일반적인 경우(충돌이 없는 경우)는 O(1)
• 최악의 경우(충돌이 모두 발생하는 경우)는 O(n)
• 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에, 시간 복잡도는 O(1)이라고 말할 수 있다.
• 검색에서 16개의 배열에 데이터를 저장하고, 검색하면 O(n)
• 16개의 데이터 저장공간을 가진 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

0624

테스트 2차 준비 9일차

트리

트리 구조

• Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 쿠조
• 트리 중 이진 트리 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용

용어

• Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
• 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인 트리
• 이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
  • 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

자료 구조 이진 탐색 트리의 장점과 주요 용도

• 주요 용도: 데이터 검색
• 장점 : 탐색 속도를 개선할 수 있다.

파이썬 객체지향 프로그래밍으로 트리 구현하기

Node 클래스

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

• 노드는 값을 받아서 저장할 수 있게 한다.
• child Node의 주소값을 저장하는 left와 right의 기본값으로 None을 설정한다.

NodeMgmt 클래스와 데이터 삽입, 검색

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

• 생성할 때 head 노드를 정해서 루트 노드로 설정한다.
• insert 메소드는 매개 변수로 value를 받아서 저장하는 메소드이다.
• current_node에 루트 노드를 저장한 뒤, 무한 루프를 도는 반복문을 실행해서 value가 루트 노드의 값보다 작고 루트 노드의 left 값이 None이 아니라면 left의 값을 current_node에 저장해서 다시 반복문을 돌게 한다.
• 그러다가 left 값이 비어 있는 노드를 발견하면 left에 새로운 노드를 생성하고 그 안에 값을 집어 넣어서 트리를 구성하도록 한다.
• search 메소드는 value를 매개 변수로 받아서 해당 값을 가진 노드 탐색에 성공하면 True를 반환하고, 실패하면 False를 반환한다.
• 마찬가지로 루트 노드를 변수에 저장하고, 변수가 None이 아닐 동안 돌아가는 반복문을 실행시킨다.
• 만약 노드의 값이, value와 같다면 값을 찾았으므로 True를 리턴하고, 같지 않다면 value가 작은 경우에는 left의 값을 current_node로, 큰 경우에는 right의 값을 current_node로 해서 반복문을 실행한다.
• current_node가 비어있다면 value의 값을 가진 노드가 생성되지 않은 것이므로 반복문을 빠져나와서 False를 반환한다.

이진 트리 삭제

• 이진 트리의 값을 삭제하는 상황에서는 경우가 매우 많으므로, 나누어서 이해해야 한다.
• Leaf Node를 삭제하는 경우에는 삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 해야 한다.
• Child Node를 삭제하는 경우에는 삭제할 Node의 Parent Node가 삭제할 Node의 Chile Node를 가리키도록 해야 한다.
• Child Node가 두 개인 Node를 삭제하는 경우는 가장 복잡한 경우로 두가지 방식으로 나뉜다.
  1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 하는 경우
  2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 하는 경우
• 나는 1번 방식을 사용할 것인데 그럴 경우에는 먼저 삭제할 Node의 오른쪽 자식을 선택한 후 가장 작은 값인 오른쪽 자식의 가장 왼쪽에 있는 Node를 선택한다.
• 해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 한다.
• 해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 한다.
• 해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 한다.
• 만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 한다.

이진 탐색 트리의 시간 복잡도와 단점

• n개의 노드를 가진다면, 트리의 높이는 logn에 가까우므로, 시간 복잡도는 O(logn)
• 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미
• 평균 시간 복잡도는 O(logn)이지만, 이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며, 최악의 경우 링크드 리스트와 동일한 성능을 보여줌 O(n)

0625 TIL

테스트 2차 준비 10일차

힙

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
  • 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면, O(logn)이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

힙 구조

• 힙은 최대값을 구하기 위한 구조와, 최소값을 구하기 위한 구조로 분류
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조이다.
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
  2. 완전 이진 트리 형태를 가짐

힙과 이진 탐색 트리의 공통점과 차이점

• 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리
• 차이점:
  • 힙은 각 노드의 값이 자식 노드보다 크거나 같음 (최대 힙)
  • 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
  • 힙은 이진 탐색 트리의 조건인 자식 노드에서 왼쪽, 오른쪽의 값 크기를 비교하지 않음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

힙 동작

• 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

힙에 데이터 삽입 - 삽입할 데이터가 힙의 데이터보다 클 경우

• 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
• 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업 반복(swap)

힙 데이터 삭제

• 보통 삭제는 최상단 루트 노드를 삭제
• 상단의 데이터 삭제 시, 가장 최하단부 왼쪽에 위치한 노드를 루트 노드로 이동
• 루트 노드의 값이 child node 보다 작을 경우, 루트 노드의 child node 중 가장 큰 값을 가진 노드와 루트 노드 위치를 바꿔주는 작업을 반복

힙 구현

힙과 배열

• 일반적으로 힙 구현 시 배열 자료구조를 활용
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해 루트 노드 인덱스 번호를 1로 지정하면, 구현이 좀 더 수월
  • 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 // 2
  • 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
  • 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1

힙 클래스 구현

class Heap:
    def __init__(self, data):
        self.heap_array = list()
        self.heap_array.append(None)
        self.heap_array.append(data)


    def move_up(self, inserted_idx):
            if inserted_idx <= 1:
                return False

            parent_idx = inserted_idx // 2
            if self.heap_array[inserted_idx] > self.heap_array[parent_idx]:
                return True
            else:
                return False

    def insert(self, data):
        if len(self.heap_array) == 0:
            self.heap_array.append(None)
            self.heap_array.append(data)
            return True

        self.heap_array.append(data)

        inserted_idx = len(self.heap_array) - 1

        while self.move_up(inserted_idx):
            parent_idx = inserted_idx // 2
            self.heap_array[inserted_idx], self.heap_array[parent_idx] = self.heap_array[parent_idx], self.heap_array[inserted_idx]
            inserted_idx = parent_idx

        return True

• 기본적으로 heap_array 변수에 리스트를 생성하여 0번째 인덱스에는 None을 삽입한다.
  • 인덱스 번호가 1번부터 시작하도록 설정
• insert 메소드는 힙에 데이터를 삽입하는 메소드이다.
• 힙 배열 길이가 0이면 제대로 생성되지 않은 것이므로, 0번 인덱스에 None을 삽입하고, data를 1번 인덱스에 삽입한다.
• 0이 아니면 append 메서드를 사용해서 heap_array에 데이터를 삽입한다.
• 삽입 후 데이터의 위치를 변경해주기 위해서 삽입된 데이터의 인덱스를 변수에 저장하고 move_up 메소드에서 True를 반환하는 동안 반복문을 실행시킨다.
• move_up 메소드는 해당 인덱스가 루트를 가리키거나 해당 인덱스의 값이 부모 인덱스의 값보다 작은 경우에만 False를 반환한다.
  • 이러한 경우에는 위치를 조정할 필요가 없기 때문에 반복문을 종료한다.
• 해당 인덱스 값이 부모 인덱스 값보다 큰 경우에는 해당 인덱스로 부모 인덱스를 계산해서 서로 위치를 바꾼다. 그리고 인덱스에 부모 인덱스 값을 설정해서 다시 반복문을 돌린다.

힙에 데이터 삭제 구현

• 보통 삭제는 최상단 노드를 삭제하는 것이 일반적이다.

def move_down(self, popped_idx):
    left_child_popped_idx = popped_idx * 2
    right_child_popped_idx = popped_idx * 2 + 1

    # case1: 왼쪽 자식 노드도 없을 때
    if left_child_popped_idx >= len(self.heap_array):
        return False
    # case2: 오른쪽 자식 노드만 없을 때
    elif right_child_popped_idx >= len(self.heap_array):
        if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
            return True
        else:
            return False
    # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
    else:
        if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                return True
            else:
                return False
        else:
            if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                return True
            else:
                return False

def pop(self):
    if len(self.heap_array) <= 1:
        return None

    returned_data = self.heap_array[1]
    self.heap_array[1] = self.heap_array[-1]
    del self.heap_array[-1]
    popped_idx = 1

    while self.move_down(popped_idx):
        left_child_popped_idx = popped_idx * 2
        right_child_popped_idx = popped_idx * 2 + 1

        # case2: 오른쪽 자식 노드만 없을 때
        if right_child_popped_idx >= len(self.heap_array):
            if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[
                    left_child_popped_idx], self.heap_array[popped_idx]
                popped_idx = left_child_popped_idx
        # case3: 왼쪽, 오른쪽 자식 노드 모두 있을 때
        else:
            if self.heap_array[left_child_popped_idx] > self.heap_array[right_child_popped_idx]:
                if self.heap_array[popped_idx] < self.heap_array[left_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[left_child_popped_idx] = self.heap_array[
                        left_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = left_child_popped_idx
            else:
                if self.heap_array[popped_idx] < self.heap_array[right_child_popped_idx]:
                    self.heap_array[popped_idx], self.heap_array[right_child_popped_idx] = self.heap_array[
                        right_child_popped_idx], self.heap_array[popped_idx]
                    popped_idx = right_child_popped_idx

    return returned_data

• pop 메서드는 루트 노드의 값을 반환하는 메서드이다.
• 반환한 데이터 변수에 1번 인덱스에 존재하는 최대값을 넣고, 맨 마지막에 삽입한 값을 최상단으로 올린다.
• move_down 메서드는 최상단으로 올린 값을 자식 노드의 값과 비교하여 내려야 하는지 참, 거짓을 반환하는 메서드이다.
• 해당 노드의 자식노드 수를 기준으로 케이스를 나눠서 구현한다.

0626 ~ 0627 TIL

2주간의 코딩 테스트를 마무리 했다.
열심히 했지만 처음 접하는 파이썬이라는 언어로 자료구조 시험을 보는 것을 2주만에 하려니 쉽지 않았다.
아직 결과가 나오지 않았지만 되든 안되든 좋은 경험이었다고 생각한다.
많이 부족함을 느끼고 다시 열심히 공부해야겠다고 다짐했다.