[파이썬] 알고리즘 패러다임 : Brute Force

2023.02.24 코드잇 학습내용

 

🔎 알고리즘 패러다임(algorithm paradigm)

문제를 해결하는 데에는 여러 가지 방식이 있음. 여러 문제를 해결하다 보면 해결 과정이 비슷한 경우가 있는데, 이러한 것을 알고리즘 패러다임이라고 함. 즉, 어떠한 문제를 풀기 위한 일반적인 접근법 혹은 방법론. 몇 가지 자주 사용되는 알고리즘 패러다임이 있으며, 각 알고리즘은 문제를 풀기 위한 자신만의 기술과 도구를 가지고 있음. 또한, 하나의 문제를 푸는 방법은 다양하기 때문에 여러 알고리즘 패러다임으로 한 문제에 접근할 수도 있음.

 

가장 자주 사용되는 알고리즘 패러다임
1. Greedy Algorithms
2. Divide and Conquer
3. Dynamic Programming
4. Backtracking
5. Branch and Bound
6. Randomized Algorithms

 

🔎 Brute Force

Brute Force 알고리즘은 문제를 해결하는 가장 간단한 접근 방법으로 최적화 혹은 휴리스틱 기술 없이 모든 경우의 수를 확인하여 문제를 해결하는 방법. 이 알고리즘은 답이 나올 때까지 가능한 해결책을 하나씩 모두 시도함. 입력 데이터의 모든 가능한 조합 또는 순열을 반복하고, 각각의 데이터가 문제 제약 조건을 충족하는지 확인함으로써 수행

 

이 알고리즘은 답을 확실하게 찾을 수 있고, 구현하기가 간단하지만, 인풋 크기가 큰 경우 매우 느리고 비효율적일 수 있음. 따라서 이 방법은 다른 해결 가능한 알고리즘 솔루션이 없거나, 문제의 크기가 Brute Force 알고리즘을 사용하여도 상관없을 만큼 작을 때 사용.

 

그러나 Brute Force 알고리즘은 보다 효율적이고 정교한 알고리즘 설계의 기준 또는 시작점이 되므로 이 알고리즘에 대한 이해가 필요함

 

🔎 Brute Force 연습문제

⚙ 두 개의 리스트에서 두 수의 곱이 가장 큰 값을 출력하는 문제

▼ Brute Force 알고리즘 패러다임 방식로 푼 코드(모범답안) ▼

① 중첩 for 반복문으로 가능한 모든 두 수의 곱의 경우의 수를 도출

② 현재까지의 최댓값을 담기위해 자기 자신을 변수로 가지는 변수(max_product)를 사용하여 현재까지의 최댓값과 for문에서의 두 수의 곱을 비교 → 두 수의 곱이 현재까지의 최댓값보다 크면 max_product로 대입

 

작동 steps
left_cards = [1, 6, 5], right_cards = [4, 2, 3]

max_product = left_cards[0] * right_cards[0] → 4
max_product = max(max_product, 1 * 4) = max(4, 4) → 4
max_product = max(max_product, 1 * 2) = max(4, 2) → 4
max_product = max(max_product, 1 * 3) = max(4, 3) → 4
max_product = max(max_product, 6 * 4) = max(4, 24) → 24
max_product = max(max_product, 6 * 2) = max(24, 12) → 24
max_product = max(max_product, 6 * 3) = max(24, 18) → 24
max_product = max(max_product, 5 * 4) = max(24, 20) → 24
max_product = max(max_product, 5 * 2) = max(24, 10) → 24
max_product = max(max_product, 5 * 3) = max(24, 15) → 24

return max_product → 24

 

※ 시간 복잡도

len(left_cards)를 n, len(right_cards)를 m이라고 했을 때, 함수 max_product의 시간 복잡도는 O(mn)

→ left_cards를 도는 for 반복문 n번과 right_cards를 도는 for 반복문 m이 중첩되어 있기 때문

 

▼ 내가 작성한 코드 ▼

공통점 : for 반목문 중첩 사용하여 왼쪽 카드와 오른쪽 카드의 곱 모든 경우의 수를 뽑음

차이점 : ① 두 수의 곱을 값으로 가지는 빈 리스트(multi)를 만들고, 반복문에서 빈 리스트에 두 수의 곱 추가

② 모든 경우의 수의 대한 곱(값)을 가지는 multi 리스트의 요소 중 최댓값 return

 

⚙ 직선 거리가 가장 가까운 두 매장 찾기

▼ 모범답안 ▼

① 가장 가까운 두 매장을 변수로 사용(pair)하여 더 가까운 두 매장을 찾으면 변수(pair)를 업데이트하는 방법으로 작성

② 같은 위치, 검사를 진행했던 튜플 쌍은 경우의 수에서 제외하기 위해 i와 j의 범위 지정 → 인덱스 활용

 

▼ 내가 작성한 코드 ▼

공통점 : for 반복문 2번 사용하여 모든 경우의 수 계산

차이점 : ① 두 매장이 아닌 최소 거리(min_distance)를 변수로 사용

② 인덱스 대신 조건문 store1 < store2을 사용하여 같은 위치, 이전에 계산했던 위치는 반복 계산하지 않도록 설정

     → 잘못된 코드로 수정 필요 (모범 답안과 같이 for문에서 반복하는 대상을 튜플 자체가 아닌 인덱스로 변경해야 함)

③ 그 후 최소 거리인 가게들의 위치 값을 추출하기 위해 조건문 사용. store1과 store2 사이의 거리가 최소 거리일 때 closest_pair에 store1, store2 저장 후 반복문이 끝나면 closest_pair 리턴

튜플 크기 비교
두 튜플의 첫 번째 요소부터 시작하여 요소별로 비교
먼저 두 요소가 동일한 유형인지 확인
그 다음 값을 기준으로 비교 → 값을 기준으로 비교할 땐 첫 번째 요소만 비교하고 나머지 요소는 무시

store1 < store2 직접 대입해 보면 의도한 대로 모든 경우의 수를 따지지 않음. (12,30) (12,10)과의 비교가 빠짐.
→ 잘못된 코드. 따라서 모법답안과 같이 인덱스를 사용한 코드로 변경해야 함
(2, 3) (12, 30)
(2, 3) (40, 50)
(2, 3) (5, 1)
(2, 3) (12, 10)
(2, 3) (3, 4)
(12, 30) (2, 3)
(12, 30) (40, 50)
(12, 30) (5, 1)
(12, 30) (12, 10)
(12, 30) (3, 4)
(40, 50) (2, 3)
(40, 50) (12, 30)
(40, 50) (5, 1)
(40, 50) (12, 10)
(40, 50) (3, 4)
(5, 1) (2, 3)
(5, 1) (12, 30)
(5, 1) (40, 50)
(5, 1) (12, 10)
(5, 1) (3, 4)
(12, 10) (2, 3)
(12, 10) (12, 30)
(12, 10) (40, 50) 
(12, 10) (5, 1)
(12, 10) (3, 4)
(3, 4) (2, 3)
(3, 4) (12, 30)
(3, 4) (40, 50)
(3, 4) (5, 1)
(3, 4) (12, 10)

참고링크 : https://www.delftstack.com/ko/howto/python/python-tuple-comparison/

 

 

위의 두 문제를 풀고 느낀 점은 Brute Force 알고리즘에서는 구하고자 하는 것을 변수로 설정하고, 원하는 값을 찾으면 업데이트하여 return 하는 방식으로 진행

 

⚙ 건물과 건물 사이에 얼마만큼의 빗물이 담길 수 있는지 계산

▼ 모범답안 ▼

① 하나의 인덱스에 대하여 해당 인덱스가 가질 수 있는 빗물의 양을 구함 

② for문 사용하여 각각의 인덱스에 대한 빗물의 양을 합함

③ 이 때 max 함수를 사용하여 자신보다 왼쪽 혹은 오른쪽 기둥 높이가 낮은 경우에는 합하지 않도록 설계

 

▼ 내가 작성한 코드 ▼

① 규칙은 어느 정도 파악했는데 어떻게 코드로 구현해야 할지를 몰라서 힌트를 참고했음 (현재 인덱스에서 받을 수 있는 빗물의 양 구하기까지)

② for 반복문과 빗물의 총량 구하는 코드는 직접 작성 → 현재 인덱스가 받을 수 있는 빗물의 양을 변수에 대입하고, max 대신 if 조건문을 사용하여 작성

③ 느낀점 : 문제를 작게 쪼개서 생각하고 규칙 생각하기. 생각나는 규칙은 정리해서 코드로 직접 구현해 보기.