수학과의 개발자 도전기

-정답 풀이:

하나의 위치는(i,j) 왼쪽(i,j-1), 왼쪽 위(i-1,j-1), 왼쪽 아래(i+1,j-1)의 숫자들로부터 온다. 그래서 이 숫자들 중에 최댓값을 (i,j)에 저장하면서 누적한다 

점화식

dp[i][j]=array[i][j] + max(dp[i-1][j-1],dp[i][j-1],dp[i+1][j-1])

t=int(input())
for _ in range(t):
	n,m=map(int,input().split())
    data=list(map(int,input().split()))
    dp=[[] for _ in range(n)]
    ans=0
    
    for i in range(n):
    	for j in range(i*m,(i+1)*m):
        	dp[i].append(data[j])
            
    for j in range(1,m):
    	for i in range(n):
              
            if i==0:
                left_up=0
            else: 
                left_up=dp[i-1][j-1]
            if i==n-1:
                left_down=0
            else:
                left_down=dp[i+1][j-1]
            left=dp[i][j-1]
            dp[i][j]=dp[i][j]+max(left_up,left_down,left)
    
    for i in range(n):
        ans=max(ans,dp[i][m-1])                   
    print(ans)

-내 풀이

여기서 오류. 문제는 한 위치에서 오른쪽 위,옆,아래로만 이동할 수 있는데 내가 쓴 풀이로 하면 이 범주를 넘어가게 연산이 돼서 틀린 답이 출력된다 

따라서 점화식으로 진행해야한다 

t=int(input())
for _ in range(t):
	n,m=map(int,input().split())
    ans=0
    dp=[[] for _ in range(n)]
    data=list(map(int,input().split())
    cnt=0
    for i in range(n):
    	for j in range(i*m,(i+1)*m):
        	dp[i].append(data[j])
            
    for j in range(m):
    	  for i in range(n):
        	  cnt=max(dp[i][j],cnt)
          ans+=cnt
          cnt=0
        
    print(ans)

-문제: https://programmers.co.kr/learn/courses/30/lessons/60060

문제풀이 아이디어가 신기했던 문제다. 

특정 문자의 시작과 끝 인덱스를 얻으려면 bisect_left,bisect_right 함수를 이용하자 

풀이 아이디어: 

1. 각 단어를 길이에 따라서 나눈다(words 리스트)

2. 모든 리스트를 정렬한 후에(words 리스트)

3. 각 쿼리에 대해서 이진 탐색을 수행한다 

"fros??"라는 쿼리가 나오면, 길이가 5이고, "fro"로 시작하는 단어를 찾는다.

count_by_range() 함수를 이용해서 "froaa" 보다 크고, "frozz"보다 작거나 같은 단어의 갯수를 센다 

"????o"인 경우에 대해서는 words의 단어들을 뒤집어서 저장한 reversed_array를 이용하면 된다 

-정답 풀이

from bisect import bisect_left,bisect_right

def count_by_range(a,left_value,right_value):
    right_index=bisect_right(a,right_value)
    left_index=bisect_left(a,left_value)
    return right_index - left_index 

array=[[] for _ in range(10001)]
reversed_array=[[] for _ in range(10001)]


def solution(words, queries):
    answer = []
    for i in words:
        array[len(i)].append(i)
        reversed_array[len(i)].append(i[::-1]) #단어를 뒤집어서 삽입 
        
    for j in range(10001):
        array[j].sort()
        reversed_array[j].sort()
        
    for q in queries:
        if q[0]!='?':
            res=count_by_range(array[len(q)],q.replace('?','a'),q.replace('?','z'))
        else: 
            res=count_by_range(reversed_array[len(q)],q[::-1].replace('?','a'),q[::-1].replace('?','z'))
        answer.append(res)
        
                
    return answer

-내 풀이

1. TypeError: string indices must be integers, not str -> 해결 mid=(start+end)/2 에서 /가 아닌 //를 이용

2. TypeError: 'NoneType'Object is not iterable. (x,y=questions(i)) -> 해결 못함. return을 제대로 안해서 생긴 문제 같음,,

def questions(x):
    length=len(x)
    start=0
    end=length-1
    
    while True:
        if start> end: 
            break       
        mid=(start+end)//2
        if x[mid]=='?':
            if x[mid+1] !='?':
                return [0,mid]
            start=end+1
        if x[mid]!= '?':
            if x[mid+1]=='?':
                return [mid,length-1]
            end=mid-1
def compareWords(i,j,a,b):
    if a==0:
        for x in range(b+1,len(i)):
            if i[x]!=j[x]:
                return False
    else:
        for y in range(0,a):
            if i[y]!=j[y]:
                return False
    return True

words=["frodo","front","frost","frozen","frame","kakao"]
queries=["fro??","????o","fr???","fro???","pro?"]
        

def solution(words, queries):
    answer = []
    for i in queries:
        x,y=questions(i)
        a,b=int(x),int(y)        
        cnt=0
        flag=True
        for j in words:
            if len(j)==len(i):
                flag=compareWords(i,j,a,b)
                if flag:
                    cnt+=1
        answer.append(cnt)
                
    return answer

-문제: https://programmers.co.kr/learn/courses/30/lessons/60058

일단 지문부터 이해하기가 좀 어려웠다. 문제를 잘풀려면 일단 문제를 잘 이해해야한다

그래서 답지를 보고 풀었다

대부분은 이해가 갔는데 이해가 잘 가지 않는 부분이 있다. 

균형 괄호의 인덱스를 구할때는 if count==0: 문장이 바깥에 있는데

올바른 괄호를 check 할때는 왜 이게 else 문에 들어가 있는지 생각을 해봐야 겠다 

else:
            if count ==0:
                return False
            count-=1

-정답풀이

def balanced_index(p):
    count=0
    for i in range(len(p)):
        
        if p[i]=='(':
            count+=1
        else:
            count-=1
            
        if count ==0:
            return i
        
def check_proper(p):
    count=0 #왼쪽 괄호의 갯수
    for i in p:
        if i=='(':
            count+=1
        else:
            if count ==0:
                return False
            count-=1
    return True 
    

def solution(p):
    answer = ''
    if p =='':
        return answer
    index = balanced_index(p)
    u=p[:index+1]
    v=p[index+1:]
    #u가 올바른 괄호 문자열이면, v에 대해 함수를 수행한 결과를 붙여 반환
    if check_proper(u):
        answer = u+ solution(v)
    #u가 균형잡힌 괄호 문자열이면 아래의 과정을 수행 
    else:
        answer='('
        answer+=solution(v)
        answer+=')'
        
        u=list(u[1:-1])
        #괄호 뒤집기 
        for i in range(len(u)):
            if u[i]=='(':
                u[i]=')'
            else:
                u[i]='('
        answer += "".join(u)        
    return answer

-문제: https://programmers.co.kr/learn/courses/30/lessons/60062?language=python3 

weak의 위치가 원형으로 이루어져 있어서 어떻게 풀어야 할지 몰랐던 문제다. 

친구의 수와 취약점들의 갯수가 많지 않으므로 완전 탐색을 통해서 답을 낼 수 있다. (주어진 조건들의 갯수 확인하기)

원형으로 주어지면 각 리스트의 값에 n을 더해 리스트의 길이를 늘려준다. 

거기서 친구별로 갈 수 있는 길이만큼 탐색을 하는 방식으로 하면 된다. 

from itertools import permutations

def solution(n, weak, dist):
    
    length= len(weak)
    for i in range(length):
        weak.append(weak[i]+n)
    
    #친구수 +1, min사용 & 친구 전체를 투입해야 할 수 있으니까
    answer = len(dist)+1
    
    for start in range(length):#각각의 weak 포인트들로부터 시작하기 
        for friends in list(permutations(dist,len(dist))):
            cnt=1            
            #시작하는 취약점 + 친구가 1시간에 이동할 수 있는 거리(해당 친구가 점검할 수 있는 마지막 위치)
            position= weak[start]+friends[cnt-1] 
            #시작점부터 모든 취약점을 확인
            for index in range(start,start+length):
                if position < weak[index]:#해당친구 점검이 끝나도 취약지점이 있을때
                    cnt+=1 #친구 추가
                    if cnt>len(dist):
                        break 
                    position = weak[index]+friends[cnt-1]
            answer= min(answer,cnt)
            
    if answer>len(dist):
        return -1
    return answer