0에서 n까지 가는 dp문제이다. 처음에는 재귀로 dp 돌렸는데 거리가 n을 초과하거나 비용이 더 작을 때만 진행시켜도 시간 초과났다. 거리가 2배인 곳으로 순간이동하는 데 비용이 없어 최대한 순간이동 시켜주는 게 좋으므로 2의 배수라는 것을 처리해주기 위해 %연산자를 써서 n에서 시작해서 0 까지 가준다. 2이 배수가 아닐 때에는 순간이동해서 온게 아니므로 -1로 짝수로 이동해준다. function solution(n) { var ans = 0; while(n>0){ if(n%2==0){ n/=2; }else{ n-=1; ans+=1; } } return ans; }
dp[i][j] < i 번째 집 j색깔 색깔이 0인 경우 이전 집 dp[i-1][1]과 dp[i-1][2] 중 더 비용이 적은 것에서 현재 0을 칠하는 비용을 더해주는 방식으로 갱신해준다. n번째 집까지 다 칠한 경우 dp[n-1][0], dp[n-1][1], dp[n-1][2] 중에서 가장 비용이 적은 것을 출력해준다. import java.util.Scanner; public class Main { static int n; static int[][] rgb; static int[][] dp; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); rgb=new int[n][3]; dp=new ..
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 보자마자 dfs 풀이가 생각났으나 dp로 풀어보려고 했다. a,b,c 대신에 배열을 쓰면 좀 더 깔끔할 듯하다. 최종 dp[n]에 들어가는 수가 1로 시작해서 n을 만들 수 있는 경우의 수이니 n에서 1을 만드는 것과 방법의 수가 같다. 각각의 방법으로 현재 수 i를 만드는 방법 중 최소의 계산 횟수를 넣어준다. import java.util.Arrays; import java.util.Scanner; public class Main { static int answer; static int n; static int[] dp;..
연속된 부분 수열은 아니고 각 문자열을 이루고 있는 문자들 순서만 맞춰서 최장 공통 부분 수열을 구하는 문제이다 a, b 두 문자열의 길이 +1 (각 첫번째 인덱스에 들어가는 값은 초기값인 0이다.) 인덱스 i,j를 비교해서 a와 b의 각 위치에 들어간 문자가 같다면 이전 최대 길이 +1 을 해주면 된다. 1: acaykp , 2: capcak에서 1의 부분 문자인 a(인덱스 0)만 봤을 때 2에서 c인 경우 0, ca인 경우 1 이런식으로 추가되는 문자가 같다면 1 증가시키는 식으로 해결한다. import sys input=sys.stdin.readline a=input().strip() # 엔터키도 들어가지 않도록 b=input().strip() # print(a,len(a)) dp=[[0]*(len..
연속된 집은 털 수 없다. 바로 이전 집의 dp값이나 두 번째 전 집에서 현재 집을 턴 합 중 더 큰 값이 현재 위치의 집에서 가장 큰 값이 된다 from collections import defaultdict class Solution: def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums)
계단 오르기 문제 메모이제이션으로 재귀로 풀어도 되고 반복문으로 풀어도 된다 1계단에 오르는 방법 1로 가는거 한 가지, 2 계단에 오르는 법은 1에서 1칸 가는 방법, 0에서 2칸 가는 방법 2가지로 초기화한다. 나머지만 현재 위치보다 1칸 아래에서 오는 방법과 2칸 아래에서 오는 방법을 더해주면 된다 from collections import defaultdict class Solution: def climbStairs(self, n: int) -> int: dp=defaultdict(int) dp[1]=1 dp[2]=2 for i in range(3,n+1): dp[i]=dp[i-1]+dp[i-2] return dp[n]
[운영체제] 2020/10/20 - [운영체제 요약정리] - [운영체제] 운영체제의 역사 [알고리즘, dp 부문] 2020/10/21 - [Leetcode] - [LeetCode] Fibonacci number (dp, 파이썬) 2020/10/21 - [Leetcode] - [LeetCode] Maximum Subarray(python, 최대 서브배열,dp) [리액트] 2020/10/21 - [React공부] - [React] 배열 데이터 처리(생성,렌더링, 수정,제거) 2020/10/21 - [React공부] - [React] 리액트 undefined처리 방법 (누구든지하는 리액트5편 공부정리)
합이 최대인 부분 배열을 찾는다 현재 값 혹은 현재값 + 이전까지의 합이 큰지 비교해서 더 큰 값을 dp배열에 넣고 최대 값을 리턴하면 된다. O(n)이 걸린다 class Solution: def maxSubArray(self, nums: List[int]) -> int: answer=[nums[0]] for i in range(1,len(nums)): answer.append(nums[i]+(answer[i-1] if answer[i-1]>0 else 0)) return max(answer) * 카데인 알고리즘 (가끔 알고리즘이나 자료구조 공부할 때 항상 등장하는 부분배열 최대값 구하기 알고리즘이다 O(n)에 구할 수 있다 현재의 부분 배열 합과 리턴해줄 최대값을 비교해 더 큰 값으로 계속 갱신해준다 ..
이런 방식으로 하면 공간복잡도(1) 시간복잡도(n)으로 아주 효율성이 좋다 class Solution: def fib(self, N: int) -> int: x,y=0,1 for _ in range(N): x,y=y,x+y return x 기본 메모이제이션 풀이 from collections import defaultdict class Solution: dict=defaultdict(int) def fib(self, N: int) -> int: if N
못지나가는 길 puddles의 i,j가 바뀌어있음을 주의 def solution(m, n, puddles): dp=[[0]*(m+1) for _ in range(n+1)] dp[1][1]=1 for i in range(1,n+1): for j in range(1,m+1): if i==j==1: continue if [j,i] not in puddles: dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007 return dp[n][m]