RUBY

출처:: www.acmicpc.net/problem/11054 분류:: dp 1. 문제 이해 및 해결과정 - dp[i] : i까지 수 중 가장 긴 바이토닉 수열의 길이 ex) 1 5 2 1 4 3 4 5 2 1 dp[0] 1 2 2 1 3 3 4 5 2 1 왼쪽부터 가장 긴 부분수열을 구한다 dp[1] 1 5 2 1 4 3 3 3 2 1 오른쪽부터 가장 긴 부분수열을 구한다. dp[2] 1 6 4 3 5 6 6 7 7 3 가장 큰 값은 중복되므로 -1, dp[0][i]+dp[1][i]-1 2. 풀이방법 1. dp #가장 긴 바이토닉 부분 수열 #https://www.acmicpc.net/problem/11054 import sys sys.stdin = open("input.txt","r") input=s..

출처:: www.acmicpc.net/problem/10819 분류:: 브루트포스, 순열 1. 문제 이해 및 해결과정 - 모든 순열로 경우를 고려하면 된다 2. 풀이방법 1. 순열 #차이를 최대로 #https://www.acmicpc.net/problem/10819 import sys from itertools import permutations sys.stdin = open("input.txt","r") input=sys.stdin.readline n=int(input()) a=list(map(int,input().split())) selected=list(permutations(a,n)) res=-1e9 for i in range(len(selected)): sum=0 s=selected[i] for..

출처:: https://www.acmicpc.net/problem/10973 분류:: 브루트포스 1. 문제 이해 및 해결과정 - 다음 순열 문제(hiruby.tistory.com/521)와 알고리즘 유사 1) 감소하는 것들 중 가장 큰 인덱스 찾기 1-1) 감소하는 것들이 없다면, 가장 처음 오는 수열이 된다 2) 인덱스 i보다 큰 수 중 a[i]보다 더 작은 값 찾기 3) a[i]와 a[j] 값 swqp 4) i보다 큰 수들을 내림차순으로 배열 2. 풀이방법 1. #이전순열 #https://www.acmicpc.net/problem/10973 import sys sys.stdin = open("input.txt","r") input=sys.stdin.readline n=int(input()) a=lis..

출처:: www.acmicpc.net/problem/11055 분류:: dp 1. 문제 이해 및 해결과정 - 가장 긴 부분 수열 중에 부분수열의 합이 가장 큰 것을 구하라 는 문제 인줄 알았는데 - 그냥 길이에 관계없이 부분수열 중에 합이 가장 큰 것을 찾으면 된다. -dp[i] : i까지 수 중 가장 큰 부분수열의 합 ex) 1 100 2 50 60 3 5 6 7 8 1 101 3 53 113 6 11 17 24 32 1) dp배열은 최소 자기자신이므로 arr[i]로 초기화 2) 기준점 인덱스보다 작고, 자기자신보다 작은 값들 중에 가장 큰 값에 자기자신더해주기 => max(dp[i],dp[j]+arr[i]) 2. 풀이방법 1.dp #가장 큰 증가 부분 수열 #https://www.acmicpc.net..

출처:: www.acmicpc.net/problem/10971 분류:: 브루트포스, DFS 1. 문제 이해 및 해결과정 - DFS로 2. 풀이방법 1. [python] dfs #외판원 순회 2 #https://www.acmicpc.net/problem/10971 import sys sys.stdin = open("input.txt","r") input=sys.stdin.readline n=int(input()) arr=[list(map(int,input().split())) for _ in range(n)] visited=[False]*n res=1e9 def dfs(start,cur,cost): #시작점, 노드, 비용 global arr,visited,res if visited.count(True)==..

출처:: www.acmicpc.net/problem/1699 분류:: dp 1. 문제 이해 및 해결과정 - dp : i를 표현할 수 있는 제곱수의 합의 최소 개수 1 1 2 2 3 3 4 1 5 2(4+1) 6 3(4+1+1) 7 4(4+1+1+1) 8 2(4+4) 9 1(9) 10 2(9+1) 11 3(9+1+1) 12 3(4+4+4) 2. 풀이방법 1. [python] dp #제곱수의 합 #https://www.acmicpc.net/problem/1699 import sys import math sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*(n+1) for i in range(1,n+1): dp[i]=i for j in range(1,i): if..

출처:: www.acmicpc.net/problem/1149 분류:: dp 1. 문제 이해 및 해결과정 - 각 열에서 한 개씩 선택해서 단, 색상조건 고려해야함 - i가 빨강으로 칠해질때, i-1에는 초록이나 파랑 칠해져 있어야한다. - i가 파랑으로 칠해질때, i-1에는 초록이나 빨강 칠해져 있어야한다. - i가 초록으로 칠해질때, i-1에는 빨강이나 파랑 칠해져 있어야한다. dp[i][j] : 집i번까지 j색으로 칠했을 때 최소비용 => dp[i][r] = min(dp[i-1][g], dp[i-1][b]) + cost[i][r] ,g,b도 이와 같다 0 1 2 번 집 빨간색으로 칠해질 때, 26 40 83 초록색으로 칠해질 때, 49 60 57 파랑색으로 칠해질 때, 13 89 99 26 40 83 ..

출처:: www.acmicpc.net/problem/2193 분류:: dp 1. 문제 이해 및 해결과정 1) 자리수별로 풀이 1자리 일때 , 1 2, 10 3, 100 101, 4, 1000 1001 1010 5, 10000,10001,10010,10100,10101 끝자리가 1이면 0만 가능 끝자리가 0이면 , 0과 1 가능 0으로 끝나는 것 1로 끝나는 것 1 0 1 2 1 0 3 1 1 4 1+1 1 5 dp[n][2] dp[i][j]=길이가 i이고 j로 끝나는 것의 개수 dp[i][0]=dp[i-1][0]+dp[i-1][1] dp[i][1]=dp[i-1][0] 2) 규칙 - dp[i]=dp[i-1]+dp[i-2] 규칙을 찾을 수 있다. 2. 풀이방법 1. [python] dp #이친수 #https..