Coding Test/DP

[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 분석 D[i] : 0~i까지 i를 포함하는 가장 길게 가하는 수열의 길이 A[i]를 i번째 수열의 값이라고 정의하면 D[k]는 A[i]>A[K]를 만족하는 최대 수열의 길이 즉, A[i]보다 작은 값을 지니고 있는 수열의 최장 증가 수열의 길이들 중 최댓값을 찾아 해당 값에 +1 한 값을 D[i]에 저장 D[i] = max({D[k]}) +1 (k=1~i-1) D 리스트를 맨 뒤에서부터 탐색해 최댓값과 동일 값을 가지는 최초 inde..

[18353번] 병사 배치하기(LIS, 이중 for문)

18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net LIS 문항 수열 길이 입력값 복잡도 18353 병사배치 1 ~ 1,000 1~10,000,000 n² 12738 가장 긴 증가하는 부분 수열2,3 1 ~ 1,000,000 1~1,000,000 -1,000,000~1,000,000 nlogn 14003 가장 긴 증가하는 부분 수열5 1 ~ 1,000,000 -1,000,000,000~1,000,000,000 nlogn 분석 N(1~2,000) : 이중 for문으로 풀이 D[i]=array[i]를 마지막..

[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing Subsequence 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) d = [0] for i in arr: if d[-1]

[2098번] 외판원 순회(TSP, 비트 마스킹)

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 외판원 순회 (모든 도시를 순회하는 최단 거리) n≤11일 경우: 브루트포스(O(n!)) n≤12일 경우: 백트래킹 n≤16일 경우: DP + BitMasking (n2∗2n) 분석 D[c][v] : 현재 도시 c, 현재까지 방문한 모든 리스트 v, 앞으로 남은 모든 도시를 경유하는데 필요한 최소비용 점화식 : D[c][v] = min(d[c][v], d[i][v|(1

[11049번] 행렬 곱셈 순서 (행렬 곱 연산 횟수의 최솟값 구하기, DP)

11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 분석 풀이 import sys imput=sys.stdin.readline # 행렬의 갯수 n=int(input()) # 행렬 m=[] # 최소 연산 횟수 저장 리스트 d=[[-1 for j in range(n+1)] for i in range(n+1)] m.append((0,0)) for _ in range(n): x,y=map(int, input().split()) m.append((x,y)) def execute(s,e): result=sys.m..

[9252번] 최장 공통 부분 수열 찾기(LCS)

9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS Longest Common Subsequence 분석 풀이 import sys input=sys.stdin.readline sys.setrecursionlimit(10000) a=list(input()) a.pop() b=list(input()) b.pop() # 점화식 테이블 d=[[0 for j in range(len(b)+1)] for i in range(len(a)+1)] # LCS 저장 리스트 re..

[2193번] 이친수 구하기

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이1 """ 이진수 0으로 시작하지않음 1이 두번 연속으로 나타나지 않음. 11을 부분 문자열로 갖지않음 이친수 : 1, 10, 100, 101, 1000, 1001 이친수X : 0010101, 101101 N(1~90)자리의 이친수의 개수 구하기] """ import sys input=sys.stdin.readline n=int(input()) d=[[0 for i in range(2)] for j in range(n+1)] d[0][0]=0 # ..