✅ 문제 풀이 - BOJ (Brute Force)
🎈 1182 부분 수열의 합
n개의 정수로 이루어진 수열이 있을 때 크기가 양수인 부분 수열 중 그 수열의 원소를 다 더한 값이 s가 되는 경우의 수를 구하는 문제.
- 첫 줄에 정수 개수 n, s가 주어지고 둘째 줄에 수열이 주어진다.
import sys
input = sys.stdin.readline
n, s = map(int, input().split())
seq = list(map(int, input().split()))
answer = 0
# 인덱스, 숫자 합 (비교를 위한) 변수 설정
def dfs(idx, total):
# 총 경우의 수 구하기 위해 전역변수 설정
global answer
# 주어진 인덱스가 순열 길이에 도달하면 return (백트래킹)
if idx >= n:
return answer
# 순열 첫 인덱스에 위치한 숫자부터 total에 더해서 저장
total += seq[idx]
# s와 숫자 합이 일치하면 answer + 1처리
if total == s:
answer += 1
# 다음 인덱스, 현 인덱스까지의 순열 숫자 합
dfs(idx+1, total)
# 다음 인덱스, 현재 인덱스에 있는 순열 숫자를 빼고 다음 인덱스로 바로 넘어가서 비교
dfs(idx+1, total - seq[idx])
# 0번인덱스 숫자합 초기 0으로 dfs탐색 시작
dfs(0, 0)
print(answer)< 풀이 과정 >
완전탐색 문제는 재귀함수 + 백트래킹을 활용하여 해결할 수 있음을 앞서 그래프 알고리즘을 학습하며 이해해놨다. 참고 내용
이를 활용하여 주어진 순열에서 0번 인덱스에 위치한 숫자부터 dfs함수를 활용하여 2가지의 case로 반복하여 탐색을 진행한다.
- dfs(다음 인덱스, 현 인덱스까지의 순열 숫자 합)
- dfs(다음 인덱스, 숫자 합(현 인덱스에 위치한 순열 숫자 값 뺀)
이때 백트래킹 조건은, 주어진 인덱스가 범위를 넘어서는 경우에 return 하도록 한다.
🎈 1759 암호 만들기
암호는 L개의 서로 다른 알파벳 소문자로 구성되고 각 암호는 최소 1개의 모음과 2개의 자음으로 구성되어 있다. 첫 줄에 L과 c가 주어지고 이후 c개의 알파벳이 주어졌을 때, 주어진 c개의 알파벳으로 L자리 암호를 만들 때 가능한 암호를 모두 출력하는 문제
import sys
input = sys.stdin.readline
l, c = map(int, input().split())
alpha = sorted(list(input().split()))
answer = []
vowel = ['a', 'e', 'i', 'o', 'u']
def dfs(cnt, idx):
# 암호문 완성된 경우 자음, 모음 개수 확인
if cnt == l:
vo, co = 0, 0
for i in range(l):
if answer[i] in vowel:
vo += 1
else:
co += 1
# 암호문 완성 및 자음 모음 개수 이상 없으면 print로 출력
if vo >= 1 and co >= 2:
return print(''.join(answer))
# 암호문 완성을 위해 idx, c 범위로 answer에 주어진 alpha 문자 삽입하며 재귀
for i in range(idx, c):
answer.append(alpha[i])
dfs(cnt+1, i+1)
answer.pop()
dfs(0, 0)
< 풀이 과정 >
암호문을 완성하는 과정에서 생각하고 구현하는데 시간이 좀 걸린 문제.
최종적으로 암호문을 완성해 자음, 모음 개수를 확인하여 출력하는 것은 오래 걸리지 않는다.
그러나 이 문제의 핵심은 암호문을 완성해가는 과정.
for문으로 dfs함수 내 parameter인 idx를 이용하여 주어진 배열 alpha의 앞문자부터 시작해 모든 경우의 수를 백트래킹 하여 구현
🎈 1476 날짜 계산
첫 줄에 E, S, M에 해당하는 숫자 3개가 주어지고 해당 년도를 출력하는 문제로 각 알파벳은 다음을 의미한다.
- E : 지구를 의미하며 [1,15]의 범위를 가짐
- S : 태양을 의미하며 [1,28]의 범위를 가짐
- M : 달을 의미하며 [1,19]의 범위를 가짐
import sys
input = sys.stdin.readline
e, s, m = list(map(int, input().split()))
year = 1
while True:
if (year-e) % 15 == 0 and (year-s) % 28 == 0 and (year-m) % 19 == 0:
break
year += 1
print(year)< 풀이 과정 >
e, s, m에 해당하는 숫자를 하나씩 입력받고 while 문으로 각 숫자의 범위 내 최대값으로 나눈 나머지가 모두 0인 경우가 찾고자 하는 년도이므로 year +1 씩 루프를 돈다.
🎈 2003 수들의 합 2
n개의 원소로 구성된 수열 A가 존재할 때 i번째 수부터 j번째 수의 합이 m이 되는 경우의 수를 구하는 문제
첫 줄에 n, m이 주어지고 수열이 둘째 줄에 주어진다.
n의 범위는 [1, 10000], m의 범위는 [1, 3*1e9], 각 원소는 30000을 넘지 않는 자연수
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
seq = list(map(int, input().split()))
left, right = 0, 1
answer = 0
while left <= right <= n:
total = sum(seq[left:right])
if total < m:
right += 1
elif total > m:
left += 1
else:
answer += 1
right += 1
print(answer)< 풀이 과정 >
2중 for문을 활용한 합산보단, 투 포인터로 시작지점, 종료지점을 지정하고 만족하는 범위 내 while문으로 루프를 돌리는 것이 시간복잡도가 더 낮다.
따라서, while문으로 합산 값을 total로 정한 후, m보다 작다면 우측으로 추가 m보다 크다면 좌측 + 1처리, m과 같다면 answer + 1, right + 1로 종료 조건에 가깝게 접근
