알고리즘 3주차

Stack/Queue/Hash

Stack

• 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. (빨래통..)
• Last In First Out (LIFO)
• 넣은 순서가 필요할 때 사용
• 스택자료구조에서 제공하는 기능
  push(data) : 맨 앞에 데이터 넣기
  pop() : 맨 앞의 데이터 뽑기
  peek() : 맨 앞의 데이터 보기
  isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기
• 데이터 넣고 뽑는 걸 자주하는 자료 구조 => 링크드리스트로 구현

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


class Stack:
    def __init__(self):
        self.head = None

    # push 기능 구현
    def push(self, value):
        if self.is_empty():
            self.head = Node(value)
        else:
            new_head = Node(value)
            new_head.next = self.head
            self.head = new_head

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return 'empty!'
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    # peek 기능 구현
    def peek(self):
        if self.is_empty():
            return 'empty!'

        return self.head.data

    # isEmpty 기능 구현
    def is_empty(self):
        return self.head is None

stack = Stack()
stack.push(3)
print(stack.peek())
stack.push(4)
print(stack.peek())
print(stack.pop())
# print(stack.is_empty())
print(stack.peek())

스택문제 - 탑

top_heights = [6, 9, 5, 7, 4]

def get_receiver_top_orders(heights):
    receiver = [0] * len(heights)
    for i in range(4,-1,-1):
        for j in range(i-1,-1,-1):
            if heights[i] < heights[j]:
                receiver[i] = j + 1
                break
    return receiver

print(get_receiver_top_orders(top_heights))

=>풀고 보니 스택으로 풀지않음....

top_heights = [6, 9, 5, 7, 4]

def get_receiver_top_orders(heights):
    receiver = []
    while heights:     #heights가 빈상태가 아닐때까지 반복
        height = heights.pop()
        for i in range(len(heights) - 1, -1, -1):
            if height < heights[i]:
                receiver[len(heights)] = i + 1
                break
            
    return receiver

print(get_receiver_top_orders(top_heights))

Queue

• 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조. (놀이기구..)
• First In First Out (FIFO)
• 먼저 들어온 순서대로 처리해야 할 때, 먼저 해야 하는 일들을 저장하고 싶을 때
• 큐 자료구조에서 제공하는 기능
  enqueue(data) : 맨 뒤에 데이터 추가하기
  dequeue() : 맨 앞의 데이터 뽑기
  peek() : 맨 앞의 데이터 보기
  isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기
• 데이터를 넣고 뽑는 걸 자주하는 자료구조 => 링크드리스트
• 스택과 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야 하므로,
  self.head 와 self.tail 을 가지고 시작

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


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, value):
        new_node = Node(value)
        if self.is_empty():
            self.head = new_node
            self.tail = new_node
            return

        self.tail.next = new_node
        self.tail = new_node

    def dequeue(self):
        if self.is_empty():
            return 'empty!'

        pick_node = self.head
        self.head = self.head.next

        return  pick_node.data

    def peek(self):
        if self.is_empty():
            return 'empty!'

        return self.head.data

    def is_empty(self):
        return self.head is None

hash - 1

• 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조.
• 해쉬 테이블은 해쉬 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산.
• 해쉬 함수(Hash Function)는 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수.
• 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행.
• 딕셔너리를 해쉬 테이블이라고 부르기도 함.
  딕셔너리는 내부적으로 배열을 사용함.

class Dict:
    def __init__(self):
        self.items = [None] * 8

    def put(self, key, value):
        # index = hash(key) % len(self.items)
        self.items[hash(key) % 8] = value

    def get(self, key):
        return self.items[hash(key) % 8]


my_dict = Dict()
my_dict.put("test", 3)
print(my_dict.get("test"))  # 3이 반환되어야 합니다!

인덱스 값이 같아지는 충돌이 발생함.
해결방법1) 링크드 리스트를 이용하여 해결 (chaining)

class LInkedTuple:
    def __init__(self):
        self.items = list()
        
    def add(self, key, value):
        self.items.append(key, value)
        
    def get(self, key):
        for k, v in self.items:
            if key == k:
                return v
            
class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LInkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

해결방법2) 배열의 다음 남는 공간에 넣기 (개방 주소법(Open Addressing))
-코드구현은 넘어감.

hash - 2

출석체크

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]


def get_absent_student(all_array, present_array):
    dict = {}
    for stud in all_array:
        dict[stud] = True

    for stud in present_array:
        del dict[stud]

    for stud in dict:
        return stud
    # for key in dict.keys():  # key 중에 하나를 바로 반환합니다! 한 명 밖에 없으니 이렇게 해도 괜찮습니다.
    #    return key


print(get_absent_student(all_students, present_students))

시간복잡도 : O(N) / 공간복잡도 : O(N)
=> 해쉬 테이블은 시간은 빠르되 공간을 대신 사용하는 자료구조

3주차 숙제

최대로 할인

shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]


def get_max_discounted_price(prices, coupons):
    shop_prices.sort(reverse=True)
    user_coupons.sort(reverse=True)
    index = 0
    sum_price = 0

    while index < min(len(shop_prices), len(user_coupons)):
        sum_price += shop_prices[index] * (100 - user_coupons[index]) / 100
        index += 1

    while index < len(shop_prices):
        sum_price += shop_prices[index]
        index += 1
    return round(sum_price)


print(get_max_discounted_price(shop_prices, user_coupons))  # 926000 이 나와야 합니다.

올바른 괄호

s = "(())()"

def is_correct_parenthesis(string):
    stack = []

    for i in range(len(string)):
        if string[i] == '(':
            stack.append('(')
        elif string[i] == ')':
            if stack == []:
                return False
            stack.pop()

    if len(stack) == 0:
        return True
    else:
        return False

print(is_correct_parenthesis(s))  # True 를 반환해야 합니다!

베스트 앨범

genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]


def get_melon_best_album(genre_array, play_array):
    n = len(genre_array)
    total_play = {}
    all_index_play = {}

    #장르별 플레이 횟수 비교
    for i in range(n):
        genre = genre_array[i]
        play = play_array[i]
        if genre not in total_play:
            total_play[genre] = play
            all_index_play[genre] = [(i, play)]
        else:
            total_play[genre] += play
            all_index_play[genre].append((i, play))

    #딕셔너리 정렬
    sorted_total_play_array = sorted(total_play.items(), key=lambda item: item[1], reverse=True)
    result = []
    for genre, value in sorted_total_play_array:
        index_play_array = all_index_play[genre]
        sorted_all_index_play_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
        for i in range(len(sorted_all_index_play_array)):
            if i > 1: #2개만 가져옴
                break
            result.append(sorted_all_index_play_array[i][0]) #인덱스 반환
    return result

print(get_melon_best_album(genres, plays))  # 결과로 [4, 1, 3, 0] 가 와야 합니다!

GIT 1주차

git

• 프로젝트의 버전 관리를 위한 도구.
• 무슨 작업을 했는지 히스토리를 볼 수 있음.
• 기능을 완성할 때마다 작업 내역을 저장하면 어떤 부분을 만들 때 에러가 발생했는지 쉽게 파악할 수 있음.
• 협업해서 하나의 프로젝트를 만들 때 유용.
  누가, 언제, 어떤 부분을 수정했는지를 한 눈에 파악할 수 있음.
• 기본 설정으로는 코드(Python, HTML, JavaScript, Java,...) text 파일, markdown파일(text 파일의 일종), CSV 파일 등 만 자동으로 내용을 비교해줌.
  다른 파일은 따로 설정이 필요하며, 기본설정으로는 파일의 크기가 변했구나 정도만 알 수 있음.

github

• git 원격 저장소 + 커뮤니티 기능 서비스
• 개발자들의 SNS
• 비슷한 기능을 제공하는 곳으로는 대표적으로 Gitlab, bitbucket 등이 있다.

sourcetree

• git을 쉽게 사용할 수 있는 도구

버전관리와 commit

• Git 에서는 버전별로 파일을 만들어줄 필요없이 중간중간 Git 을 사용해 현재 프로젝트의 상태만 저장해주면 '누가, 언제, 현재 프로젝트의 상태가 어떤지(현재 파일 내용들)' 세 가지 정보를 포함해 작업내역을 관리함.
• 현재 프로젝트 상태를 저장한 것을 commit(커밋)이라고 표현함.