2023 팀네이버 신입 공채 준비 (12) DP

오늘 한 리스트

1. 프로그래머스 DP 2문제

프로그래머스 DP N으로 표현

• 문제 유형 : DP
  N으로 표현 ``` def Case_5(N,test,check): if check==False: if not test: test.append(N10+N) test.append(-(N10+N)) test.append(N//N) test.append(-(N//N)) test.append(N+N) test.append(-(N+N)) test.append(NN) test.append(-(NN)) #test.append(-N) ### return test new_list=[] if test: for i in test: #new_list.append(i) new_list.append(-(i10+N)) new_list.append(i10+N) new_list.append(-(i//N)) new_list.append(i//N) new_list.append(-(iN)) new_list.append(iN) if i-N!=0: new_list.append(i-N)### new_list.append(-(i-N))
  return list(set(new_list)) else: new_list=[] for i in N: for j in test: if j!=0: new_list.append(i//j) new_list.append(-(i//j)) if i!=0: new_list.append(j//i) new_list.append(-(j//i)) new_list.append(i+j) new_list.append(-(i+j)) new_list.append(ij) new_list.append(-(ij)) if i-j!=0: new_list.append(i-j) if j-i!=0: new_list.append(j-i) return new_list

def solution(N, number): # case 1 => N_110+N # case 2 => N/N # case 3 => N+N # case 4 => NN # Case 5 => N-N # 다른 가지에서 더해질 수도있는 경우를 생각해야댐 test=[] test_dict={1:[N,-N]} test_list=[] for i in range(1,8): test=Case_5(N,test,False) if number in test: test_list.append(i+1) continue for j in test_dict.keys(): if j+i+1>=8: continue new_list=Case_5(test_dict[j],test,True) if number in new_list: test_list.append(j+i+1) continue test_dict[i+1]=test #print(len(test_dict[i])) if test_list: return min(test_list) else: return -1

모든 경우에 대해서 만들어 봤으나 몇가지 경우에 대해서 실패함 다른 사람들의 solution code를 확인해봄

def solution(N, number): dp = [[]]

x = 0
for i in range(1, 9):
    dp.append(set())
    x = 10*x + N
    dp[i].add(x) # N, NN, NNN...
    print(dp)
    for j in range(i):
        # 연산자 케이스 
        for op1 in dp[j]:
            for op2 in dp[i-j]:
                dp[i].add(op1 + op2)
                dp[i].add(op1 - op2)
                dp[i].add(op1 * op2)
                if op2 != 0:
                    dp[i].add(op1 // op2)


        if number in dp[i]:
            return i
        print(dp)
        break

return -1 ``` dp에 set()을 넣어주면 add할 때마다 자동으로 정렬을 해줌, 다양한 case에 대해서 dp에 저장하고 모든 경우에 대해서 `+ - * //`을 진행한 후 결과를 확인 함

프로그래머스 DP 등굣길

• 문제 유형 : DP
  등굣길

  def solution(m, n, puddles):
    answer = 0
    final_list=[]
    pu=[]
    m_min=101
    n_min=101
    for i in puddles:
        if i[0]==1 or i[1]==1:
            pu.append(i)
    if pu:
        pu=sorted(pu,key=lambda x: x[0])
        n_min=pu[0][1]
        pu=sorted(pu,key=lambda x: x[1])
        m_min=pu[0][0]
    for i in range(n):
        test_list=[]
        for j in range(m):
            if i==0 or j==0:
                test_list.append(1)
            else:
                test_list.append(0)
        final_list.append(test_list)
    #print(final_list)
    if m_min!=101:
        print(m_min)
        for i in range(m_min-1,len(final_list[0])):  
            final_list[0][i]=-1
    if n_min!=101:
        for i in range(n_min-1,len(final_list)):
            final_list[i][0]=-1
    #print(final_list)
          
              
    for i in puddles:
        final_list[i[1]-1][i[0]-1]=-1
    #print(final_list)
    for i in range(1,n):
        for j in range(1,m):
            if final_list[i][j]==-1:
                continue
            else:
                if final_list[i-1][j] != -1 and final_list[i][j-1] != -1:
                    final_list[i][j]=final_list[i-1][j]+final_list[i][j-1]
                else:
                    final_list[i][j]=max(final_list[i-1][j],final_list[i][j-1])
    if final_list[n-1][m-1]==-1:
        return 0
    return final_list[n-1][m-1] % 1000000007
  

  처음 만들었을 때 모든 case에 대해서 진행했다고 생각했으나 잘 안됨 그래서 문제가 무엇인지 생각해 봤을 때 padding을 진행하지 않아서 코드가 너무 더러워 졋다고 판단함
  다른 사람들 코드

  def solution(m,n,puddles):
    grid = [[0]*(m+1) for i in range(n+1)] #왼쪽, 위로 한줄씩 만들어서 IndexError 방지
    if puddles != [[]]:                    #물이 잠긴 지역이 0일 수 있음
        for a, b in puddles:
            grid[b][a] = -1                #미리 -1로 체크
    grid[1][1] = 1
    print(grid)
    for j in range(1,n+1):
        for k in range(1,m+1):
            if j == k == 1:                #(1,1)은 1로 만들어두고, 0이 되지 않도록
                continue
            if grid[j][k] == -1:           #웅덩이는 0으로 만들어 다음 덧셈 때 영향끼치지 않게
                grid[j][k] = 0
                continue
            grid[j][k] = (grid[j][k-1] + grid[j-1][k])%1000000007   #[a,b] = [a-1,b] + [a,b-1] 공식
  
    return grid[n][m]
  

  padding을 한번 해주니 코드가 너무 깔끔해졋다…