전체 글 (359) 썸네일형 리스트형 [백준] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 영상강의: https://fastcampus.co.kr/courses/210773/clips/ 영상보다 쉬운 해설: https://guy-who-writes-sourcecode.tistory.com/43 "dp를 어떻게 정의하는가가 상당히 어렵고 이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다." ==>>그동안 내가 공부했던 점화식을 구하는데 사용했던 최적의 원리를 적용하기 너무 어렵다(최적해의 부분해가 또다시 그것의 부분문제의 최적해가 된다는 것을 적용하기 힘듬). dp문제의 특징은 이미 이전의 값은 구해졌다고 가정하고 시작한다. 그 구해진 값을 통해서 이번값을 어떻게 구하는지만 해결하면 된.. [백준] 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 (수정중) 보호되어 있는 글입니다. 이전 1 ··· 40 41 42 43 44 45 다음
