알고리즘 (60) 썸네일형 리스트형 [백준] 9251번 : LCS(Longest Common Subsequence) https://cryosleep.tistory.com/17 LCS란? Longest Common Subsequence=최장 공통 부분순서 그냥 댕쉬움. 문제 풀면서 인지한 동적 프로그래밍, Tabulation의 테이블 작성의 공통점. 정답을 구하기 위해 당장에는 무의미한것까지 맨땅부터 차근차근 다 해보는 것이다(당장에는 무의미하지만 그 무의미한게 답을 구하게 해줌). 두개의 문자열을 비교하는 것이므로 2차원 배열임. x축=문자열A, y축=문자열B 배열은 문자열 각각의 길이에서의 LCS의 길이로 구성됨. 비교되는 2개의 문자열의 타겟 문자가 같으면 dp[i][j]=1+dp[i-1][j-1] 비교되는 2개의 문자열의 타겟 문자가 다르면 dp[i][j]=max(dp[i-1][j], dp[i][j-1] from.. S-algo08 탐욕적(Greedy) 알고리즘 보호되어 있는 글입니다. School algo02 전수조사에서 조합에 관한것(작성중) 매개변수가 여러개 있는것은 체크와 대입을 위한 것이다. n개중 r개를 선택하는 문제인 조합, 3자리 짝수찾기 문제등은 트리를 내려가면서 이것은 넣고 저것은 넣지 않고, 이것은 넣고 저것은 넣지 않고의 과정을 수없이 반복하기 때문에 매개변수가 많아지는 것이다. 재귀 트리 그림을 그려가면서 이 과정의 디테일한 모습이 머릿속에 그려져야 한다. 그리고 강조하지만 체크없는 대입은 없다대부분임). 항상 조건문을 통해 체크가 이뤄지고 조건에 성립할시 대부분의 경우 대입이 일어난다. Solution1. 아래와 같이 해결가능하지만 매개변수가 많이 존재하는게 걸림. Java! import java.util.*; //index를 이용한 좀더 자유로운(내가 입력하는 n개의 수를 담을 real배열하나를 추가하여 n개의 수를 담.. School algo02 mergeSort, timsort 풀이코드 Merge sort에 관한 코드가 여러 폼이 존재하여 각각의 특징을 명확히 공부하기 위해 남겨놓는다. 파이썬으로 코딩하고 그것을 각각 자바 코드로 변환해 보았다. ###병합정렬1 가장 대표적인 폼의 병합정렬 def merge(arr, f, l): if(f School algo10 , 0-1배낭문제 보호되어 있는 글입니다. 배낭채우기 문제 0,1 배낭채우기 문제 출처:https://gsmesie692.tistory.com/113 내정리: 중요한 것은 Greedy이든 Dynamic Programming이든 같은 종류의 문제(최댓값을 구하라, 최소값을 구하라등)에 적용될 수 있는 해결책들이라는 것이다. 다만 탐욕적 방법이 안될때 동적 기법이 사용될 수 있다는 것이 차이점이다. 따라서 어떤 문제를 볼때 어느 하나만 생각하는 것은 옳지 않다. 모든 기법을 생각할 수 있는 것이 자연스러운 것이다. 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 흔히 알고리즘을 배.. School algo10 Dynamic programming 으로 다시 풀어본 can,how,count, best Sum (수정중) 보호되어 있는 글입니다. 재귀설계 중요코드모음 & 전수조사 재귀설계 연습의 중요 4가지 문제 비교 중요:무엇보다 재귀설계를 할때가 가장 곤혹이다. 많이 연습해 보는 방법밖에 없고 비슷한 유형의 문제를 두고 머릿속으로 그림을 그려가며 그 그림과 해당 코드의 내용을 비교하면서 그리고 문제간의 코드차이도 비교해 보면서 익숙히 하는게 장땡이다. 아래가 그 공부방법의 정확한 예시다. 피보나치와 막대기자르기의 Top-down방식 해결책에서 살펴본 코드로 바로 보이는 큰그림과 숨겨진 작은그림 def fiboTD(m,n): if(m[n]>0): return m[n] if(n=0): return m[n] if(n==0): q=0 else: q=-1 for i in range(1, n+1): q=max(q, p[i]+cuttingStickTd(p, n-i, m))#자식노드들 여럿을 비교하여 그 중가장큰것이 #부모노드의.. 이전 1 ··· 4 5 6 7 8 다음
