본문 바로가기

Algorithm/Dynamic Programming

 (11)
LCS 알고리즘 LCS 알고리즘 - 최장 공통 부분 수열 또는 최장 공통 문자열을 의미한다. - 최장 공통 부분 수열 : (ABCDEF, GBCDFE) -> BCDF, BCDE - 최장 공통 문자열 : (ABCDEF, GBCDFE) -> BCD 1. 최장 공통 문자열 특징 - 연속해서 같아야 한다. 점화식 - 만약 문자가 같다면 현재 각각의 문자열의 인덱스-1 위치의 값(그 전에 일치했는지 여부)에 + 1 을 해주면 된다. 시간복잡도 - O(NM) 예시 - 문자열1 : ABCDEF 문자열2 : GBCDFE - 두번째 인덱스에서 B가 같은데, 문자열1, 문자열2의 해당 인덱스에서 한칸씩 앞에서도 같은지 확인하고 더해주는 원리이다. A B C D E F 0 0 0 0 0 0 0 G 0 0 0 0 0 0 0 B 0 0 1 0..
못생긴 수 유형 파악 및 구현 이 문제는 생각해내는게 좀 어려웠던 것 같다. 못생긴 수는 2, 3, 5의 조합들을 의미한다. 못생긴 수의 리스트를 보면 1, 2, 3, 2x2, 5, 2x3, 2x2x2, 3x3, 2x5 이런식으로 진행된다. 즉 초기 못생긴 수를 넣고 (2, 3, 5) 이미 들어간 못생긴 수에 2, 3, 5를 곱하는 방식으로 진행된다. 구현을 하기 위해서는 2 or 3 or 5가 다음에 곱해져야하는 리스트 인덱스를 담는 변수 -> i2, i3, i5 결과마다 가장 작은 것을 뽑아서 리스트에 넣기 전 결과를 표현하는 변수 -> next2, next3, next5가 필요하다. 코드 # 찾으려는 인덱스 n = int(input()) # 못생긴 수 초기화 ugly = [0]*(n+1) # 첫번째 못생긴 수..
병사 배치하기 유형 파악 및 구현 예를 들어, [15, 11, 4, 8, 5, 2, 4]가 있을 때, 오른쪽으로 갈수록 수를 크게 만들면서, 리스트 내의 요소가 가장 많은 경우를 구하는 것이다. 이는 전형적인 다이나믹 프로그래밍의 문제 중 하나인 '가장 긴 증가하는 부분 수열 문제'이다. [15, 11, 4, 8, 5, 2, 4] dp 리스트는 아래와 같은 방식으로 채워진다. 4 - [1] : 마지막 요소 뒤에는 아무 요소가 없다. -> dp(n-1) 2- [1] : 2의 뒤에는 2보다 작은 요소가 없다. -> dp(n-2) 5 - [2] : 5의 뒤에는 2 or 4를 넣을 수 있다. -> dp(n-3) = dp(n-2) + 1 or dp(n-1) + 1 8 - [3] : 8의 뒤에는 (5, 2) or (5, 4)를 ..
퇴사 유형파악 및 구현 이 문제는 아이디어는 떠올리기 쉬웠으나 구현이 어려웠던것 같다. 아이디어 - 우선, 뒤에서부터 하나하나 확인을 한다. - 만약 걸리는 시간때문에 퇴사전 이 일을 마무리 못하는 경우라면 패스한다. - 가능하다면 추가를 한다. - 다음의 경우로 마지막날 전날 인터뷰에 대해서 점검을 하는데 예를들어, 7일까지 일을할 것이고 7일은 1일소요, 500원, 6일은 2일소요 100원이라고 가정하자 6일날 일하게 되면 6,7일은 일을 못하고 다음일은 8일부터 가능하다. 따라서 7일날 일하는 경우 vs 6일날 버는 돈 + 8일 이후에 버는돈 을 비교해 큰값으로 값을 기록한다. 이 후, 그 전날 , 그 전날 이런식으로 나아간다. 전형적인 DP문제이다. 하지만 헷갈렸던 거는, 기록을 하는 dp리스트는 크기..
정수 삼각형 유형 분석 이 문제 또한 전에 풀었던 금광문제처럼 사고의 전환이 필요하다. 1열에서 2열로 더한다 라기 보단 2열을 기준으로 1열에서 최선의 선택을 해 더한다로 생각하는게 낫다. 다만, 헷갈렸던 점은 대각선을 더해야하는데, 2차원 배열로 나타내면 대각선 표현이 어렵다는 점이다. 그걸 주의해서 잘 풀어야 하는것 같다. 코드 n = int(input()) m = int(input()) graph = [] graph.append([m]) for i in range(1, n): graph.append(list(map(int, input().split()))) dy = [-1, 0] for x in range(1, n): for y in range(len(graph[x])): max_value = 0 for i ..
금광 문제 금광은 N,M 행열로 구성되어 있다. 첫번째 열부터 시작해 마지막 열까지 이동하는데, 방문한 행에 있는 금을 캘 수 있다. 오른쪽 위, 아래, 옆 중 하나를 선택해 이동가능하다. 최대한 많이 캔경우 금의 양은? 유형 파악 및 구현 금광 (x, y)는 (x-1, y-1) or (x, y-1), (x+1, y-1) 중 하나와 더해 가장 크게 만들어야 한다. 첫번째 열부터 시작하니 이동 경로마다 값을 구하기 보단 생각을 역전해서 두번째 열에 있는 금들은 첫번째 열의 어떤 금들과 더해져야 가장 커지는가?에 대해서 생각하면 좋다. 1행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? 2행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가? ... 1행 4열은 3열의 금들 중 어떤 금이랑..
효율적인 화폐 구성 문제 주어진 코인을 이용해 문제에서 주어진 돈을 만들어라 유형 파악 및 구현 전형적인 DP문제인것 같다. 예를 들어 [2, 3]원을 활용해 5원을 만든다고 가정하자. 1원 만들 수 있는가? X 2원 만들 수 있는가? O -> 2%2 == 0 3원 만들 수 있는가? O -> 3%3 == 0 4원 만들 수 있는가? O -> 4%2 == 0 5원 만들 수 있는가? O -> 5%2 ==0 ? X -> 5%3 ==0 ? X -> (5-2)원은 만들 수 있는가? == 0? O -> 3원을 만드는 경우의 수 + 1 즉, 5원을 만들때, 2원이나 3원만으로는 만들 수 없다. 하지만 5-2 or 5-3원을 만들 수 있는지 체크 한 후 만들 수 있다면 그 값에 1을 더하면 된다. 코드 n = 3 result = 10 co..
바닥공사 문제 3가지 종류의 타일을 사용해 가로 N 세로 2인 바닥을 채울 때, 채울 수 있는 경우의 수를 구하라 유형파악 및 구현 타일의 종류는 2x1, 1x2, 2x2가 있다. N이 1일 때, 경우의 수는 한가지 경우이다. 1x2 N이 2일 때, 경우의 수는 세가지 이다 (1x2, 1x2), (2x1, 2x1), (2x2) N이 3일 때, - (1x2, 2x1, 2x1), (1x2, 2x2) : N(1) + (2x1, 2x1) or (2x2) - (1x2, 1x2, 2x1), (2x1, 2x1, 1x1), (2x2, 1x2) : N(2) + (1x2) 점화식을 만들어보면, check[n] = check[n-1] + 2*check[n-2] 이다. 코드 n = 10000 check = [0]*(n+1) check..

티스토리툴바