2023 팀네이버 신입 공채 준비 (9) 프로그래머스 DP

오늘 한 리스트

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

프로그래머스 DP 정수 삼각형

• 문제 유형 : DP
  정수 삼각형 결과 찾기

  def solution(triangle):
    n = len(triangle)
    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            triangle[i][j] += max(triangle[i+1][j], triangle[i+1][j+1])
    return triangle[0][0]
  

  굉장히 아이디어를 생각하는데 오래 걸렸던 문제였다. 각각의 위치에서 제일 큰 값을 저장하고 나머지는 버리는 방식으로 진행 된다.

프로그래머스 DFS/BFS 타겟 넘버

• 문제 유형 : DFS/BFS
  타겟 넘버

  def dfs(numbers, target,res_num,idx):
    answer=0
    if idx==len(numbers):
        if res_num==target:
            return 1
        else:
            return 0
    res_num_p=numbers[idx]+res_num
    res_num_m=-numbers[idx]+res_num
      
    answer+=dfs(numbers, target, res_num_p, idx+1) # +
    answer+=dfs(numbers, target, res_num_m, idx+1) # -
    return answer
  def solution(numbers, target):
    answer=dfs(numbers,target,0,0)
    return answer
  

  솔직하게 말하면 못풀고 다른 사람의 풀이를 확인했다. 다른 사람의 풀이를 참고하면서 푼 코드이다.

프로그래머스 DFS/BFS 네트워크

• 문제 유형 : DFS/BFS
  네트워크

  def dfs(computers,visited,index):
    answer=0
    visited[index]=True
    result=computers[index]
    for n,j in enumerate(result):
        if j ==1 and visited[n]==False:
            dfs(computers,visited,n)
    return visited
  def solution(n, computers):
    #m_cls=memory(n)
    visited=[False]*n
    num=0
    while False in visited:
        index=visited.index(False)
        visited=dfs(computers,visited,index)
        num+=1
    return num
  

  직접 짠 코드이며 위에서 봤던 코드를 활용해서 풀어봤다.