[프로그래머스] 코딩 테스트 공부 (DP, 다익스트라)

2023. 8. 14. 15:28·Coding Test/programmers
728x90

https://school.programmers.co.kr/learn/courses/30/lessons/118668

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

1. DP

INF=float('inf')
def solution(alp, cop, problems):
    max_alp=0 # 알고력
    max_cop=0 # 코딩력
    for a,b,c,d,e in problems:
        max_alp=max(max_alp, a)
        max_cop=max(max_cop, b)
            
    alp = min(alp, max_alp)
    cop = min(cop, max_cop)
    
    # dp[i][j] : 알고력이 i, 코딩력이 j를 얻기위해 걸리는 최소시간
    dp = [[INF]*(max_cop+1) for _ in range(max_alp+1)]
    dp[alp][cop]=0
    
    for i in range(alp, max_alp+1):
        for j in range(cop, max_cop+1):
            
            # 코딩공부(1시간)로 높이기
            if i != max_alp:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+1)
            if j != max_cop:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j]+1)
                
            # 문제 풀어서 높이기
            for nalp, ncop, ralp, rcop, cost in problems: # [필요알고력, 필요코딩력, 증가알고력, 증가코딩력, 문제푸는데드는시간]
                if i >= nalp and j >= ncop:
                    next_alp = min(max_alp, i+ralp)
                    next_cop = min(max_cop, j+rcop)
                    dp[next_alp][next_cop] = min(dp[next_alp][next_cop], dp[i][j]+cost)
                    
    return dp[-1][-1]  # 모든 문제들을 풀 수 있는 알고력과 코딩력을 얻는 최단시간

 

2. 다익스트라

from collections import namedtuple
from heapq import heappush, heappop
INF=float('inf')

Problem = namedtuple('Problem', ['cost', 'nalp', 'ncop', 'ralp', 'rcop'])

def solution(alp, cop, problems):

    dist={(alp,cop):0}
    visited=set()
    q=[]
    
    problems=[Problem(cost, nalp, ncop, ralp, rcop) for nalp, ncop, ralp, rcop, cost in problems ]
    problems+=[Problem(1,0,0,1,0), Problem(1,0,0,0,1)]
    
    max_alp=max(p.nalp for p in problems)
    max_cop=max(p.ncop for p in problems)
    
    heappush(q, (0,alp,cop))
    
    while q:
        d,a,c = heappop(q)
        
        if (a,c) in visited:
            continue
        else:
            visited.add((a,c))
            
        for p in problems:
            newa, newc = min(a+p.ralp, max_alp), min(c+p.rcop, max_cop)
            newcost=d+p.cost
            
            if a>=p.nalp and c>=p.ncop and newcost < dist.get((newa, newc), INF):
                dist[(newa, newc)] = newcost
                heappush(q, (newcost, newa, newc))

    return dist[(max_alp, max_cop)]

 

 

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)
'Coding Test/programmers' 카테고리의 다른 글
  • [프로그래머스] 고고학 최고의 발견
  • [프로그래머스] 시험장 나누기 (이분탐색)
  • [프로그래머스] 2차원 동전 뒤집기
  • [프로그래머스] N으로 표현
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    DP
    프로그래머스
    최소신장트리
    Algorithm
    플로이드워셜
    스택
    조합
    동적계획법
    트리
    다익스트라
    재귀
    BFS
    덱
    최대공약수
    월간코드챌린지
    그래프
    정렬
    최단거리
    힙
    구현
    LIS
    백준
    파이썬
    큐
    DFS
    알고리즘
    그리디
    자료구조
    구간합
    이분탐색
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[프로그래머스] 코딩 테스트 공부 (DP, 다익스트라)
상단으로

티스토리툴바