Sparta_algorithm_course_03) velog

1. 강의 자료

 

https://www.notion.so/teamsparta/3-83a14432311c401598ce3c05e3be25c4

[스파르타코딩클럽] 알고보면 알기쉬운 알고리즘 - 3주차

 

---

2. 강의 듣기 전 계획과 생각

3주차 커리큘럼에는 그동안 자료구조를 공부하면서 정말 많이 겪었었던 스택, 큐, 해쉬(딕셔너리, 힙)에 대한 강의가 있었습니다. 혼자 공부하는 것보다 좋았던 것은 디테일한 의문점까지도 하나하나 짚어주셨던 점이었습니다. (해쉬가 정확히 어떻게 설계되어있는지, 여러 자료구조의 시간복잡도 등등)

 

---

3. 핵심 강의 내용

 

▶ 정렬 : 데이터를 순서대로 나열하는 방법.

 

☞ 버블 정렬 : 첫 번째 자료와 두번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식

 

☞ 선택 정렬 : 최솟값을 찾아 변경하며 정렬하는 방식

for i in range(5 - 1):     # Q. 여기서 왜 5 - 1 일까요?
	for j in range(5 - i): # A. 맨 마지막 비교는 하지 않아도 되기 때문입니다!
		print(i + j)       #    위의 예시에서 4번째 비교를 하면
                           #    [1, 2, 4, 6, 9] 로 변경이 되는데,
                           #    굳이 9와 9를 비교할 필요가 없기 때문이에요! 
                           #    앞에 다 최솟값이 갔으니 알아서 잘 가 있겠지? 하는 느낌입니다.

# 실행결과
# 0
# 1
# 2
# 3
# 4
# 0
# 1
# 2
# 0
# 1
# 0

 

☞ 삽입 정렬 : 전체에서 하나씩 올바른 위치에 삽입하며 정렬하는 방식

for i in range(1, 5):   # Q. 여기서 왜 range(5) 가 아니라 range(1, 5) 일까요?
	for j in range(i):  # A. 삽입 정렬의 0 번째 인덱스는 정렬된 상태라고
		print(i - j)    #    판단할 수 있기 때문에, 첫 번째 인덱스를 비교하지 않고 넘어갑니다.

# 실행결과
# 1
# 2
# 1
# 3
# 2
# 1
# 4
# 3 
# 2
# 1

 

☞ 버블, 선택, 삽입 정렬의 시간 복잡도 : O(N^2)

 

☞ 병합 정렬 : 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 방식

array_a = [1, 2, 3, 5]
array_b = [4, 6, 7, 8]


def merge(array1, array2):
    result = []
    array1_index = 0
    array2_index = 0
    while array1_index < len(array1) and array2_index < len(array2):
        if array1[array1_index] < array2[array2_index]:
            result.append(array1[array1_index])
            array1_index += 1
        else:
            result.append(array2[array2_index])
            array2_index += 1

    if array1_index == len(array1):
        while array2_index < len(array2):
            result.append(array2[array2_index])
            array2_index += 1

    if array2_index == len(array2):
        while array1_index < len(array1):
            result.append(array1[array1_index])
            array1_index += 1

    return result


print(merge(array_a, array_b))

print("정답 = [-7, -1, 5, 6, 9, 10, 11, 40] / 현재 풀이 값 = ", merge([-7, -1, 9, 40], [5, 6, 10, 11]))
print("정답 = [-1, 2, 3, 5, 10, 40, 78, 100] / 현재 풀이 값 = ", merge([-1,2,3,5,40], [10,78,100]))
print("정답 = [-1, -1, 0, 1, 6, 9, 10] / 현재 풀이 값 = ", merge([-1,-1,0], [1, 6, 9, 10]))

 

> 병합 정렬은 분할 정복의 개념을 적용하면 된다.

   MergeSort(0, N) = Merge(MergeSort(0, N/2) + MergeSort(N/2, N))

def merge_sort(array):
    if len(array) <= 1:
        return array
    mid = (0 + len(array)) // 2
    left_array = merge_sort(array[:mid])   				# 왼쪽 부분을 정렬하고
    right_array = merge_sort(array[mid:])  				# 오른쪽 부분을 정렬한 다음에
    return merge(merge_sort(left_array), merge_sort(right_array))         # 합치면서 정렬하면 됩니다!

 

☞병합 정렬의 시간 복잡도 : O(N*logN)

 

 

▶ 스택(Stack) : 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조 (LIFO)

 

> push(data) : 맨 앞에 데이터 넣기

def push(self, value):                 # 현재 [4] 밖에 없다면
    new_head = Node(value)             # [3] 을 만들고!
    new_head.next = self.head          # [3] -> [4] 로 만든다음에
    self.head = new_head               # 현재 head의 값을 [3] 으로 바꿔준다.

> pop() : 맨 앞의 데이터 뽑기

def pop(self):
    if self.is_empty():                  # 만약 비어있다면 에러!
        return "Stack is empty!"
    delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
    self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
    return delete_head                   # 그리고 제거할 node 반환

> peek() : 맨 앞의 데이터 보기

> isEmpty(): 스택이 비었는지 안 비었는지 여부 반환!

 

▶ 큐(Queue) : 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 (FIFO)

 

> enqueue(data) : 맨 뒤에 데이터 추가하기

def enqueue(self, value):              
    new_node = Node(value)             
		if self.is_empty():                # 만약 비어있다면,
        self.head = new_node           # head 에 new_node를
        self.tail = new_node           # tail 에 new_node를 넣어준다.
        return

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

> dequeue() : 맨 앞의 데이터 뽑기

def dequeue(self):
    if self.is_empty():
        return "Queue is empty!"        # 만약 비어있다면 에러!

    delete_head = self.head             # 제거할 node 를 변수에 잡습니다.
    self.head = self.head.next          # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.

    return delete_head.data             # 그리고 제거할 node 반환

> peek() : 맨 앞의 데이터 보기

> isEmpty(): 큐가 비었는지 안 비었는지 여부 반환

 

 

▶ 해쉬 테이블(Hash Table) : 키와 데이터를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용하는 자료구조

 

▶ 해쉬 함수(Hash Function) : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는 함수

 

☞ 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면?

> 체이닝(링크드 리스트를 데이터형식으로 지정)과 개방 주소법(이미 값이 생성되어 있다면 그 다음 주소를 할당) 방법으로 해결할 수 있다.

 

☞ 해쉬 테이블은 시간은 빠르되 공간을 많이 사용하는 자료구조

---

4. 문제풀이

 

▶ 쓱 최대로 할인 적용하기

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


# 나의 풀이
def get_max_discounted_price(prices, coupons):
    discount_price = 0
    prices.sort(reverse=True), coupons.sort(reverse=True)

    if len(prices) > len(coupons):
        price_cnt = 0
        for idx in range(len(coupons)):
            discount_price += prices[idx] * ((100 - coupons[idx])/100)
            price_cnt += 1
        for idx in range(price_cnt, len(prices)):
            print(idx)
            discount_price += prices[idx]
    else:
        for idx in range(len(prices)):
            discount_price += prices[idx] * ((100 - coupons[idx])/100)

    return discount_price


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

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


# 튜터님 풀이
def get_max_discounted_price(prices, coupons):
    coupons.sort(reverse=True)
    prices.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


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

Comment : 문제에 대한 접근 방법은 같았습니다. 하지만 저는 for문을 튜터님께서는 while문을 사용하셨다는 점에서 조금의 차이는 있었습니다.

 

 

▶ 올바른 괄호

from collections import deque
s = "(())()"


# 나의 풀이
def is_correct_parenthesis(string):
    answer = True
    left_bracket_cnt = 0
    right_bracket_cnt = 0

    for i in string:
        if i == "(":
            left_bracket_cnt += 1
        else:
            right_bracket_cnt += 1

    if left_bracket_cnt != right_bracket_cnt:
        answer = False

    return answer


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


# 나의 풀이 (큐)
def is_correct_parenthesis(string):
    answer = True
    bracket_deque = deque()

    for char in string:
        if char == "(":
            bracket_deque.append(char)
        elif char == ")":
            if not bracket_deque:
                answer = False
                return answer
            bracket_deque.popleft()

    if bracket_deque:
        answer = False
    else:
        answer = True

    return answer


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("((())"))


# 튜터님 풀이 (스택)
def is_correct_parenthesis(string):
    stack = []

    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 False
    else:
        return 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("((())"))

Comment : 처음에는 단순한 괄호의 짝맞춤 문제로 알고 갯수를 이용하여 문제를 해결하려고 하였습니다. 이 방법에는 오류가 발생하는 테스트 케이스가 있어서, deque를 이용하여 queue의 형태로 문제를 해결했습니다.

문제 해결의 아이디어는 튜터님과 비슷했습니다. 다만 튜터님은 스택으로 해결하셨습니다. 혹시나 싶어 확인해봤지만, 스택으로 푸는것과 큐로 푸는것의 시간복잡도 차이는 거의 없었습니다. 

 

 

▶ 멜론 베스트 앨범 뽑기

from collections import defaultdict

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


# 나의 풀이
def get_melon_best_album(genre_array, play_array):
    answer = []
    genres_plays = defaultdict(int)
    genres_songs = defaultdict(list)

    idx = 0
    for genre, play in zip(genre_array, play_array):
        genres_plays[genre] += play
        genres_songs[genre].append((idx, play))
        idx += 1

    sorted_genre_play = sorted(genres_plays.items(), key=lambda x: x[1], reverse=True)

    for genre in sorted_genre_play:
        sorted_genre = sorted(genres_songs[genre[0]], key=lambda x: x[1], reverse=True)
        answer.append(sorted_genre[0][0])
        if len(sorted_genre) > 1:
            answer.append(sorted_genre[1][0])

    return answer


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


# 튜터님 풀이
def get_melon_best_album(genre_array, play_array):
    n = len(genre_array)
    genre_total_play_dict = {}
    genre_index_play_array_dict = {}
    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
            genre_index_play_array_dict[genre] = [[i, play]]
        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 item: item[1], reverse=True)
    result = []
    for genre, _value in sorted_genre_play_array:
        index_play_array = genre_index_play_array_dict[genre]
        sorted_by_play_and_index_play_index_array = sorted(index_play_array, key=lambda item: item[1], reverse=True)
        for i in range(len(sorted_by_play_and_index_play_index_array)):
            if i > 1:
                break
            result.append(sorted_by_play_and_index_play_index_array[i][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]))

Comment : 처음에는 튜터님과 유사한 방법으로 풀이가 나왔었는데, 어떻게 조금이라도 코드를 줄일 수 있을지 고민하다가 defaultdict 이라는 라이브러리를 알게 되었습니다. defaultdict은 key값이 존재하지 않는다면 자동으로 default값을 할당해주는 dict의 서브 클래스입니다. 때문에 굳이 key값이 이미 존재하는지 확인하지 않더라도 추가가 가능해집니다.

 

https://dongdongfather.tistory.com/69

[파이썬 기초] 유사 딕셔너리 defaultdict() 활용법

 

---

5. 3주차 강의를 통해 새롭게 알게된 점

 

해쉬, 스택, 큐의 구조에 대해서 조금 더 심도있게 이해할 수 있었고, 문제를 해결하면서 defaultdict과 sorted의 기능에 대해 조금 공부할 수 있었습니다.