실습 설명

def max_product(card_lists):
    # 여기에 코드를 작성하세요


# 테스트 코드
test_cards = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards))

여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 1, 2, 3을 들고 있고, 두 번째 플레이어는 4, 6, 1을 들고 있고, 세 번째 플레이어는 8, 2, 4를 들고 있는 거죠.

함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. max_product를 Greedy Algorithm 방식으로 구현해 보세요.

실습 결과

def max_product(card_lists):
    # 누적된 곱을 저장하는 변수
    product = 1

    # 반복문을 돌면서 카드 뭉치를 하나씩 본다
    for card_list in card_lists:
        # product에 각 뭉치의 최댓값을 곱해 준다
        product *= max(card_list)

    return product


# 테스트 코드
test_cards1 = [[1, 6, 5], [4, 2, 3]]
print(max_product(test_cards1))

test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], [7, 7, 4]]
print(max_product(test_cards2))

test_cards3 = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]]
print(max_product(test_cards3))

test_cards4 = [[5, 5, 5], [4, 3, 5], [1, 1, 1], [9, 8, 3], [2, 8, 4], [5, 7, 4]]
print(max_product(test_cards4))

24
244944
10800
12600

실습 설명

최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현해 보겠습니다.

우리가 작성할 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다.

예를 들어 1170원을 거슬러 주기 위해서는 500원 2개, 100원 1개, 50원 1개, 10원 2개를 줄 수 있기 때문에 6을 리턴하면 되겠죠?

동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합시다.

실습 결과

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0

    # coin_list의 값들을 큰 순서대로 본다
    for coin in sorted(coin_list, reverse=True):
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
        count += (value // coin)

        # 잔액을 계산한다
        value %= coin

    return count

# 테스트 코드
default_coin_list = [100, 500, 10, 50]
print(min_coin_count(1440, default_coin_list))
print(min_coin_count(1700, default_coin_list))
print(min_coin_count(23520, default_coin_list))
print(min_coin_count(32590, default_coin_list))

10
5
49
70

오답 

• 리스트의 정렬

coin_list.sort(reverse=True) #리스트가 내림차순으로 정렬
coin_list.sort()             #리스트가 오름차순으로 정렬

• 리스트 정렬+반복문 = 한 번에 가능

for coin in sorted(coin_list, reverse=True):

1. 수신(예금)이 없는 비은행 금융사들은 막대한 자금을 어디서 구할까?

2. 흔히 말하는 여전사(여신전문 금융회사)는 돈을 빌려주고 이자를 받는 회사라고만 알고 있었음

3. 근데 이때 사람들에게 빌려주는 돈을 어디서 구해오는가?

4. 이건 고민해본적이 없던 사실임

5. 알고보니 회사채나 기업어음으로 대출을 받아서 자금을 조달하는 것이라고 함

6. [여전사의 사업구조]
도매 : 회사 신용을 보증서로 은행에서 돈을 꿔옴(회사채)
소매 : 일반 고객들에게 돈을 빌려주고 이자를 받음(캐피탈,카드론,자동차할부)

7. 수익이 나려면 (소매로 얻는 이자) > (회사채로 내는 이자) 여야 함

8. 인터넷 쇼핑몰을 생각해보면, (동대문에서 옷을
사오는 가격) < (일반 소비자에게 판매하는 비용)보다 싸야하는 것처럼 당연한 이치임

9. 하지만 래고랜드 사태로 인해 지자체에서 발행한 채권의
안정성이 의심을 받게 되었고 -> 이는 회사채까지 영향을 끼치게 되었다고 함

10. 그래서 회사채를 통해 저렴하게 자금 조달하던 여전사들에게 빨간불이 켜지기 되었다고 함

대리님 추천으로 메르의 블로그 포스팅 읽다가 너무 길어서 흥미로웠던 내용만 요약함

(출처 : 메르의 블로그)

def max_profit(price_list, count):
    # 개수별로 가능한 최대 수익을 저장하는 리스트
    # 새꼼달꼼 0개면 0원
    profit_table = [0]

    # 개수 1부터 count까지 계산하기 위해 반복문
    for i in range(1, count + 1):
        # profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
        # 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
        # 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정   
        if i < len(price_list):
            profit = price_list[i]
        else:
            profit = 0

        # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 찾는다
        for j in range(1, i // 2 + 1):
            profit = max(profit, profit_table[j] + profit_table[i - j])

        profit_table.append(profit)

    return profit_table[count]


# 테스트 코드
print(max_profit([0, 200, 600, 900, 1200, 2000], 5))
print(max_profit([0, 300, 600, 700, 1100, 1400], 8))
print(max_profit([0, 100, 200, 400, 600, 900, 1200, 1300, 1500, 1800], 9))

2000
2400
1800

오답노트

• profit_table을 만드는 것이 포인트이다

실습 설명

솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요...

가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다.

• price_list: 개수별 가격이 정리되어 있는 리스트
• count: 판매할 새꼼달꼼 개수
• cache: 개수별 최대 수익이 저장되어 있는 사전

예를 들어 price_list가 [100, 400, 800, 900, 1000]이라면,

1. 새꼼달꼼 1개에 100원
2. 새꼼달꼼 2개에 400원
3. 새꼼달꼼 3개에 800원
4. 새꼼달꼼 4개에 900원
5. 새꼼달꼼 5개에 1000원

이렇게 가격이 책정된 건데요. 만약 오늘 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼마를 벌 수 있을까요?

한 친구에게 3개 팔고 다른 친구에게 2개를 팔면, 800+400을 해서 총 1200원의 수익을 낼 수 있겠죠.

실습 결과

def max_profit_memo(price_list, count, cache):
    # Base Case: 0개 혹은 1개면 부분 문제로 나눌 필요가 없기 때문에 가격을 바로 리턴한다
    if count < 2:
        cache[count] = price_list[count]
        return cache[count]

    # 이미 계산한 값이면 cache에 저장된 값을 리턴한다
    if count in cache:
        return cache[count]

    # profit은 count개를 팔아서 가능한 최대 수익을 저장하는 변수
    # 팔려고 하는 총개수에 대한 가격이 price_list에 없으면 일단 0으로 설정
    # 팔려고 하는 총개수에 대한 가격이 price_list에 있으면 일단 그 가격으로 설정
    if count < len(price_list):
        profit = price_list[count]
    else:
        profit = 0

    # count개를 팔 수 있는 조합들을 비교해서, 가능한 최대 수익을 profit에 저장
    for i in range(1, count // 2 + 1):
        profit = max(profit, max_profit_memo(price_list, i, cache) 
                 + max_profit_memo(price_list, count - i, cache))

    # 계산된 최대 수익을 cache에 저장
    cache[count] = profit

    return profit


def max_profit(price_list, count):
    max_profit_cache = {}

    return max_profit_memo(price_list, count, max_profit_cache)


# 테스트 코드
print(max_profit([0, 100, 400, 800, 900, 1000], 5))
print(max_profit([0, 100, 400, 800, 900, 1000], 10))
print(max_profit([0, 100, 400, 800, 900, 1000, 1400, 1600, 2100, 2200], 9))

1200
2500
2400

실습 설명

 n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 됩니다.

공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요.

실습 결과

def fib_optimized(n):
    current = 1
    previous = 0

    # 반복적으로 위 변수들을 업데이트한다. 
    for i in range(1, n):
        print("%i : cur[%d], pre[%d]" %(i,current, previous))
        current, previous = current + previous, current

    # n번재 피보나치 수를 리턴한다. 
    return current
    
# 테스트 코드
print(fib_optimized(16))
print(fib_optimized(53))
print(fib_optimized(213))

1 : cur[1], pre[0]
2 : cur[1], pre[1]
3 : cur[2], pre[1]
4 : cur[3], pre[2]
5 : cur[5], pre[3]
6 : cur[8], pre[5]
7 : cur[13], pre[8]
8 : cur[21], pre[13]
9 : cur[34], pre[21]
10 : cur[55], pre[34]
11 : cur[89], pre[55]
12 : cur[144], pre[89]
13 : cur[233], pre[144]
14 : cur[377], pre[233]
15 : cur[610], pre[377]

987
53316291173
146178119651438213260386312206974243796773058

SQL처음 공부할 때는 알았으려나...?

그동안 실무를 하면서 너무 UNION ALL 에 익숙해져서 둘의 차이를 잊고 있었다!

UNION (= UNION DISTINCT)

(SELECT cust_no, lst_lgin_dtm FROM A) 

UNION 

(SELECT cust_no, lst_lgin_dtm FROM B)

CUST_NO    LST_LGIN_DTM
-------------------------------
1111       2022/10/31 10:21:59
1111	   2022/11/21 17:49:34
1111	   2023/04/02 23:51:01
1111	   2023/04/04 09:51:01

두 테이블에서 같은 데이터 row가 2건 이상 나오면 해당 데이터는 1건만 남기고 나머지는 지운다.

UNION ALL

(SELECT cust_no, lst_lgin_dtm FROM A) 

UNION ALL

(SELECT cust_no, lst_lgin_dtm FROM B)

CUST_NO    LST_LGIN_DTM
-------------------------------
1111       2022/10/31 10:21:59
1111	   2022/11/21 17:49:34
1111	   2023/04/02 23:51:01
1111	   2023/04/02 23:51:01
1111	   2023/04/02 23:51:01
1111	   2023/04/04 09:51:01

두 테이블에서 같은 데이터 row가 2건 이상 나오면 한 건도 빠짐없이 모두 조회된다.

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성해 보세요.

fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다!

실습 결과

def fib_tab(n):
    # 이미 계산된 fib 값들을 담는 리스트
    fib_table = [0, 1, 1]
    
    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n+1):
        #print("[%d] fib_table : %s" %(i,fib_table))
        fib_table.append(fib_table[i-1]+fib_table[i-2])
        
    return fib_table[n]

# 테스트 코드
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

#[3] fib_table : [0, 1, 1]
#[4] fib_table : [0, 1, 1, 2]
#[5] fib_table : [0, 1, 1, 2, 3]
#[6] fib_table : [0, 1, 1, 2, 3, 5]
#[7] fib_table : [0, 1, 1, 2, 3, 5, 8]
#[8] fib_table : [0, 1, 1, 2, 3, 5, 8, 13]
#[9] fib_table : [0, 1, 1, 2, 3, 5, 8, 13, 21]
#[10] fib_table : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
55
225851433717
1725375039079340637797070384

포인트

• Dynamic Programming : 중복된 과정은 1번만 진행하도록 하는 알고리즘 패러다임
• memorization : 재귀
• tabulation : 단순 반복문

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요.

fib_memo는 꼭 memoization 방식으로 구현하셔야 합니다!

실습 결과

# 캐시에 담긴 n번째 피보나치 수를 반환
def fib_memo(n, cache):
    #base case
    if n <= 2:
        return 1
    
    # 캐시에 저장된 피보나치 수가 있으면?
    if n in cache:
        return cache[n]
    # 캐시에 없으면, 캐시에 저장
    else:
        cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache) 
        return cache[n]
    

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)


# 테스트 코드
print(fib(10))
print(fib(50))
print(fib(100))

55
12586269025
354224848179261915075

실습 설명

이전 과제에서 quicksort 함수를 작성했습니다.

# 테스트 코드
test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6]
quicksort(test_list, 0, len(test_list) - 1)
print(test_list)

그런데 quicksort 함수에 필수로 start와 end 파라미터를 넘겨줘야 한다는 게 조금 거슬리네요. 테스트를 할 때 만큼은 아래처럼 깔끔하게 작성하고 싶은데요.

# 테스트 코드
test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6]
quicksort(test_list) # start, end 파라미터 없이 호출
print(test_list)

어떻게 할 수 있을까요?

실습 결과

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    temp = my_list[index1]
    my_list[index1] = my_list[index2]
    my_list[index2] = temp

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i = start
    b = start
    p = end

    # 범위안의 모든 값들을 볼 때까지 반복문을 돌린다
    while i < p:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    # b와 기준점인 p 인덱스에 있는 값들을 바꿔준다
    swap_elements(my_list, b, p)
    p = b

    #pivot의 최종 인덱스를 리턴해 준다
    return p

# 퀵 정렬
def quicksort(my_list, start=0, end=None):
    if end == None:
        end = len(my_list) - 1

    # base case
    if end - start < 1:
        return

    # my_list를 두 부분으로 나누어주고,
    # partition 이후 pivot의 인덱스를 리턴받는다
    pivot = partition(my_list, start, end)

    # pivot의 왼쪽 부분 정렬
    quicksort(my_list, start, pivot - 1)

    # pivot의 오른쪽 부분 정렬
    quicksort(my_list, pivot + 1, end)

# 테스트 1
list1 = [1, 3, 5, 7, 9, 11, 13, 11]
quicksort(list1) # start, end 파라미터 없이 호출
print(list1)

# 테스트 2
list2 = [28, 13, 9, 30, 1, 48, 5, 7, 15]
quicksort(list2) # start, end 파라미터 없이 호출
print(list2)

# 테스트 3
list3 = [2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]
quicksort(list3) # start, end 파라미터 없이 호출
print(list3)

[1, 3, 5, 7, 9, 11, 11, 13]
[1, 5, 7, 9, 13, 15, 28, 30, 48]
[1, 1, 2, 2, 4, 4, 4, 5, 6, 6, 7, 7, 10, 11, 13, 15]

힌트 1

파이썬 함수의 옵셔널 파라미터(Optional Parameter) 기억하시나요?

def func1(p1, p2, p3=0, p4=None):
    print(p1, p2, p3, p4)

func1(2, 3, 5, 7)
func1(11, 13)     # p3와 p4을 따로 설정하지 않았으니 기본값인 0과 None이 지정됨

2 3 5 7
11 13 0 None