• 티스토리 홈
  • 프로필사진
    Cat_Code
  • 방명록
  • 공지사항
  • 태그
  • 블로그 관리
  • 글 작성
Cat_Code
  • 프로필사진
    Cat_Code
    • 분류 전체보기 (116)
      • [네이버 부스트캠프] (46)
        • ⭐주간 학습 정리 (43)
        • 🎶추가 학습 정리 (3)
      • [연습의 흔적들] (27)
        • 백준⚾ (26)
        • 캐글 & 데이콘 🤝 (1)
      • [ML] (23)
        • 머신러닝 💕 (5)
        • 딥러닝 🔫 (10)
        • 데이터 분석 🖤 (1)
        • 수학 ☑️ (4)
        • LLM🦜 (3)
      • [CS] (16)
        • 파이썬 🖤 (12)
        • 해체 분석기📝 (3)
        • Service Product (1)
        • MultiMedia (0)
      • [개발일지] (2)
  • 방문자 수
    • 전체:
    • 오늘:
    • 어제:
  • 최근 댓글
      등록된 댓글이 없습니다.
    • 최근 공지
        등록된 공지가 없습니다.
      # Home
      # 공지사항
      #
      # 태그
      # 검색결과
      # 방명록
      • [백준] 14501번 퇴사 파이썬(Python) 풀이🚩
        2022년 10월 19일
        • Cat_Code
        • 작성자
        • 2022.10.19.:22
         

        14501번: 퇴사

        첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

        www.acmicpc.net

         

        [문제]


        [코드]

        n = int(input())
        day = []
        money = []
        
        dp = [0]  * (n + 1)
        max_value = 0
        
        for _ in range(n):
            x, y = map(int, input().split())
            day.append(x)
            money.append(y)
        
        for i in range(n-1, -1, -1):
            time = day[i] + i
            if time <=n:
                dp[i] = max(money[i] + dp[time], max_value)
                max_value = dp[i]
            else:
                dp[i] = max_value
        
        print(max_value)

        [해설]

         

         

         이 풀이의 핵심은 '다이나밍 프로그래밍'  (동적 계획법)이다. [줄여서 'DP'] 

        사실 나도 전공자가 아니기 때문에 이러한 용어에 익숙하지 않지만 이번 문제를 풀면서 좀 더 자세히 살펴볼 수 있었다. [이는 코드 해설이후 자세히 기록해 두었다.]

         

        1. 우선 총 날짜를 input()으로 받고 이를 변수로 지정한다

        그리고 day와 money의 빈 리스트를 생성한다.

        n = int(input())
        day = []
        money = []

         

        2. 그리고 dp를 생성하는데 n+1번째 날이 퇴사를 하는 기쁜 날이기 때문에 n+1길이 만큼 생성한며

        max_value값을 생성하여 0으로 지정한다 (max_value 값은 우리가 원하는 출력값으로 그날에 최대로 땡길 수 있는 금액을 의미한다)

        dp = [0]  * (n + 1)
        max_value = 0

         

        3. 그리고 for 문을 활용해서 x=걸리는 날, y=받는 금액을 input()으로 받고 이를 각각 day리스트와 money리스트에 추가한다

        for _ in range(n):
            x, y = map(int, input().split())
            day.append(x)
            money.append(y)

         

        4. 다음이 이 문제의 핵심 풀이라고 할 수 있는데 우선 for문을 활용해서 위에서 아래로 내려오게한다(역순)

        그런다음 time이라는 변수를 지정하고 이는 i번째 걸리는 날 + i를 더한 값으로 이 값이 n보다 작을때만 계산이 작동하게 한다. 만약 크다면 이는 그날의 상담을 할 수 없기 때문에 그냥 넘어가게한다.

         

        먼저 0으로 채워진 dp의 i번째 값을 money[i] + dp[time(=day[i] + i)]와 max_value중 큰값을 저장하고

        d이를 다시 max_value로 지정한다.

         

        그리고 이러한 계산이 끝나고 난 후 max_value를 출력하면 우리가 원하는 값이 출력된다.

        for i in range(n-1, -1, -1):
            time = day[i] + i
            if time <=n:
                dp[i] = max(money[i] + dp[time], max_value)
                max_value = dp[i]
            else:
                dp[i] = max_value
        
        print(max_value)

         

         > 코드가 돌아가면 어떻게 계산이 될까?

        예제 1의 값을 입력했을 때 돌아가는 원리 

        <예제1 입력>

        7
        3 10
        5 20
        1 10
        1 20
        2 15
        4 40
        2 200

        ---------------------------------------- else
        i: 6
        time 8
        dp: [0, 0, 0, 0, 0, 0, 0, 0]
        max_value: 0
        ---------------------------------------- else
        i: 5
        time 9
        dp: [0, 0, 0, 0, 0, 0, 0, 0]
        max_value: 0
        ---------------------------------------- if time <=n
        i: 4
        time 6
        dp: [0, 0, 0, 0, 15, 0, 0, 0]
        max_value: 15
        ---------------------------------------- if time <=n
        i: 3
        time 4
        dp: [0, 0, 0, 35, 15, 0, 0, 0]
        max_value: 35
        ---------------------------------------- if time <=n
        i: 2
        time 3
        dp: [0, 0, 45, 35, 15, 0, 0, 0]
        max_value: 45
        ---------------------------------------- if time <=n
        i: 1
        time 6
        dp: [0, 45, 45, 35, 15, 0, 0, 0]
        max_value: 45
        ---------------------------------------- if time <=n
        i: 0
        time 3
        dp: [45, 45, 45, 35, 15, 0, 0, 0]
        max_value: 45


        다이나믹 프로그래밍 Dynamic programming, Dp

        최적화 이론의 한 기술이며, 트정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

        즉, 이전의 값을 활용해서 답을 구하는 것이다 (쉽게 설명하면)

        이는 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것이다.

         

         

        그렇다면 DP는 왜 사용할까?

        일반적인 재귀방식 또한 DP와 비슷한 부분이 많이 존재하지만 재귀방식의 경우 동일한 작은 문제해결 방식이 반복해서 사용되기 때문에(같은 방법이 계속 반복) 비효율적이라는 것이다.

        이는 파보나치 수열의 문제를 예로 들 수 있다.

        위 사진은 파보나치 수열을 재귀함수를 사용했을때의 트리 모양이다.

        f함수의 계산을 계속해서 사용하고 있다는 것을 확인할 수 있다. 이는 숫자가 커지면 계산의 횟수가 기하 급수적으로 증가한다.

        그러나 위의 계산값들을 자세히 보면 중복되는 계산결과가 많다는 것을 확인할 수 있다.

        즉 이를 dp에 저장해서 불러온다면 계산의 횟수를 효율적으로 줄일 수 있다.

         

        더 자세한 설명은 아래 블로그를 참조 

         

        알고리즘 - Dynamic Programming(동적 계획법)

        1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으

        hongjw1938.tistory.com

         

        '[연습의 흔적들] > 백준⚾' 카테고리의 다른 글

        [백준] 11724번 연결 요소의 개수 파이썬(Python) 풀이  (0) 2022.10.31
        [백준] 1012번 유기농 배추 파이썬(Python) 풀이  (0) 2022.10.26
        [백준] 1260번 DFS와 BFS 파이썬(Python) 풀이  (0) 2022.10.24
        [백준] 1021번 회전하는 큐 파이썬(Python) 풀이  (0) 2022.10.22
        [백준] 2108번 통계학 파이썬(Python) 풀이  (0) 2022.10.20
        다음글
        다음 글이 없습니다.
        이전글
        이전 글이 없습니다.
        댓글
      조회된 결과가 없습니다.
      스킨 업데이트 안내
      현재 이용하고 계신 스킨의 버전보다 더 높은 최신 버전이 감지 되었습니다. 최신버전 스킨 파일을 다운로드 받을 수 있는 페이지로 이동하시겠습니까?
      ("아니오" 를 선택할 시 30일 동안 최신 버전이 감지되어도 모달 창이 표시되지 않습니다.)
      목차
      표시할 목차가 없습니다.
        • 안녕하세요
        • 감사해요
        • 잘있어요

        티스토리툴바