[BOJ]숫자카드, 곱셈, 쿼드트리

아 원래는 로직 모르면 진짜 구글 카피캣이었는데........이젠......스스로 해보려한다........절대 구글을 보지 않겠다 선언.

 

 

라는 문제를 풀어봤다.

이미..... 강의를 해주신 분의 코드를 봐버려서....그분의 카피캣이 되는 것 같다만......직접 짜보진않고 눈으로만 봤으니까 !!

 

이거는 시간복잡도 생각하면 리스트보다 set과 in쓰면 좋을 것 같다. 왜냐면....set과 in을 배웠으니까...긴한데 그래도 적용 시켜보니 뭔가 어떨 때 써야할 지 감이옴 . 

input받을 때도 원래는 하나하나 받아서 리스트 저장했는데 이젠 한 줄로 map과 split주구장창 써야겠다 .

 

n = int(input())

have_cards= set(map(int, input().split()))
m=int(input())

for i in map(int,input().split()):
    if i in have_cards:
        print(1 , end=" ")
    else:
        print(0, end=" ")

set집합에다 input받아주는데 공백으로 구분되어 받아줘야하니 map으로 해준다....

그리고 바로 for문에다 넣어가면서 비교해보게 하기

 

 

 

그럼 17^500 같은 큰 수는 어떻게 효율적이게 계산할까

숙제로 내주셨을 땐 " 어차피 같은 수 곱하니까 쪼개서 곱해가면 되지 않을까 ~ " 했음.

근데 쪼개서 뭘 어쩔건지는....몰랐다.

 

로직을 설명해준 거 한 줄 설명하면 

500 > a * a

a > b* b 해서 재귀돌리면된다.......................라는 식

이게 분할 정복인데 ! 원래 하나씩 다 곱하면 O(n)이 되는데 분할정복을 하게되면 1/2씩 횟수가 줄어들어감.

횟수*1/2 = 구할 것 > log 밑2 지수 구할것 이렇게 바뀌기 때문에!!

O(logN)이 됨... 이거 진짜 뭔 말인지 그냥 외웠엇ㄴ느데 이해 되니까 짱재밌다..........

 

 

그래서 바로 백준 풀어보기 

이 문제인데. 우선 C로 나눈 나머지를 구하는 건 나중에 하고 A ^B부터 구현해보자

쓸 건 분할 정복. 재귀

#공백을 두고 입력받아야하므로 map사용
a,n = map(int,input().split())


#재귀를 돌려버리기
def divcon(inputnum, num):
    if num == 1:
        return num
    elif num % 2 ==0 :
        temp = divcon(inputnum,num//2)
        return temp * temp
    elif num % 2 == 1:
        temp =divcon(inputnum,num//2)
        return temp*temp*inputnum
    
print(divcon(a,n))

해주면 효율적으로 거듭제곱을 계산 할 수 있는데, C를 나눠줘야한다.

이럴땐 나머지만 구하면 되므로 큰 계산을 다 하지말고, 나머지끼리 계산 한 후 나머지를....나눠주는 

모듈러 연산!!을 사용하면 된다 

#공백을 두고 입력받아야하므로 map사용
a,n ,c= map(int,input().split())


#재귀를 돌려버리기
def divcon(inputnum, num):
    if num == 1:
        return num
    elif num % 2 ==0 :
        temp = divcon(inputnum,num//2)
        return ( temp * temp ) % c
    elif num % 2 == 1:
        temp =divcon(inputnum,num//2)
        return ( temp*temp*inputnum ) %c
    
print(divcon(a,n) %c)

는 무슨 ㅋㅋ 이거 틀림.... return에 inputnum을 return해줘야하는데 이걸 틀렸다?

== 난 또 강의자님의 카피캣이된거다..........

그래서 다른 문제를 풀어보기로 했다.

 

정말..어려워보이지만.....재귀를 이해했다면.........분할정복을 이해했다면.............풀어야지.......그럼.....

일단 문제 이해는 ㅇㅋ나눠지는 부분마다 ()로 안 나눠질 때까지 하면 되는것.

 

.................

배고파서 그런걸까 집중이안되는 군 일주일 이번주내로 풀기 ㅠㅠㅠㅠㅠ

로직은 우선.... 

list로 엔터만큼 리스트 만들고

만약 리스트 속 숫자들 . ex 11110000 , 11000011,.... 이면 

첫 리스트 인덱스 요소를 2로 나눈 뒤 temp에 저장하고

또 다음 인덱스 요소를 2로 나눈 뒤 temp에 추가해주고 

계속하다보면 첫 네모구역 만큼의 temp 인덱스가 나올거임 . (1)1111(2)1111(3)1111(4)11111

이렇게 괄호 빼고 temp가 구성될거란 말이지 .

이거를 set으로 저장했을 것이고 다른숫자가  있는지 검사한 후 

없으면 answer에 1or0을 ( 숫자 ) 이런식으로 저장해준다..........

이걸 재귀로 다른 숫자 있을 때 마다 다시 divcon해주면 될 것 같은데

이게 시간복잡도가 낮을 수 있는 로직인가 싶다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

엄청 복잡하게 코드짜는 것 같은데

아니 애초에 이걸 코테에서 시간안에 풀 수있을까 .......조바심도 나고

암튼 배고파서 이런 것 같으니 낼...은 멋사하고........금토일 알바하고 짬내서 ..해보자.............

 

size = int(input())
img = list(map(int, input().split("\n")))
answer=""
def divcon(size, p):
    
    #size/2 만큼 첫 리스트 검사. size/2만큼 리스트 검사
    size /= 2
    for i in size:
        temp = index(i)
        if i+1 == 
    
    
print(answer)

는 처참히 실패....5일동안 고민해봐도 뭔지모르겠음...........ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

머리가 안돌아간다 안돌아가

진짜 진짜 진짜 어쩔 수 없이 구글보고 ........해석해보자...

// size개수 입력받기
n = int(input().split())

//큰 틀의 배열 (1차원배열)
graph = []
//1차원 배열 속 list 공백을 두고 입력[ [] [] [] []... ]의 형태가 되는 거 맞나?
for i in range(n):
    graph.append(list(map(int,input().split())))

//재귀 ( x y는 시작 좌표 , n은 사분할 사이즈 )
def dfs(x,y,n):
	//만약 분할할 게 없다면 바로 그 좌표 값을answer에 추가
    if n==1:
        answer.append(graph[x][y])
        return
    
    //기준 그래프 좌표의 값 지정
    stand = graph[x][y]
    //x기준부터 x의 사분할 사이즈까지 검사
    for i in range(x,x+n):
    	//만약 검사 중인 좌표값이 기준 그래프 좌표값과 다르다면
        if graph[i][j]!=stand:
        	//사분할 사이즈를 절반해주고
            n//=2
            //새로운 사분할 들어가기 전 ( 추가
            answer.append('(')
            //새로운 사분할의 1사분면 시작
            dfs(x,y,n)
            //새로운 사분할의 2사분면 시작
            dfs(x,y+n,n)
            //새로운 사분할의 4사분면 시작
            dfs(x+n,y,n)
            //새로운 사분할의 3사분면 시작
            dfs(x+n, y+n,n)
            //사분할 값이 끝났으면 )로 닫아주기
            answer.append(')')
            return
            
    //모두 1 혹은 0으로 채워진 경우 
    answer.append(stand)
    return


answer=[]
dfs(0,0,n)
//리스트로 공백과 콤마 구분자 출력 방지  (풀어준 뒤 공백 지우기)
print(*answer,sep="")

아~~눈으로만 보면 당연히 이해 되지 이걸 뭐 어떻게 해야하지??????

담주에 다시 풀어본다....