1. 완전탐색

=브루트포스(brute-force) 알고리즘

컴퓨터의 빠른 계산 속도를 믿고 모든 경우의 수를 전부 따지기.

제한시간이 있는 문제를 풀 때, 완전 탐색 가능한지 판단이 먼저. O(n) 시간복잡도 계산하기.

컴퓨터는 1초에 약 1억 번의 연산을 한다고 함.

 

~백준 세 문제 풀어보기~

 

13423번: Three Dots (acmicpc.net)

13423번: Three Dots

시간복잡도 계산 안 하고 냅다 3중반복문으로 풀었을 때 : 시간초과

점이 최대 1000개이니, 1000*1000*1000만큼의 연산이 필요하기때문.

import sys
input = sys.stdin.readline
t=int(input())
for i in range(t):
    n=int(input())
    x=sorted(list(map(int,input().split())))
    p=0
    for a in range(n):
        aa=x[a]
        for b in range(a+1,n):
            bb=x[b]
            for c in range(b+1,n):
                cc=x[c]
                if bb-aa==cc-bb:
                    p+=1
    print(p)

파이썬 라이브러리 중 하나인 itertools를 이용해도 변함없음. (여기선 순열을 만드는 함수 combinations(~,n) 사용)

===========================================

sys 모듈의 stdin  vs  inputinput : prompt 메시지 출력, 입력받음, 개행문자 삭제시키고 반환stdin : 그냥 입력받아 반환>>> 여러 줄 입력받을 때 input 사용하면 시간 초과 에러 뜨는 경우가 생김

>>> 개행문자까지 받아줘서 print(temp+"\n") 이렇게 따로 문자열 처리 안 해줘도 됨

     이미 받을 때부터 temp="하고싶은말\n" 로 입력 받았을 것

 

readline() :문장 한 줄을 읽어 문자열로 반환.*read(), readlines(), read(숫자) 같은 것들도 있음.

 

input=sys.stdin.readline 으로 지정해줬으므로, 이제 input 으로 정수 3 을 입력받으면 문자열 '3\n' 이 받아짐>>>int로 꼭 형 변환해주고 개행문자 떼어 주고 사용============================================

 

from itertools import combinations as cb #외부함수이니 import 해야함
...
    for j in cb(x,3): # x라는 리스트에서 세 개 골라뽑기
        if j[2]-j[1]==j[1]-j[0]:
            p+=1

 

defaultdict를 사용하면 해결된다고 함!

 

===== [defaultdict란?] 기본값을 지정한 딕셔너리. collections 모듈에 있는 기능.

             일반딕셔너리

di=dict()                                                 #di라는 딕셔너리                                                                                                     

di('a')                                   #key a을 삽입하지않고 호출.                      

>>> KeyError: 'a'                                                         

#딕셔너리에서 setdefault 사용, 호출과 동시에 선언가능

di.setdefault("a",3)   

>>>{'a':3} 

 

           defaultdict

from collaections import defaultdict                                                 #import하기

di=defaultdict(int)                                                                   #di라는 defaultdict

>>>defaultdict(<class 'int'>, {})                                 #디폴트값이 int인 딕셔너리

di['a']                                                                        #key a을 삽입하지않고 호출

>>>defaultdict(<class 'int'="">, {'a': 0})          #값을 설정하지 않아도 0 초기화 됨

===============================================================

#공부목적으로 블로그참고한코드
import sys
input = sys.stdin.readline
from collections import defaultdict
t=int(input())
for i in range(t):
    n=int(input())
    x=sorted(list(map(int,input().split())))
    di=defaultdict(int)
    for j in x:
        di[j]=1 #True를 의미함
    p = 0
    for a in range(n-1):
        for b in range(a+1,n):
            aa=x[a]
            bb=x[b]
            cc=x[b]+(x[b]-x[a]) #bb에서 bb와aa사이만큼더함
            if di[cc]==1: #만들어둔딕셔너리에 존재? 있는점이구나!
                p+=1
    print(p)

근데 이 코드도 시간초과남;; 1000*1000도는것까지 지금 줄인상태~?~?~?

이제 어쩔지는... 생각해보는걸로...

얘는 완전탐색 안되는게아닐까??? 정답코드참고할라고 파이썬으로푼거 다찾아봤는데 완전탐색으로 풀리는게없음 ㅇㄴ;;

이게맞아?

 

1436번: 영화감독 숌 (acmicpc.net)

1436번: 영화감독 숌

이 문제는 푸는 법도 모르겠다. 심지어 정답률은 이쪽이 더 높음 ^!^!^

1. '666' 문자 앞뒤로 숫자 붙이기

2. 666에서 +1000을 하다가 +1을 해주고 하기 <그나마 이쪽이 조건 와다다 달면 풀 수는 있을 것 같음

3. 컴퓨터에게 모든 걸 맡기고 666 붙어있을 때만 뽑아달라하기 <<< n=3일 때 조차 버거워하길래 관뒀음...

이 생각밖에 안든다 남들은 어케 푼 거지?

n=int(input())
a='0666'
if n==1:
    print(666)
else:
    for _ in range(n-1):
        if a[-4]=='5':
            a= str(1 + int(a))
            #a='666'+'0'*(len(a)-3)
            while (a.count('666') == 0):
                a = str(1 + int(a))
        elif a[-4]=='6':
            a = str(1 + int(a))
        else:
            a=str(1000+int(a))

        if a.count('666')==0:
            while(a.count('666')==0):
                a=str(1 + int(a))
	print(a)

틀렸대... 뭐가 틀린건데... 난 맞는거같애... 악

아 줄 잘 맞춰야겠다 어쩐지 반례 다넣어도 맞는데 왜 틀렸나했네

답 블로그 안 보고 반나절 머리싸매다 푸니까 기분이 좋다가 남들은 이거 후루룩 잘 풀고 다른 문제 풀었을텐데 싶다가 아니??? 너가 작년에 놀았으니 지금 이렇게 하고 더하고더해야하지않을까??? 니 이제부터 하루 일 포스팅해라 지켜본다

 

 

1895번: 필터 (acmicpc.net)

1895번: 필터

조건보니 하라는대로 완전탐색해도 시간충분. 정말 하라는대로 해봄

import sys
input = sys.stdin.readline
r,c=map(int,input().split())
li=[]
final=[]
for _ in range(r):
    x=list(map(int,input().split()))
    li.append(x)
t=int(input())
for i in range(r-2): #r*c 픽셀
    for j in range(c-2):
        vlist = []
        for m in range(3): #3*3 필터
            for n in range(3):
                vlist.append(li[i+m][j+n])

        vlist=sorted(vlist)
        final.append(vlist[4]) #중앙값
q=0
for i in range(len(final)): #t보다큰거나 같은지 판단
    if final[i]>=t:
        q+=1
print(q)

생각없이 문제에서 하라는대로했더니 너무 긴가싶음. 좀 더 멋지게 풀 순 없나? 다른사람들도 이런식으로 푼듯함. 중앙값을 굳이 추가하지 않은 경우가 많음.

r,c=map(int,input().split())
li=[]
final=[]
for _ in range(r):
    li.append(list(map(int,input().split())))
t=int(input())
q=0
for i in range(r-2):
    for j in range(c-2):
        vlist = []
        for m in range(3):
            for n in range(3):
                vlist.append(li[i+m][j+n])
        vlist.sort()
        if vlist[4]>=t:
            q+=1
print(q)

 

 

 

+ 추가문제

6603번: 로또 (acmicpc.net)

6603번: 로또

어차피 완전탐색 카테고리로 들어간 문제이기도 하고... 대강 출력할 애들 보면 시간도 안전함

걍 조합 패키지 써야겠음 itertools 패키지의 combinations는 저렇게... 쓰는거임 리스트랑~

출력할때 join 써서 띄어쓰기로 문자열로변환해서 잘 나눠써주고~~