본문 바로가기

백준

브루트포스

 

 

<브루트 포스 >

검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회 → 완전 탐색 알고리즘

(고지식한 알고리즘)

시간 복잡도 : 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]) 

 

 

 

 

 

 

'백준' 카테고리의 다른 글

집합과 맵  (0) 2024.07.30
정렬  (0) 2024.07.26
시간 복잡도  (0) 2024.07.25
기하  (0) 2024.07.25
[BaekJoon/Python3] 약수, 배수와 소수  (0) 2024.07.24