<브루트 포스 >
검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회 → 완전 탐색 알고리즘
(고지식한 알고리즘)
시간 복잡도 : O(mn) *m : 찾으려는 문자열 패턴의 길이, n : 총 문자열 길이
<2798번 : 블랙잭>
N,M = map(int, input().split())
arr = list(map(int, input().split()))
max_arr=[]
for i in range(N):
for j in range(i+1, N):
for k in range(j+1,N):
three = arr[i] + arr[j] + arr[k]
if three>M:
continue # 무시
else:
max_arr.append(three)
print(max(max_arr))
- 5 6 7 8 9를 리스트로 입력받은 후 반복문을 중첩 사용하여 모든 경우의 수에 대한 합을 구하고 새로운 리스트에 담도록 한다.
그 합이 M을 초과한다면 무시(계속 반복문 진행하고)하고, M보다 작거나 같은 경우에는 그 값을 새로운 리스트에 추가하도록 했다.
[조합(combination) 이용해서 풀기]
# 조합 이용해서 풀기
from itertools import combinations
N,M = map(int, input().split())
arr=list(map(int,input().split()))
max_arr = []
for three in combinations(arr,3):
if sum(three)>M:
continue
else:
max_arr.append(sum(three))
print(max(max_arr))
<2231번 : 분해합>
n = int(input()) # 분해합을 입력값으로 받음
for i in range(1, n+1): # 해당 분해합의 생성자 찾기
num = sum((map(int, str(i)))) # i의 각 자릿수를 더함
num_sum = i + num # 분해합 = 생성자 + 각 자릿수의 합
# i가 작은 수부터 차례로 들어가므로 처음으로 분해합과 입력값이 같을 때가 가장 작은 생성자를 가짐
if num_sum == n:
print(i)
break
if i == n: # 생성자 i와 입력값이 같다는 것은 생성자가 없다는 뜻
print(0)
- for루프를 통해 1부터 N까지의 숫자 i를 순회한다
- str(i)를 사용하여 숫자 i를 문자열로 변환한 뒤, 각 자릿수를 'map(int, str(i))'를 통해 정수로 변환하고, sum()을 사용하여 각 자릿수의 합을 구한다.
- num_sum : i와 각 자릿수의 합을 더한 값
- 만약 num_sum이 N과 같다면 i가 N의 가장 작은 생성자이므로 이를 출력하고 루프를 종료(break)
- 만약 i가 N까지 도달했지만 생성자를 찾지 못한 경우, 이는 생성자가 없는 것이므로 0을 출력한다.
ex: N = 256
i = 245
num = sum(map(int, str(i))) = 2 + 4 + 5 = 11
num_sum = 245 + 11 = 256
num_sum이 N과 같으므로 245가 출력되고 루프 종료
<19532번 : 수학은 비대면강의입니다>
-풀어서 맞춤!
[브루트포스 이용]
# 연립방정식
a,b,c,d,e,f = map(int,input().split())
# a*x + b*y = c
# d*x + e*y = f
for x in range(-999,1000):
for y in range(-999,1000):
if(a*x + b*y)==c and d*x + e*y == f:
print(x,y)
[근의 공식 이용 - 시간복잡도가 O(1)로 속도가 매우 빠름]
import sys
a,b,c,d,e,f = map(int, sys.stdin.readline().split())
x = (e*c)-(b*f)) // ((a*e)-(d*b)
y = (a*f)-(d*c)) // ((a*e)-(d*b)
print(x, y)
<1436번 : 영화감독 숌>
문제 : 666이 들어가는 N번째 큰 수를 찾는 것.
* 주의 : 666, 1666, 2666, 3666, ... 이렇게 가다가 5666 다음으로 큰 수는 6660, 6661, 6662, ... 이런 형태로 증가
따라서 666을 포함하여 왼쪽이 증가하는 경우와 오른쪽이 증가하는 경우가 있음
* 그냥 1부터 10,000까지의 숫자 중에서 666이 들어간 숫자를 찾고 그 숫자가 몇 번째 숫자인지 반환
N = int(input())
num = 666
cnt = 0
while True:
if '666' in str(num): # N번째 수에 '666'이 포함되어 있다면 (str이 아니면 무조건 1의자리부터 시작하니까)
cnt +=1 # 카운트하기
if cnt == N: # 카운트랑 N이 같다면
print(num) # num을 출력하고
break # while문 종료
num+=1 # 666이 포함된 수가 나올 때까지 num을 1씩 증가 시킨다
<2839번 : 설탕 배달>
N = int(input())
cnt = 0
while N >= 0:
if N % 5 == 0: # N이 5의 배수이면
cnt += (N // 5) # 5로 나눈 몫을 구해야 정수
print(cnt)
break
N -= 3
cnt+=1
else:
print(-1)
*놓친 아이디어 : 나누기를 이용하자
- else문 조건도 잘 보기!(예제 입출력에서)
<소트인사이드>
N = int(input())
arr = []
for i in str(N):
arr.append(int(i))
arr.sort(reverse=True)
for i in arr:
print(i,end='')
☆ for문 돌 때 범위는 str로! 배열에 추가해줄 땐 int로!
<11650번 : 좌표 정렬하기>
N = int(input())
arr= []
for i in range(N):
[a,b] = map(int, input().split())
arr.append([a,b])
arr.sort()
for i in arr:
print(i[0],i[1])
☆ 두번째 for문 잘 생각해보기
<11651번 : 좌표 정렬하기2>
☆ y좌표를 기준으로 sort() 해야함!!
arr.sort(key = lambda x : (x[1], x[0]))
☆ 위의 코드는 각 점 x에 대해 (y좌표, x좌표) 순서로 정렬한다.
☆ sort() 함수 람다!
<1181번 : 단어 정렬>
N = int(input())
words = []
for i in range(N):
words.append(input())
words = list(set(words)) # 중복 제거
words.sort() # 사전 순서대로 나열
words.sort(key = len) # 길이를 기준으로 나열
for i in words:
print(i)
☆ 문제 조건 : 중복된 단어는 하나만 남기고 제거 → 중복제거는 set!!
☆ sort() 는 문자도 정리해줌!!!!! 알파벳 순으로 . .
☆ arr.sort(key=len) : 길이를 기준으로 나열해줌!
☆ words.sort() 한 다음에 words.sort(key=len)해줘야함! 왜냐면 길이를 기준으로 먼저 정렬하고 또 sort()하면 다시 abc순서대로 되기 때문에 앞에서 한게 의미 없어짐!!
list.sort() : 오름차순 정렬
.sort(reverse = True) : 내림차순 정렬
.sort(key = len) 혹은 sort(key = lambda x:len(x)): 길이 기준으로 오름차순 정렬
sorted(리스트): 기존 순서를 변경하지 않고 새로운 객체에 정렬된 원소를 저장
.sort(key = lambda x: x[1]): 리스트의 첫 번째 인수들을 기준으로 오름차순 정렬
.sort(key = lambda x: -x[1]): 리스트의 첫 번째 인수들을 기준으로 내림차순 정렬
<10814번 : 나이순 정렬>
N = int(input())
arr=[]
for i in range(N):
[a,b] = map(str, input().split())
a = int(a)
arr.append([a,b])
arr.sort(key = lambda x : x[0]) # (a,b)에서 a만 비교
for i in arr:
print(i[0], i [1])
☆ [a,b] 입력 받을 때 먼저 str로 입력 받고 나이는 정수로 다시 밑 줄에서 바꿔준다.
☆ sort(key = lambda x : x[0])