백준 2789번 : 블랙잭

해당 문제는 Brute Force Algorithm을 활용하는 것으로, 보안쪽 사람들이라면 Brute Force라는 용어가 익숙할 것으로 보인다. 나 또한 플젝을 하며 Brute Force 공격에 대해 얕게 공부하였는데 여기서는 알고리즘으로써 사용된다.

 

Brute Force Algorithm은 정답을 찾을 때까지 모든 경우의 수를 다 훑어보는 알고리즘으로 순간적으로 복잡도가 커지는 특성이 있다보니 대규모 데이터를 다루는 상황이라면 해당 알고리즘으로 인하여 과부하가 걸릴 수 있을 것이다.

문제

풀이

n, m = map(int, input().split())
cards = list(map(int, input().split()))
tot = 0

for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      sum = cards[i] + cards[j] + cards[k]
      if sum >= tot and sum <= m:
        tot = sum
    
print(tot)

 

이문제는 결국 모든 경우의 수를 다 훑어보며 주어진 m과 가장 가까운 합을 찾는 것이 목표이다

 

나는 이 문제를 i를 기준으로 다음 카드, 그 다음 카드를 훑어볼 수 있도록 하여 3중 반복문으로 훑어보았다.

시간복잡도가 O(N^3)으로 매우 큰 복잡도를 가지고 있으나 이를 어떻게 줄일 수 있을지 마땅한 방안이 생각나지 않았다.

 

숏코드 분석

from itertools import*
n,m,*c=map(int,open(0).read().split())
print(max(s*(s<=m)for s in map(sum,combinations(c,3))))

 

itertools를 사용하지 않은 숏코드를 보고싶었지만 대부분 itertools를 사용한 코드들이 숏코드 상위 랭킹이었다..

어쩔 수 없이 위의 코드만 분석해본다.

 

• open(0)은 stdin과 같은 역할
• asterisk를 이용해 남은 요소들을 unpacking
• itertools에 있는 combinations는 확률과 통계의 "조합"을 의미하며 c에 있는 요소들을 3개씩 조합하여 경우의수를 반환해주는 형태이다.
  • combinations의 원리는 아래와 같다.

def combinations(iterable, r):
    # combinations('ABCD', 2) → AB AC AD BC BD CD
    # combinations(range(4), 3) → 012 013 023 123

    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = list(range(r))

    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)

• combinations를 통해 뽑은 3개의 카드를 summation하여 입력받은 m과 비교하였을 때 max값을 추출
  • 이 과정에서 max값을 어떻게 뽑는가?
    • s*(s<=m)for s in map(sum,combinations(cards,3))

      해당 코드의 출력 값은 generator로 iterable obejct이다보니 max 함수를 이용해 해당 object 내에 있는 원소들을 비교해 max값을 추출

---

Brute Force Algorithm 개념 참고

https://www.geeksforgeeks.org/brute-force-approach-and-its-pros-and-cons/

Brute Force Approach and its pros and cons - GeeksforGeeks

 

문제

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

 

itertools.combinations

https://docs.python.org/3/library/itertools.html#itertools.combinations

itertools — Functions creating iterators for efficient looping