코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

알고리즘 패러다임

• 자주나오는 알고리즘 접근법을 묶어서 알고리즘 패러다임이라고 한다.
• 우리는 여러 알고리즘 패러다임으로 같은 문제를 접근할 수도 있다.

왜 공부해야 할까?

새로운 문제를 봤을 때 어떤식으로 풀어 나가야 할지 감이 잡힌다.

다양한 알고리즘 패러다임을 익혀보자. 자연스럽게 효율적으로 문제를 풀어 나가게 된다.

첫번째 패러다임, Brute Force

가능한 모든 경우의 수를 시도하는 순진한 알고리즘 접근법

Brute Force에 대한 평가

• 모든 경우의 수를 확인해서 문제를 푸는 방법이다.
• 모든 경우의 수를 확인하기에 확실한 답을 찾을 수 있다는 보장이 있다. 그러나 똑똑한 방법은 아니다.
• 비효율적이며 인풋이 커질수록 대가가 커진다.

장점은?

• 직관적이고 명확하다.
• 답을 확실하게 찾을 수 있다.

그러나 인풋이 엄청 크다면? 효율적인 알고리즘을 찾아야한다.

왜 이걸 알아야 할까?

문제를 해결하는 첫 단추는 뭘까? 첫 알고리즘의 출발점은 Brute Force이다. 따라서 Brute Force의 이해가 필요하다.

문제1. 카드 뭉치 최대 조합

문제

두 개의 카드 뭉치가 있다. 왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶다. 가장 큰 곱을 구하라.

함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받는다.

left_cards는 왼쪽 카드 뭉치의 숫자들이다.

right_cards는 오른쪽 카드 뭉치의 숫자들이다.

max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴한다.

def max_product(left_cards, right_cards):
    # 코드를 작성하세요.

# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

24
32
28

풀이

Brute Force 를 이용해서 푼다.

모든 숫자를 곱해서 가장 큰 숫자를 반환하도록 구현하였다.

코드

def max_product(left_cards, right_cards):
    result = left_cards[0] * right_cards[0]
    for left_card in left_cards:
        for right_card in right_cards:
            result = max(result, left_card * right_card)
    return result
    
# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

문제2. 가까운 매장 찾기

문제

스타벅스는 줄어든 매출 때문에 지점 하나를 닫아야 하는 위기에 처해있다. 서로 가까이 있는 매장이 있으면 그 중 하나는 없어져도 될거같다. 직선거리가 가장 가까운 두 매장을 찾아라.

다음은 매장 좌표 위치이다.

test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]

튜플은 각 매장의 위치를 x, y좌표로 나타낸 것이다. 0번 매장은 (2, 3)에, 그리고 1번 매장은 (12, 30)위치에 있다.

좌표 리스트를 파라미터로 받고 리스트 안에서 가장 가까운 두 매장을 리턴하는 closet_pair함수를 작성하라. [(x1, y1), (x2, y2)] 형식으로 리턴된다.

두 좌표 사이의 거리를 계산해 주는 distance는 이미 작성되어 있다.

# 제곱근 사용을 위한 sqrt 함수
from math import sqrt

# 두 매장의 직선 거리를 계산해 주는 함수
def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

# 가장 가까운 두 매장을 찾아주는 함수
def closest_pair(coordinates):
    # 여기 코드를 쓰세요

# 테스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

# 콘솔 출력
[(2, 3), (3, 4)]

풀이

Brute Force를 이용하는 문제이다. 매장간의 모든 거리를 계산해서 가장 거리가 작은 두 좌표를 반환하면 된다.

코드

# 제곱근 사용을 위한 sqrt 함수
from math import sqrt

# 두 매장의 직선 거리를 계산해 주는 함수
def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

# 가장 가까운 두 매장을 찾아주는 함수
def closest_pair(coordinates):
    result = [coordinates[0], coordinates[1]]
    for i in range(len(test_coordinates)):
        for j in range(i+1, len(test_coordinates)):
            # 거리가 더 가까우면 result를 수정
            if distance(result[0], result[1]) > distance(coordinates[i], coordinates[j]):
                result = [coordinates[i], coordinates[j]]
    return result

# 테스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

문제3. 강남역 폭우

문제

강남역에 엄청난 폭우가 쏟아진다. 고층 건물이 비에 잠길 정도다.

건물과 건물 사이에 얼마만큼의 빗물이 잠길 수 있는지 알고 싶다. 이를 계산해 주는 함수 trapping_rain을 작성하라.

trapping_rain함수는 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴한다.

예를들어 buildings=[3, 0, 0, 2, 0, 4]일 때 0번 인덱스에는 높이 3의 건물이, 3번 인덱스에 높이 2의 건물이, 5번 인덱스 높이 4의 건물이 있다는 뜻이다. 1, 2, 4번 인덱스에는 건물이 없다. 그러면 아래의 사진과 같이 총 10만큼의 빗물이 담길 수 있다. 따라서 trapping_rain은 10을 리턴한다.

파라미터 buildings로 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]일 때는 trapping_rain 함수는 6을 리턴한다.

def trapping_rain(buildings):
    # 코드를 작성하세요

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

10
6

풀이

• 첫번째와 마지막 인덱스는 빗물이 찰 수 없으므로 순회목록에서 제외하였다.
• 인덱스별로 빗물이 차는 조건은 왼쪽, 오른쪽에 더 높은 건물이 있을 때이다.
• 빗물이 차는 조건 정리
  1. 모든 인덱스를 순회하면서 현재 인덱스를 제외한 왼쪽, 오른쪽에 가장 높은 건물을 구한다.
  2. 두 건물보다 낮은 건물이 현재 건물보다 높은만큼 빗물이 찬다.
• 빗물이 차는 조건을 참고해서 brute force로 풀어보자

코드

def trapping_rain(buildings):
    # 코드를 작성하세요
    total_height = 0
    for i in range(1, len(buildings)-1):
        # 왼쪽에서 가장 높은 건물의 높이, 오른쪽에서 가장 높은 건물의 높이
        left_max, right_max = max(buildings[:i]), max(buildings[i+1:])
        
        # 빗물의 높이
        # 더 낮은 건물의 높이에서 현재 건물의 높이를 빼면 빗물의 높이를 구할 수 있다.
        height = max(min(left_max, right_max) - buildings[i], 0)
        total_height += height
    return total_height

# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

10
6