본문 바로가기

DP8

[프로그래머스 lv 3] N으로 표현 사용 언어 - Python3 문제 - N으로 표현 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 정답 n숫자를 이용해서 number를 만들기 n 숫자를 1개부터 8개(cnt)까지 활용하면서 찾아준다. n을 최소한으로 사용해야하므로 number 값이 나오면 바로 끝낸다. return cnt 구하는 값 저장할 리스트, dp = [] dp 값들로 사칙연산한 값을 저장할 set, partial_dp = set() n을 2번 사용한다 = n + n o.. 2023. 12. 5.
[백준] 1520번 내리막 길 사용 언어 - Python3 문제 - 1520번 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) ex,ey가 m*n 그래프 안에 있어야함 조건2) .. 2023. 11. 1.
[백준] 19947번 욕심쟁이 판다 사용 언어 - Python3 문제 - 19947번 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) n*n 그래프 안에 있어야함 0 조건.. 2023. 11. 1.
[백준] 1149번 RGB거리 사용 언어 - Python3 문제 - 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 정답 바텀업 DP 손코딩, 아이큐 테스트, 규칙 찾기 문제 빨/초/파는 같은 rgb를 가진 집과 이웃하면 안되므로, 각 색깔을 기준으로 비용을 업데이트해준다. 빨 - 이전의 초 or 파 중 최솟값 + 현재의 빨 값 초 - 이전의 빨 or 파 중 최솟값 + 현재의 초 값 파 - 이전의 빨 or 초 중 최솟값 + 현재의 .. 2023. 10. 31.
[백준] 11726번 2xn 타일링 사용 언어 - Python3 문제 - 11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 정답 피보나치 타일링 - 바텀업 DP 손코딩, 아이큐 테스트, 규칙 찾기 문제 # 규칙이 보여야만 풀수 있는 문제 => 많이 풀다보면 규칙이 보이는 문제이다. # 피보나치를 그림으로 만든 문제 0,1,1,2,3,5,8 dp[i] = dp[i-2] + dp[i-1] n dp 1 1 2 2 3 3 4 5 5 8 9 55 import sys input = sy.. 2023. 10. 31.
[백준] 12865번 평범한 배낭 (냅색 문제) 사용 언어 - Python3 문제 - 12865번 평범한 배낭 냅색 Knapsack 문제 : 여러 물건이 있을 때, 특정 조건을 만족하는 조합 구하기 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 정답 1. 완전 탐색적 재귀함수 => 시간 초과 def recur(idx, w, v) def recur(idx,w,v): global answer if w > k: # 버틸 수 있는 .. 2023. 10. 30.
[백준] 14501번 퇴사 사용 언어 - Python3 문제 - 14501번 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 정답 1. 완전 탐색적 재귀함수 def recur(day, total) recur(상담받는 날짜, 수익합) day = 0일부터 n-1일까지 반복 day가 n-1보다 크고, n보다 크면 무시 아니라면, total,answer 중 더 큰 수익값으로 업데이트 - 상담 하는 경우, 날짜+날짜만큼 더하기, 수익+수익만큼 더하기 - 상담 안하는 경우, 날짜+1, 수익 그대로 print(answer) def recur(day,total): global answer if day > n-1: #.. 2023. 10. 30.
다이나믹 프로그래밍? 나동빈 이코테 유튜브 강의 정리 https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6 다이나믹 프로그래밍 DP = 동적 계획법 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록. 두 가지 조건 만족 시 DP 사용 - 최적 부분 구조 Optimal Substructure 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다. - 중복되는 부분 문제 Overlapping Subproblem 동일한 작은 문제를 반복적으로 해결해야 합니다. 대표 문제. 피보.. 2023. 6. 1.

티스토리툴바