백준 1062번 가르침
https://www.acmicpc.net/problem/1062
- 이번에는 완전 탐색의 유연한 생각에 대표 문제인 골드 5티어 가르침 문제를 풀어보았습니다.
- 최근 공부하고 있는 알고리즘 관련해서 뼈대라 할 수 있는 문제의 대표격이라 풀어보았는데 생각보다 시간이 많이 걸려서 좀 당황했습니다.
###### 접근
- 조건 처리를 잘 해야 빠르게 정답을 찾을 수 있었던 문제 였던 것 같습니다.
- n개의 단어와 k(배울 수 있는 알파벳 개수)를 입력받고, 어떤 조합으로 k개의 알파벳을 익혀야 최대한 많이 단어를 읽을 수 있는지에 대한 문제인데, 단어는 anta 로 시작해서 tica 로끝나는 형태인 것입니다. 즉 anta ? tica 이 순이 되는 것입니다.
###### 풀이순서
- 단어 입력 및 필수 글자 처리:
- 단어는 중복된 알파벳이 있을 수 있으므로, set 자료형을 사용하여 중복을 제거한 집합으로 변환합니다. 이렇게 변환된 집합을 통해 각 단어에서 반드시 필요한 알파벳이 무엇인지 확인할 수 있습니다.
- 이때, 각 단어에서 고유한 알파벳들로 이루어진 집합의 길이(curSetLen)가 배울 수 있는 글자 수 k보다 크다면, 해당 단어는 절대 읽을 수 없으므로 바로 무시합니다.
- 단어 집합 길이가 5인 경우 처리:
- 현재 단어 집합의 길이가 정확히 5라면, 이는 'a', 'n', 't', 'i', 'c' 알파벳으로만 구성된 단어이므로 무조건 읽을 수 있습니다. 따라서 결과 변수 cnt에 1을 더합니다.
- 필수 알파벳 제외한 고유 알파벳 수집:
- 각 단어에서 필수 알파벳인 'a', 'n', 't', 'i', 'c'를 제외한 나머지 고유한 알파벳 집합을 구하고, 이를 uniqueList에 저장합니다.
- 이 과정에서 uniqueSet이라는 변수에 고유 알파벳들을 계속해서 업데이트(합집합)하여, 중복을 제거한 전체 고유 알파벳 집합을 구합니다. 이 uniqueSet은 이후 조합(combinations) 탐색에서 사용할 것입니다.
- 특수 조건들에 대한 예외 처리:
- (1) k가 5 미만인 경우: 필수 알파벳 5개('a', 'n', 't', 'i', 'c')를 배우지 못하면 어떤 단어도 읽을 수 없으므로, 바로 0을 반환합니다.
- (2) uniqueList가 비어 있는 경우: 만약 모든 단어가 'a', 'n', 't', 'i', 'c'로만 구성된 경우라면, 더 이상 처리할 필요 없이 cnt 값만 반환하면 됩니다.
- (3) 고유 알파벳이 k-5 이하인 경우: 만약 고유 알파벳의 개수가 k-5 이하라면, 해당 알파벳을 모두 배우면 모든 단어를 읽을 수 있으므로 더 이상 탐색할 필요 없이 cnt에 uniqueList의 길이를 더하여 반환합니다.
- 브루트포스 탐색 (조합 사용):
- 이제 필수 알파벳 5개('a', 'n', 't', 'i', 'c')를 제외한 고유한 알파벳들(uniqueSet) 중에서 k-5개의 글자를 선택해야 합니다. 이를 위해 combinations 함수를 사용해 가능한 모든 조합을 구합니다.
- 각 조합에 대해 uniqueList의 각 단어와 비교하여, 해당 조합이 그 단어의 고유 알파벳을 모두 포함하는지 여부를 판단합니다. 포함하는 경우, 즉 상위집합(superset)이면 그 단어를 읽을 수 있으므로, 그때마다 카운터(tmpAns)를 증가시킵니다.
- 모든 경우에 대해 최대 읽을 수 있는 단어 수(maxCnt)를 계산하여 최종적으로 cnt에 더합니다.
- 최종 결과 반환:
- cnt에는 초기 필수 글자만으로 읽을 수 있는 단어와, 추가로 배운 알파벳 조합으로 읽을 수 있는 단어 수를 더해 최종 결과를 반환합니다.
| from itertools import combinations import sys input = sys.stdin.readline def solve(n, k): required = {'a', 'n', 't', 'i', 'c'} # 필수로 배워야 하는 글자 unique_list = [] # 각 단어에서 필요한 고유 글자들 (a, n, t, i, c 제외) unique_set = set() # 전체 단어에서 고유한 글자들 (중복 없이) cnt = 0 # 읽을 수 있는 단어 개수 for _ in range(n): cur = input().strip() cur_set = set(cur) cur_set_len = len(cur_set) # 단어를 구성하는 글자의 개수가 k보다 크면 배울 수 없으므로 배제 if cur_set_len > k: continue # 단어가 오직 필수 글자들로만 구성된 경우 바로 카운트 if cur_set_len == 5: cnt += 1 continue # a, n, t, i, c를 제외한 고유 글자들만 저장 cur_unique = cur_set - required unique_list.append(cur_unique) unique_set.update(cur_unique) # 필수 글자만으로도 부족할 경우 if k < 5: return 0 # 추가로 배울 글자가 없는 경우, 즉 antic로만 읽을 수 있는 경우 if len(unique_list) == 0: return cnt # 배워야 할 글자의 수가 K-5 이하일 경우 모든 단어를 읽을 수 있음 if len(unique_set) <= k - 5: return cnt + len(unique_list) max_cnt = 0 # 모든 가능한 조합을 brute-force로 시도해 가장 많은 단어를 읽을 수 있는 조합 찾기 for c in combinations(unique_set, k - 5): case_set = set(c) tmp_ans = 0 for unique_word in unique_list: if case_set.issuperset(unique_word): # 선택한 글자들이 해당 단어의 모든 글자를 포함할 경우 tmp_ans += 1 max_cnt = max(max_cnt, tmp_ans) cnt += max_cnt return cnt n, k = map(int, input().strip().split()) print(solve(n, k)) |
- 초기 변수 설정:
- required: 모든 단어에서 필수로 배워야 하는 글자들. 'a', 'n', 't', 'i', 'c'는 모든 단어에 필수적으로 포함되기 때문에, 이 5개의 글자는 무조건 배워야 합니다.
- unique_list: 각 단어에서 필수 글자 외에 배워야 할 고유한 글자들. 각 단어마다 required를 제외한 고유 글자를 저장합니다.
- unique_set: 모든 단어에서 필요한 고유한 글자들의 집합. 중복을 제거한 글자들이 저장됩니다.
- cnt: 읽을 수 있는 단어의 수를 카운트합니다.
- 각 단어 처리:
- 입력받은 단어를 cur_set으로 변환해 글자 집합을 만들고, 그 길이를 계산하여 조건을 확인합니다.
- 글자 수가 k보다 많다면, 해당 단어는 배울 수 없으므로 건너뜁니다.
- 단어가 필수 글자들로만 구성된 경우, 바로 읽을 수 있으므로 카운트를 증가시킵니다.
- 그 외의 경우에는 필수 글자를 제외한 나머지 고유 글자들을 unique_list에 저장하고, unique_set에 추가해 나갑니다.
- 특수 조건 처리:
- 배워야 할 글자의 수 k가 5 미만이라면 필수 글자들을 배우지 못하기 때문에 바로 0을 반환합니다.
- 추가로 배워야 할 글자가 없는 경우, 즉 모든 단어가 필수 글자들로만 구성된 경우에는 더 이상 탐색할 필요 없이 바로 읽을 수 있는 단어 개수를 반환합니다.
- 고유한 글자 수가 k-5 이하라면 모든 단어를 읽을 수 있으므로, unique_list의 길이를 더해 반환합니다.
- 브루트포스 탐색:
- combinations를 이용해 unique_set에서 k-5개의 글자 조합을 생성하고, 각 조합으로 몇 개의 단어를 읽을 수 있는지 계산합니다.
- case_set이 각 단어의 고유 글자를 모두 포함할 경우, 해당 단어를 읽을 수 있다고 판단하여 카운트를 증가시킵니다.
- 최대로 읽을 수 있는 단어의 개수를 계산하여 반환합니다.
### 브루트포스 탐색이란?
- 이번 코드로 인해서 브루트 포스 탐색에 대해 좀 더 공부할 수 있었습니다.
```
브루트포스 탐색은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 방식입니다. 이 방법은 문제를 해결할 수 있는 모든 경우를 하나하나 다 살펴보면서 해결책을 찾기 때문에, 해를 반드시 찾을 수 있다는 장점이 있습니다. 하지만 경우의 수가 많을 경우, 비효율적일 수 있습니다.
브루트포스 탐색 과정
모든 경우의 수를 탐색:
문제에서 가능한 모든 경우를 전부 나열하고, 그 중에서 정답을 찾는 방식입니다.
예를 들어, N개의 알파벳에서 K개를 선택하는 모든 경우의 수를 살펴보고, 조건을 만족하는지를 확인합니다.
문제 적용:
문제에서 'a', 'n', 't', 'i', 'c'를 제외한 알파벳들 중에서 K-5개의 알파벳을 선택해야 합니다.
이를 위해서는 선택할 수 있는 모든 알파벳의 조합을 구하고, 그 조합으로 몇 개의 단어를 읽을 수 있는지를 하나하나 계산합니다.
결과 도출:
모든 조합을 살펴본 후, 가장 많은 단어를 읽을 수 있는 조합을 찾아 최적의 해를 도출합니다.
브루트포스 탐색 예시
예를 들어, 6개의 고유한 알파벳이 있다고 가정하고, 그 중에서 3개의 알파벳을 선택하는 모든 경우의 수를 찾는다고 해봅시다:
- 선택 가능한 알파벳: ['b', 'd', 'e', 'f', 'g', 'h']
- 3개의 알파벳을 선택하는 조합의 경우의 수는 다음과 같습니다:
* ('b', 'd', 'e')
* ('b', 'd', 'f')
* ('b', 'd', 'g')
* ('b', 'd', 'h')
* ...
총 20가지의 경우의 수가 나옵니다.
모든 경우의 수를 하나씩 확인한 뒤, 각 조합으로 얼마나 많은 단어를 읽을 수 있는지 계산하는 방식입니다.
브루트포스 탐색의 장단점
장점:
간단하고 직관적입니다. 가능한 모든 경우의 수를 고려하기 때문에 해를 놓치는 일이 없습니다.
최적해를 보장합니다. 모든 경우를 탐색하므로, 반드시 최적의 답을 찾을 수 있습니다.
단점:
비효율적일 수 있습니다. 특히 경우의 수가 매우 많아질 때(즉, 탐색 공간이 커질 때) 시간 복잡도가 급격히 증가합니다.
일반적으로 시간 복잡도가 높아 큰 입력값을 다루기 힘듭니다.
시간 복잡도
브루트포스 탐색의 시간 복잡도는 문제에 따라 다르지만, 일반적으로는 경우의 수가 많아질수록 지수 시간 복잡도가 될 수 있습니다. 예를 들어, N개의 원소 중 K개를 선택하는 경우의 수는 조합을 사용하여 O(N^K)가 될 수 있습니다.
## 이번 문제에서의 브루트포스 탐색
- 문제에서는 'a', 'n', 't', 'i', 'c'를 제외한 나머지 알파벳들 중에서 K-5개의 알파벳을 선택해야 했으므로. 고유 알파벳의 조합을 모두 탐색하며, 각 조합으로 몇 개의 단어를 읽을 수 있는지 하나씩 확인해야 했습니다.
- 브루드포스 탐색 단계를 보면
- 고유 알파벳을 추출: 단어에서 'a', 'n', 't', 'i', 'c'를 제외한 고유 알파벳들을 추출합니다.
- 조합을 생성: 고유 알파벳들 중에서 K-5개의 알파벳을 선택하는 모든 경우의 수를 구합니다.
- 단어 비교: 각 조합에 대해 해당 조합으로 읽을 수 있는 단어 수를 계산합니다.
- 최댓값 계산: 모든 경우의 수를 탐색한 후, 가장 많은 단어를 읽을 수 있는 조합을 찾습니다.
# 코드를 통해서 보게 되면 아래와 같이 구성된 것입니다.
| from itertools import combinations # 모든 고유 알파벳에서 K-5개의 조합을 탐색 for c in combinations(uniqueSet, k-5): caseSet = set(c) # 현재 선택된 알파벳 조합 tmpAns = 0 # 각 단어의 고유 알파벳이 선택된 알파벳 조합에 포함되는지 확인 for uniqueWord in uniqueList: if caseSet.issuperset(uniqueWord): tmpAns += 1 # 해당 단어를 읽을 수 있으면 카운트 증가 maxCnt = max(maxCnt, tmpAns) # 최댓값 갱신 |
- 여기서 combinations 함수는 고유 알파벳 집합에서 가능한 모든 조합을 생성하고, 각 조합에 대해 단어를 몇 개나 읽을 수 있는지 확인한 후 최댓값을 찾는 역활을 하는 것이죠
Team-TIL/9.19 ~ 9.30 회고/2024-09-24 - 지웅.md at main · Python-Backend-Team3/Team-TIL
Today Learned repository. Contribute to Python-Backend-Team3/Team-TIL development by creating an account on GitHub.
github.com
- 오늘의 회고 입니다!