내일배움캠프 AI, 16일차 TIL - 2022.09.21

스파르타 코딩클럽 내일배움캠프 AI 웹개발자양성과정 3회차

2022.09.21. 16일차 - TIL

 

 

1. 알고리즘, 자료구조 강의

• 3주차 과제 (1)
  - 문제 : 상품의 가격을 담은 배열과 쿠폰을 담은 배열이 주어질 때, 최대한 할인을 많이 받았을 때의 가격을 구하라(단, 쿠폰은 한 제품에 한 번씩만 적용 가능)
  - 풀이 : 가장 비싼 금액이 가장 많이 할인을 받게 한다.

def get_max_discounted_price(prices, coupons):
    prices.sort(reverse=True)  # 가격 배열을 내림차순 정렬
    coupons.sort(reverse=True)  # 쿠폰 배열을 내림차순 정렬
    prices_index = 0  # 각각의 배열에 접근하기 위한 인덱스 지표
    coupons_index = 0
    total_price = 0 # 할인된 전체 가격
    
    # 가장 비싼 가격에 가장 큰 할인을 적용
    while prices_index < len(prices) and coupons_index < len(coupons):
    	total_price += prices[prices_index]*(100-coupons[coupons_index])/100
        prices += 1
        coupons += 1
        
    # 쿠폰을 다 적용시켰는데 상품이 남은 경우 정가를 더하기    
    while prices_index < len(prices):
    	total_price += prices[prices_index]
        prices_index += 1
        
    return total_price
    
print("정답 = 926000 / 현재 풀이 값 = ", get_max_discounted_price([30000, 2000, 1500000], [20, 40]))
print("정답 = 485000 / 현재 풀이 값 = ", get_max_discounted_price([50000, 1500000], [10, 70, 30, 20]))
print("정답 = 1550000 / 현재 풀이 값 = ", get_max_discounted_price([50000, 1500000], []))
print("정답 = 1458000 / 현재 풀이 값 = ", get_max_discounted_price([20000, 100000, 1500000], [10, 10, 10]))

• 3주차 과제(2)
  - 문제 : 문자열이 주어졌을 때, 문자열의 괄호가 바르게 짝지어져 있는지 확인하라
  - 풀이 : stack을 사용해 괄호가 나오면 push, 올바르게 짝지어지면 pop

def is_correct_parenthesis(string):
	stack = []  # 괄호를 저장할 stack
    
    for i in range(len(string)):
    	if string[i] == '(':  # element가 '('일 때
        	stack.append(string[i])  # stack에 해당 문자를 추가
        elif string[i] == ')':  # element가 ')'일 때 pop으로 나오는 문자가 뭔지 확인
        	if len(stack) == 0:  # stack이 비어있을 때 pop을 시킬 수 없으므로
                    return False   # False 리턴
            elif stack.pop() != '(':  # 바로 이전에 저장된 문자가 '('이 아니라면
                    return False   # False 리턴
     
     # '(', ')'을 저장해둔 stack이 올바르게 짝을 이루어 비어있는지 확인
     if len(stack) != 0:  # stack이 비어있지 않다면
     	return False    # False 리턴
     else:   # stack이 비어있다면
     	return True   # True 리턴
        

print("정답 = True / 현재 풀이 값 = ", is_correct_parenthesis("(())"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis(")"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())))"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("())()"))
print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())"))

• 3주차 과제(3)
  - 문제 : 장르 별로 가장 많이 재생된 노래를 넣은 배열의 인덱스 순서대로 반환하라(속한 노래가 많이 재생된 장르 먼저, 장르 내에서도 많이 재생된 노래 먼저, 장르 내 재생횟수가 같은 노래의 경우 고유 번호가 낮은 노래 먼저)
  - 풀이 : 정렬 -> 장르(key)별 재생 수(value) 관리(딕셔너리 이용)
    * 속한 노래가 많이 재생된 장르 : 딕셔너리를 만들어 key로 장르, value로 재생 수를 저장(동일한 장르는 값을 더함)
    * 장르 내 많이 재생된 노래 : 장르를 key로 해 [번호, 재생 횟수]를 따로 저장 
    * 고유 번호가 낮은 노래 

# 예시 -> genre_array = ["classic", "pop", "classic", "classic", "pop"]
# 예시 -> play_array = [500, 600, 150, 800, 2500]

def get_melon_best_album(genre_array, play_array):
    n = len(genre_array)
    genre_total_play_dict = {}  # 각 장르 별 플레이 횟수합을 저장할 딕셔너리 -> 장르의 정렬위해
    # 예시 -> {'classic': 1450, 'pop': 3100}
    genre_index_play_array_dict = {}  # 각 장르 별 노래 번호와 플레이 횟수를 저장할 딕셔너리 -> 장르 내 정렬 위해
    # 예시 -> {'classic': [[0, 500], [2, 150], [3, 800]], 'pop': [[1, 600], [4, 2500]]}
    
    for i in range(n):
    	genre = genre_array[i]
        play = play_array[i]
        if genre not in genre_total_play_dict:  # 해당 장르가 딕셔너리에 없을 경우
            genre_total_play_dict[genre] = play  # key와 value로 장르와 플레이 횟수를 추가
            genre_index_play_array_dict[genre] = [[i, play]]  # key로 장르, value로 노래번호와 플레이 횟수를 추가
        else:  # 해당 장르가 딕셔너리에 이미 있을 경우
            genre_total_play_dict[genre] += play  # 기존 value에 플레이 횟수를 더해 저장
            genre_index_play_array_dict[genre].append([i, play])  # value 배열에 노래번호와 플레이 횟수를 담은 배열을 추가
       
    # 장르 별 순위를 위해 genre_total_play_dict 내림차순 정렬
    # sorted의 결과는 리스트
    # 딕셔너리의 요소를 꺼내는 items() 함수
    # 플레이 횟수(value) 별 정렬이기에 item[1]
    sorted_genre_play_array = sorted(genre_total_play_dict.items(), key=lambda item: item[1], reverse=True)
    # 예시 -> [('pop', 3100), ('classic', 1450)]
    result = []
    
    for genre, _value in sorted_genre_play_array:  # 정렬된 장르별 접근, 예시 genre -> 'pop' && 'classic'
    	index_play_array = genre_index_play_array_dict[genre]  # 해당 장르의 노래번호와 플레이 횟수를 담은 배열
        # 예시 -> 'pop' [[1, 600], [4, 2500]]  &&  'classic' [[0, 500], [2, 150], [3, 800]]
        sorted_by_play_and_index_play_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
        # 예시 -> 'pop' [[4, 2500], [1, 600]]  &&  'classic' [[3, 800], [0, 500], [2, 150]]
        for i in range(len(sorted_by_play_and_index_play_array)):
        	if i > 1:  # 장르별 최대 2곡 까지기 때문에 1보다 크면 break문으로 빠져나옴
                   break
        	result.append(sorted_by_play_and_index_play_array[i][0])  # 노래 번호를 저장해야하기에 [0]에 접근
        
        return result
        
        
print("정답 = [4, 1, 3, 0] / 현재 풀이 값 = ", get_melon_best_album(["classic", "pop", "classic", "classic", "pop"], [500, 600, 150, 800, 2500]))
print("정답 = [0, 6, 5, 2, 4, 1] / 현재 풀이 값 = ", get_melon_best_album(["hiphop", "classic", "pop", "classic", "classic", "pop", "hiphop"], [2000, 500, 600, 150, 800, 2500, 2000]))

 

• 트리 : 계층형 비선형 자료구조
  - 선형 : 자료를 구성하는 데이터가 순차적으로 나열 -> 큐, 스택
  - 비선형 : 데이터가 계층적 혹은 망으로 구성 -> 트리, 그래프
• 트리 용어 정리
  - node : 데이터를 저장하는 기본 요소
  - root node : 트리 맨 위의 노드
  - level : 최상위 노드를 level 0, 하위로 내려갈수록 1씩 증가
  - parent node : 어떤 노드의 상위 레벨에 연결된 노드
  - child node : 어떤 노드의 하위 레벨에 연결된 노드
  - leaf node : child node가 하나도 없는 노드
  - sibling : 동일한 parent node를 가진 노드
  - depth : 트리에서 노드가 가질 수 있는 최대 level
• 이진 트리 : 각 노드가 최대 2개의 자식 노드를 가지는 트리
• 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입한 트리 -> 이 경우만 배열로 표현 가능
  - 트리 구현을 위해 0번째 인덱스는 사용 X -> None으로 배열에 넣고 시작
  - 왼쪽 자식 노드 인덱스 = 현재 노드 인덱스 *2
  - 오른쪽 자식 노드 인덱스 = 현재 노드 인덱스*2 + 1
  - 부모 노드 인덱스 = 현재 노드 인덱스 // 2
  - 트리 높이 = k일 때, level k의 최대노드 개수 = 2^k, (full인)트리의 전체 노드 개수 = 2^(k+1) - 1
  - 따라서 트리 노드 개수가 n일 때 최대 높이는 $$ k=\log_{2}(n+1)-1 $$
  - 이진 트리의 높이는 O(logn)

 

• 힙 : 최대값 or 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
  - Max Heap : 최댓값이 맨 위인 힙 -> 부모 노드의 값이 자식 노드의 값보다 항상 크다
  - Min Heap : 최솟값이 맨 위인 힙 -> 부모 노드의 값이 자식 노드의 값보다 항상 작다
• Max Heap에 원소 추가
  - 추가할 원소를 맨 마지막에 넣는다
  - 부모 노드와 비교해 더 크다면 자리를 바꾼다
  - 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 위의 과정을 반복한다

class MaxHeap:
    def __init__(self):
        self.items = [None]  # 0 인덱스를 사용하지 않기 위해 None으로 넣고 시작

    def insert(self, value):
        self.items.append(value)  # 가장 마지막 위치에 값 추가
        cur_idx = len(self.items) - 1  # 현재 노드의 인덱스
     
        while cur_idx > 1: # cur_idx가 1이면 parent_idx가 0이기에 오류 발생 -> 1은 포함x
            parent_idx = cur_idx // 2  # 현재 노드의 부모 노드 인덱스
            if self.items[cur_idx] > self.items[parent_idx]:  # 현재 노드가 부모 노드보다 값이 크다면
                self.items[cur_idx], self.items[parent_idx] = self.items[parent_idx], self.items[cur_idx]  # 서로 값 변경
                cur_idx = parent_idx  # 현재 노드 인덱스를 부모 노드 인덱스로 업데이트
            else:  # 현재 노드가 부모 노드보다 값이 작거나 같다면
                break  # 힙 조건을 만족하므로 정렬 종료
                
        return self.items


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!
# max 힙의 원소 추가는 O(log n)만큼의 시간 복잡도를 가짐 -> 꼭대기까지 비교이므로

• Max Heap에 원소 제거
  - 최대 힙에서 원소를 삭제하는 방법은 최댓값, 즉 루트 노드 삭제만 가능 -> 애초에 그러기 위해 생긴 자료구조
  - 루트 노드와 맨 끝에 있는 노드를 교체한다
  - 맨 뒤에 있는 노드를 삭제한다(원래 루트였던 것...)
  - 변경된 노드와 자식 노드들을 비교한다 -> 두 자식 중 더 큰 자식 노드와 비교해 자식이 더 크다면 자리를 바꾼다
  - 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 위의 과정을 반복한다
  - 제거한 원래 루트 노드 반환(이건 따로 저장해 놓았어야 함...)

class MaxHeap:
    def __init__(self):
        self.items = [None]  # 0 인덱스를 사용하지 않기 위해 None으로 넣고 시작

    def insert(self, value):
        self.items.append(value)  # 가장 마지막 위치에 값 추가
        cur_idx = len(self.items) - 1  # 현재 노드의 인덱스
     
        while cur_idx > 1: # cur_idx가 1이면 parent_idx가 0이기에 오류 발생 -> 1은 포함x
            parent_idx = cur_idx // 2  # 현재 노드의 부모 노드 인덱스
            if self.items[cur_idx] > self.items[parent_idx]:  # 현재 노드가 부모 노드보다 값이 크다면
                self.items[cur_idx], self.items[parent_idx] = self.items[parent_idx], self.items[cur_idx]  # 서로 값 변경
                cur_idx = parent_idx  # 현재 노드 인덱스를 부모 노드 인덱스로 업데이트
            else:  # 현재 노드가 부모 노드보다 값이 작거나 같다면
                break  # 힙 조건을 만족하므로 정렬 종료
        return self.items

    def delete(self):
        self.items[1], self.items[-1] = self.items[-1], self.items[1]  # 루트 노드와 맨 끝 노드 교체
        pre_max = self.items.pop()  # 맨 뒤 노드 저장 후 삭제
        cur_idx = 1  # 현재 노드를 가리킬 인덱스
        while cur_idx < len(self.items):  # 현재 노드를 가리키는 인덱스가 끝까지 도달하지 않을 동안 반복 -> 도달하면 자식노드 인덱스 구하는 과정에서 오류 발생
            left_child_node = cur_idx*2  # 왼쪽 자식 노드 인덱스
            right_child_node = cur_idx*2 + 1  # 오른쪽 자식 노드 인덱스
            max_idx = cur_idx  # cur_idx, left, right 중 최댓값을 나태는 인덱스

            if left_child_node < len(self.items) and self.items[left_child_node] > self.items[max_idx]:  # cur, left, right 중 left가 가장 큰 경우
                max_idx = left_child_node  # 최댓값 인덱스를 left로

            if right_child_node < len(self.items) and self.items[right_child_node] > self.items[max_idx]:  # cur, left, right 중 right가 가장 큰 경우
                max_idx = right_child_node  # 최댓값 인덱스를 left로

            if max_idx == cur_idx:  # cur, left, right 중 cur이 가장 큰 경우
                break  # 반목문 종료 -> 힙 정렬 끝남

            self.items[cur_idx], self.items[max_idx] = self.items[max_idx], self.items[cur_idx]  # 현재 노드와 최댓값(left와 right 중) 자리 교체
            cur_idx = max_idx  # 현재 위치 인덱스 업데이트
            

        return pre_max


max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 합니다!
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]