2022.11.14 TIL

9:00 - 9:50
공부 준비

10:00 - 10:50
쉽게 배우는 알고리즘 3-5 스택Stack
스택은 맨 앞(self.head)에서 들어오고 나감, LIFO(Last In First Out)

class Stack:
    def __init__(self):
        self.head = None
    def push(self, value): # 맨 앞에 데이터 넣기
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head
        return
    # pop 기능 구현
    def pop(self): # 맨 앞의 데이터 뽑기
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head
    def peek(self): # 맨 앞의 데이터 보기
        if self.is_empty():
            return "Stack is empty"
        return self.head.data
    # isEmpty 기능 구현
    def is_empty(self): # 비어있는지 확인하기
        return self.head is None

python에서는 push 기능으로 append, pop 기능으로 pop 메서드 사용

11:00 - 11:50
스택 퀴즈

내가 적은 답: 왼쪽부터 모든 경우의 수를 계산하는 방식

top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
    stack = []
    array = [0] * len(heights)
    array_index = 0
    for i in heights:
        stack.append(i)
        index = 0
        for j in stack:
            index += 1
            if i < j:
                array[array_index] = index
        array_index += 1
    return array
print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

정답: 오른쪽부터 pop을 사용해 제거해가며 비교하는 방식

top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
    answer = [0] * len(heights)
    while heights:
        height = heights.pop()
        for idx in range(len(heights)-1, 0, -1):
            if heights[idx] > height:
                answer[len(heights)] = idx+1
                break
    return answer
print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

12:00 - 13:00
쉽게 배우는 알고리즘 3-6 큐Queue
큐는 맨 앞(self.head)에서 들어오고 맨 뒤에서 나감,FIFO(First In First Out)

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 = self.tail.next
        return
    def dequeue(self): # 맨 앞의 데이터 뽑기
        if self.is_empty():
            return "Queue is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data
    def peek(self): # 맨 앞의 데이터 보기
        if self.is_empty():
            return "Queue is Empty"
        return self.head.data
    def is_empty(self): # 비어있는지 확인하기
        return self.head is None

14:00 - 16:00
쉽게 배우는 알고리즘 3-7, 8 해쉬(해시)Hash

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]: # 왜 8인지 잘 모르겠음
            self.items.append(LinkedTuple())
    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)
        return
    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
def get_absent_student(all_array, present_array):
    student_dict = {}
    for key in all_array:
        student_dict[key] = True # *공간복잡도가 O(N)*, True 대신 아무 값이나 상관 없음
    for key in present_array:
        del student_dict[key]
    for key in student_dict.keys(): # keys = 모든 키를 의미, 고정되어 있는 이름
        return key
print(get_absent_student(all_students, present_students))

• 해쉬를 사용하여 key 값들을 넣고, 키를 제거하는 방향으로 진행
• 아래 반복문(N^2)에 비해 시간복잡도는 N으로 매우 적으나 key를 보관하는 공간복잡도가 늘어남
• 시간복잡도와 공간복잡도의 상호 교환 but 대부분의 경우 시간복잡도가 매우 중요

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
    for i in all_array:     # 반복으로 찾는 법(내가 작성), O(N^2) 시간 복잡도를 가짐
        if i in present_students:
            continue
        else:
            return i
print(get_absent_student(all_students, present_students))

16:00 - 21:00
3주차 숙제 : 쓱 최대로 할인 적용하기
나의 답

shop_priaces = [30000, 2000, 1500000]
user_coupons = [20, 40]
def get_max_discounted_price(prices, coupons):
    for i in range(len(prices)-1):
        for j in range(len(prices)-1-i):
            if prices[j] < prices[j+1]:
                prices[j], prices[j+1]= prices[j+1], prices[j]
    for i in range(len(coupons)-1):
        for j in range(len(coupons)-1-i):
            if coupons[j] < coupons[j+1]:
                coupons[j], coupons[j+1]= coupons[j+1], coupons[j]
    prices_sum = 0
    for i in range(len(prices)):
        if i <= len(coupons)-1:
            prices_sum += prices[i] * (1 - coupons[i] * 0.01)
        else:
            prices_sum += prices[i]
    prices_sum = int(prices_sum)
    return prices_sum
print(get_max_discounted_price(shop_priaces, user_coupons))

정답지

shop_priaces = [30000, 2000, 1500000]
user_coupons = [20, 40]
def get_max_discounted_price(prices, coupons):
    prices.sort(reverse=True)       # sort 사용하면 편리함
    coupons.sort(reverse=True)
    price_index = 0
    coupon_index = 0
    max_discounted_price = 0
    while price_index < len(prices) and coupon_index < len(coupons):
        max_discounted_price += prices[price_index] * (100 - coupons[coupon_index]) / 100
        price_index +=1
        coupon_index +=1
    while price_index < len(prices):
        max_discounted_price += prices[price_index]
        price_index +=1
    return max_discounted_price

• sort를 사용해도 되는지 모르고 수업에서 나온 방식을 적용하여 풀이하였다.
• sort, sorted 사용이 가능함을 알았다면 훨씬 시간을 단축할 수 있었는데 아쉽다.

3주차 숙제 : 괄호 짝짓기
나의 답

s = "(())()"
def is_correct_parenthesis(string):
    left_count = 0
    right_count = 0
    for i in string:
        if i == "(":
            left_count +=1
        else:
            right_count +=1
        if left_count < right_count:
            return False
    return left_count == right_count
print(is_correct_parenthesis(s))  # True 를 반환해야 합니다!

답안지

s = "(())()"
def is_correct_parenthesis(string):
    stack = []           # 당연히 총 개수를 세어서 풀거라고 생각했는데 stack 개념으로 pop을 활용한 것이 재미있음
    for i in range(len(string)):
        if string[i] == "(":
            stack.append(i)
        elif string[i] == ")":
            if len(stack) == 0:
                return False
            stack.pop()
    if len(stack) == 0:
        return True
    else:
        return False

• 개인적으로 이번 문제는 내가 풀이한 방법이 더 합리적이라고 생각한다.
• 답안에서 stack의 개념을 적용하여 pop을 활용하는 것이 참신하게 느껴진다.

3주차 숙제 : 멜론 베스트 앨범 뽑기

genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
def get_melon_best_album(genre_array, play_array):
    genre_total_play_dict = {}   # 중괄호 {}는 딕셔너리를 의미
    genre_index_play_array_dict = {}
    for i in range(len(genre_array)):
        genre = genre_array[i]
        play = play_array[i]
        if genre not in genre_total_play_dict:      # key not in 사용 방법
            genre_total_play_dict[genre] = play
            genre_index_play_array_dict[genre] = [[i, play]]    # key, value 사용 형식 기억할 필요 있음, 대괄호 두 번 쓰는 이유 
        else:
            genre_total_play_dict[genre] += play
            genre_index_play_array_dict[genre].append([i, play])		# 여기 때문에 대괄호로 묶어야 같이 나오는 듯..
    sorted_genre_play_array = sorted(genre_total_play_dict.items(), key=lambda x: x[0], reverse=True)
    result = []
    for genre, _value in sorted_genre_play_array:  # _value 없어도 됨
        index_play_array = genre_index_play_array_dict[genre]
        sorted_index_play_array = sorted(index_play_array, key=lambda x: x[1], reverse=True)
        for i in range(len(sorted_index_play_array)):
            if i > 1:
                break
            result.append(sorted_index_play_array[i][0])
    return result
print(get_melon_best_album(genres, plays))

• key, value를 적용하는 방식이 익숙하지 않아 많이 헤맸던 부분이다.
• 후반부의 sorted는 전혀 몰랐어서 key를 기준으로 정렬하는 방법이 있음을 새로 배웠다.
• key 기준 정렬이 필요하다고 생각되면 구글에 그 생각을 바로 검색하는 습관이 아직 부족함을 느낀다.