[브론즈2]백준 2798번(블랙잭) - 문제 완벽 풀이(python)

 

문제 해석

블랙잭 게임인데 M(주어진 수)에 3장을 뽑아서 그들을 더한 수가 M과 같거나 작은 수로 만들어 그 값을 산출하는 것과 같다. 

 

그렇게 하기 위해서 다양한 것을 생각할 수 있다.  

 

문제 풀이 전략

1. 브루트 포스 (Brute Force) 접근법

가장 직관적인 방법은 가능한 모든 카드 3장의 조합을 생성하여, 각 조합의 합이 M 이하인지 확인한 후, 그 중 최댓값을 찾는 것이 있다. 

 

이것의 장점은 구현이 간단하고 문제의 조건(카드의 수 n이 상대적으로 작을 때)에서는 충분히 빠르게 동작한다는 점에 있다.

 

하지만 이것의 단점은 전체 조합의 수는 nC3으로 n이 커지면 시간 복잡도가 급격하게 증가한다는 것이다.

 

에를 들어 n이 100이라면 약 161,700가지 조합을 확인하게 되지만 n이 1000이라면 166,167,000가지 조합을 확인해야한다. 하지만 여기서 n은 100까지이기에 브루트 포스적으로 풀어도 시간복잡도는 1억(컴퓨터는 1초에 1억번 개산함)을 넘기지 않기 때문에 괜찮은 방법 중에 하나이다.

 

2. 정렬과 두 포인터(Two Pointers) 기법

문제에서 카드 3장을 선택하는 문제는, 우선 카드들을 오름차순으로 정렬한 뒤 한 장을 고정하고 나머지 두장에 대해 투 포인터 기법을 적용하는 방법이 있다.

 

알고리즘 개요

1. 정렬: 카드 리스트를 오름차순으로 정렬한다.
2. 외부 루프: 첫 번째 카드의 인덱스를 하나씩 고정한다.
3. 투 포인터: 고장된 카드 이후의 리스트에서, 두 개의 카드를 선택하기 위해 left와 right포인터를 이용한다.
4. 조건 검사: 만약 세 카드의 합이 M이하이면, 이 값이 지금까지의 최대값보다 큰지 확인하고 업데이트 한 후 left 포인터를 오른쪽으로 이동한다.  만약 합이 M을 초과하면, right 포인터를 왼쪽으로 이동시켜 합을 줄인다.

이것의 장점은 정렬된 상태를 활용함으로써 불필요한 조합을 피할 수 있으며, 시간 복잡도는 O(n^2)로 줄어든다.

 

단점은 코드의 구현 복잡도가 다소 올라갈 수 있고, 정렬이 필요하므로 입력 데이터가 매우 클 때는 추가적인 시간 소여가 있을 수 있다는 점이다.

 

3. 라이브러리를 활용한 조합 생성

파이썬의 itertools.combinations 라이브러리를 사용하면, 카드 리스트에서 3장의 조합을 쉽게 생성할 수 있다. 

 

알고리즘 개요

1. itertools.combinations(cards, 3)를 사용하여 모든 3장 조합을 생성한다.
2. 각 조합의 합을 계산하여 M 이하인 경우 최댓값을 업데이트 한다. 

이것의 장점은 코드가 매우 간결해지며, 문제의 카드 수가 작다면 충분히 빠른 성능을 보이는 것에 있다.

 

단점은 앞서 언급한 브루트 포스 방식과 동일하게, 카드의 수가 많아지면 전체 조합의 수가 기하급수적으로 늘어나 비효유럭이다는 점이다.

 

4. 동적 계획법(Dynamic Programming) 접근법

문제의 특성상 3장이라는 제한된 선택이 있기 떄문에, 일반적인 동적 계획법(DP) 접근법을 적용하기는 어렵다. DP는 보통 여러 개의 원소를 선택하는 경우나 부분 문제의 중복 계산을 줄이는 데 유용하다.

 

이 문제는 단순이 3장을 선택하는 조합 문제이기 때문에, DP를 굳이 사용하지 않아도 되며, 오히려 코드 복잡도가 증가할 수 있다. 

 

문제 전략에 대한 고찰

여러 가지 접근 방식 중에서, 카드의 개수가 크지 않다면, itertools.combinations를 활용한 브루트 포스 접근법이 코드의 간결성 측면에서 유리할 수 있다. 그러나 n이 커지는 경우에는 정렬과 두 포인터 기법을 활용하는 것이 시간 효율성을 고려했을 때 최적의 선택이 될 수 있다. 문제의 조건과 카드의 수에 따라 적절한 방법을 선택한는 것이 중요하다.

 

이처럼, 문제를 해결하기 위해서는 문제의 특성 (예: 카드의 수, 시간 제한 등)을 고려하여 다양한 접근 방식을 생각해보고, 그 중 최적의 방법을 선택하는 것이 핵심이다. 

 

구현

1. 브루트 포스 접근법 활용 (itertools.combinatios 활용)

import itertools

# 입력 처리: 카드의 개수 n, 제한값 m, 그리고 카드 리스트
n, m = map(int, input().split())
cards = list(map(int, input().split()))

ans = 0

# 모든 3장의 카드 조합을 생성하여 확인
for comb in itertools.combinations(cards, 3):
    total = sum(comb)
    # 합이 m 이하이면서 ans보다 크면 갱신
    if total <= m and total > ans:
        ans = total

print(ans)

 

코드 설명

 

1) itertools.combinations(cards, 3)을 통해 카드 리스트에서 3장의 모든 조합을 생성한다.

2) 각 조합의 합을 계산한 후, 조건(total <= m)을 만족하는 경우 최댓값을 업데이트한다.

3) 카드의 개수가 작을 때는 간결하고 이해하기 쉬운 방법이다. 

 

2. 정렬과 두 포인터 기법을 사용한 접근법

# 입력 처리: 카드의 개수 n, 제한값 m, 그리고 카드 리스트
n, m = map(int, input().split())
cards = list(map(int, input().split()))

# 카드 리스트를 오름차순으로 정렬
cards.sort()

ans = 0

# 첫 번째 카드(i)를 고정한 후, 두 포인터(left, right)로 나머지 두 카드를 탐색
for i in range(n - 2):
    left = i + 1
    right = n - 1
    while left < right:
        total = cards[i] + cards[left] + cards[right]
        # 세 카드의 합이 m 이하이면, 현재 조합의 합을 후보로 고려
        if total <= m:
            if total > ans:
                ans = total
            # 더 큰 합을 찾기 위해 left 포인터를 오른쪽으로 이동
            left += 1
        else:
            # 합이 m을 초과하면 right 포인터를 왼쪽으로 이동시켜 합을 줄임
            right -= 1

print(ans)

 

코드 설명

 

1) 카드 리스트를 정렬한 후, 각 카드(i)를 고정하고 나머지 카드들에 대해 두 포인터를 이용해 가능한 조합을 탐색한다.

2) left와 right 포인터를 이용하여 합이 m을 초과하지 않으면서 최댓값을 찾는다.

3) 이 방식은 정렬을 통해 두 포인터를 효율적으로 이동시켜 O(n^2)의 시간 복잡도로 문제를 해결할 수 있다.

 

두 방법 모두 문제의 조건을 충족한다. 하지만 브루트 포스방식은 더 간결해 풀기가 쉬우며 반면 두 포인터 기법은 시간 효율성이 좋다.

---

* 두 포인터(Two Pointers) 기법에 대한 이야기

두 포인터 기법은 배열이나 리스트, 문자열 등 순차적 자료구조에서 두 개의 인덱스(포인터)를 활용하여 문제를 해결하는 알고리즘 기법이다. 이 기법은 여러 문제에서 시간 복잡도를 획기적으로 줄이기 위해 사용되며, 그 구조와 아이디어는 비교적 단순하지만 매우 강력한 도구로 자리 잡았다. 

 

1. 개념과 동작원리

1) 핵심 아이디어

두 개의 포인터를 사용하여 자료구조의 양쪽 끝 또는 특정 부분을 동시에 탐색한다. 이를 통해 불필요한 반복을 줄이고, 문제의 조건에 맞게 인덱스 위치를 조정할 수 있다.

 

2) 동작 방식

(1) 양쪽 끝에서 시작

예를 들어, 정렬된 배열에서 두 수의 합이 특정 값에 가까운 값을 찾는 문제에서는, 하나의 포인터는 시작(최솟값)에서, 다른 하나는 끝(최대값)에서 시작한다. 두 수의 합이 목표보다 크면 큰 쪽의 포인터를 줄이고, 작으면 작은 쪽 포인터를 증가시켜 합계를 조절한다.

 

(2) 슬라이딩 윈도우

연속된 구간의 합, 길이, 혹은 다른 조건을 만족하는 구간을 찾을 때, 한 포인터를 윈도우의 시작, 다른 포인터를 끝으로 사용하여 구간의 크기를 조절한다. 

 

이와 같은 방식은 자료가 이미 정렬되어 있거나 순타적인 특성을 가지는 문제에서 매우 유용하다.

 

2. 사용되는 문제와 응용 분야

1) 합계/차 계산 문제

정렬된 배열에서 두 수의 합이 특정 값과 일치하거나 특정 범위내에 있는 쌍을 찾는 문제에 적용된다. 예로 들어 "두 수의 합"문제 "3SUM 문제" 등에서 핵심 역활을 한다.

 

2) 연속 구간 (Silding Window) 문제

문자열이나 배열 내 연속된 부분 구간에서 특정 조건(예: 최대 또는 최소 길이, 합계 제한)을 만족하는 구간을 찾는 문제에서 사용된다.

 

3) 병합 및 교집합 문제

정렬된 두 배열이나 리스트에서 교집합, 합집합, 혹은 병합하는 과정을 효율적으로 수행할 때 두 포인터를 동시에 이동시키는 방법으로 사용된다.

 

4) 최적화 문제

여러 가지 조간을 만족하는 최적의 해(최대, 최소, 가장 가까운 값 등)를 찾는 문제에서, 포인터 이동을 통해 후보 해를 빠르게 탐색할 수 있다. 

 

3. 역사와 기법의 기원

특정 인물에 의해서 발명되었다기 보다는 알고리즘 설계와 자료구조 탐색 기법이 발전하는 과정에서 자연스럽게 등장한 아이디어이다. 

 

이 방법론은 문제의 특성을 분석하야, 전체 공간을 한 번만 순회하거나 두 번 동시에 순회하면서 조건을 만족하는 해를 잦고자 하는 방법론이다. 이것은 예로 들어 정렬된 배열에서 "합이 특정 값 이하"와 같이 순서에 따라 크기가 결정되는 문제에서는, 배열의 양쪽 끝에서 시작하여 조건에 맞게 포인터를 이동시키면 모든 가능한 쌍을 O(n) 시간에 확인할 수 있다.

 

이에 대한 이해가 가지 않는다면 다음을 보면 이해가 갈 것이다.

[AL] 투 포인터 알고리즘 (+슬라이딩 윈도우) - JavaScript