브루트포스(Brute-force search) : 백준 14719 [빗물] & 파이썬

브루트포스 알고리즘을 공부하면서, 백준 문제에도 적용을 해보았습니다! 👀 반복 숙달을 통해 더욱 익숙해지자! 🏆

참고로 해당 문제는 leet_code에서도 찾을 수 있었습니다. 해당 문제도 업데이트해보겠습니다. 주소는 제일 아래 reference에 추가하겠습니다.

🔍 Brute-force search

• 그대로 해석하면 "무차별 대입 검색"
• 의미 그대로, 무차별적으로 가능한 모든 경우의 수를 시도해 보는 알고리즘
• 가장 순진한 알고리즘 접근법
• 예를 들어, 비밀번호 4자리 자물쇠가 있다고 하면, 0000부터 9999까지 전체를 다 확인하는 것!

이미지 출처는 아래에

이미지는 여기에서 가지고 왔습니다.

👍 장점

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

😵‍💫  단점

• 모든 경우를 보기 때문에 비효율적임 ➡️ 인풋이 커질수록 비효율의 댓가가 커진다!!!! 🔥🔥🔥

➡️ 비효율적인데 왜 알아야하지❓ 효율적인 알고리즘을 찾기 위한 고민의 출발점이 바로 Brute Force! 그래서 이해해야 합니다!👀

---

백준 14719 [빗물]

 

📎 Problem

https://www.acmicpc.net/problem/14719

14719번: 빗물

---

📎 Submission Code

H, W = map(int, input().split())
buildings = list(map(int, input().split()))

def trapping_rain(buildings):
    # 총 담기는 빗물의 양을 변수에 저장
    total_height = 0

    # 리스트의 각 인덱스을 돌면서 해당 칸에 담기는 빗물의 양을 구한다
    # 0번 인덱스와 제일 마지막 인덱스는 빼고 반복문을 돈다
    for i in range(1, len(buildings) - 1):
        # 물이 안차기때문에 현재 인덱스를 기준으로 양쪽에 가장 높은 건물의 위치를 구한다
        max_left = max(buildings[:i]) #  현재 인덱스의 왼쪽에서 가장 높은 건물의 높이
        max_right = max(buildings[i:]) # 현재 인덱스의 오른쪽에서 가장 높은 건물의 높이

        # 현재 인덱스에 빗물이 담길 수 있는 높이 : 그 중 더 낮은 건물의 높이
        upper_bound = min(max_left, max_right)

        # 현재 인덱스에 담기는 빗물의 양을 계산
        # 상한 높이에서 현재 인덱스에 있는 건물의 높이를 빼서 물의 높이를 구하고 total에 더해준다
        # 만약 upper_bound가 현재 인덱스 건물보다 높지 않다면, 현재 인덱스에 담기는 빗물은 0
        total_height += max(0, upper_bound - buildings[i])

    return total_height

print(trapping_rain(buildings))

---

📎 Reference

• leet_code : 11. Container With Most Water
• 코드잇
• 이미지 출처 블로그