[알고리즘] 문제4 - Brute Force

코드잇 강의를 듣고 정리한 알고리즘 문제들 입니다.

 

Brute Force : 무차별 대입으로 가능한 모든 경우에 대해 모두 탐색하여 조건에 충족되는 결과만 가져옴

장점 : 직관적이고 명확, 답을 확실하게 찾을 수 있음

단점 : 비효율적임

 

그럼에도 불구하고 알아야하는 이유 : 효율적인 알고리즘을 찾는 가장 기본적인 접근 방법이기 때문

 

---

 

 1. 카드 뭉치 최대 조합 구하기

 

 조건 

-함수명 : max_product

-매개변수명 : 카드 뭉치1(left_cards), 카드 뭉치2(right_cards)

-카드 뭉치1과 카드 뭉치2에서 카드를 하나 뽑아서 곱했을 때 그 값이 최대가 되는 값을 반환

---

풀이

# 시간 복잡도 : O(mn) (m은 left_cards의 갯수, n은 right_cards의 갯수)

def max_product(left_cards, right_cards):

    card_max = 0

    for i in range(len(left_cards)):
        for j in range(len(right_cards)):
            temp = left_cards[i] * right_cards[j]
            if card_max < temp:
                card_max = temp

    return card_max


# 테스트
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. 가까운 매장 찾기 

- 줄어든 매출 때문에 서로 가까이 붙어 있는 매장 중 하나를 없애려고 할 때,

직선 거리가 가장 가까운 두 매장을 반환하기

 

 조건 

1. 두 매장의 직선 거리를 계산해 주는 함수

-함수명 : distance

-매개변수명 : 가게1 위치(store1), 가게2 위치(store2)

-가게들의 위치는 튜플 형태로 받음

-두 지점의 직선거리 반환

 

2. 가장 가까운 두 매장을 찾는 함수

-함수명 : cloest_pair

-매개변수명 : 가게들의 좌표가 담긴 리스트(coordinates)

-가장 가까운 두 매장의 좌표를 리스트 형태로 반환

 

3. 두 매장 사이의 거리 

- 좌표평면 위의 두점 사이의 거리 공식 이용

sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

- 제곱근 사용을 위해 sqrt 함수 추가

from math import sqrt

---

풀이

# 시간 복잡도 : O(n^2)

# 제곱근 사용을 위한 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):
    closer_list = [coordinates[0], coordinates[1]]
    temp = 0

    for i in range(len(coordinates)-1):
        for j in range(i+1, len(coordinates)):
            store1, store2 = coordinates[i], coordinates[j]

            if distance(closer_list[0], closer_list[1]) > distance(store1, store2):
                closer_list = [store1, store2]

    return closer_list


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

 

 

---

 

 3. 강남역 폭우 

- 강남역에 엄청난 폭우가 쏟아져 고층 건물이 비에 잠긴다고 할 때, 

건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 구하기

 

 조건 

-함수명 : trapping_rain

-매개변수명 : 건물들의 높이가 담긴 리스트(buildings)

-담기는 빗물의 총량을 반환

 

 예시 

1. 빗물의 총량(파랑색 부분) : 10

 

2. 빗물의 총량(파랑색 부분) : 6

---

풀이

# 시간 복잡도 : O(n^2)

def trapping_rain(buildings):
    # 코드를 작성하세요
    
    # 빗물의 총량을 담을 변수
    rain = 0
    
    for i in range(1, len(buildings)-1):
    	# 현재 인덱스의 왼쪽에서 가장 높은 건물의 높이를 구한다.(현재 인덱스 포함 X)
        max_left = max(buildings[:i])
        
        # 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이를 구한다.(현재 인덱스 포함 O)
        max_right = max(buildings[i:])

	 	# 둘 중 더 낮은 건물의 높이를 구한다.
        max_high = min(max_left, max_right)

		# 그 높이에서 현재 인덱스에 있는 건물의 높이를 뺀다.
        # 만약 max_high보다 현재 인덱스가 크거나 같으면 빗물이 담기지 않으므로 0이 된다.
        rain += max(0, max_high-buildings[i])

    return rain


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