본문 바로가기

분류 전체보기

 (381)
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))#자식노드들 여럿을 비교하여 그 중가장큰것이 #부모노드의..
DP 기본문제인 막대기 자르기(백준에 없는문제) 코드&그림매칭 자식들간 비교를 하여 그 중 최대값을 반환하는 코드 1. 막대기 자르기 문제의 일반화 나누어지는 대상이 1차이로 나누어지고 각각의 값(길이)에 대한 가치 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할 수 있다. 좀더 일반화 나누어지는 대상이 n차이로 나누어지고 각각의 값(길이)에 대한 가치가 부여되는 문제라면 재귀의 기저사례로부터 올라오면서 차례차례 구할수 있다. Bottom-up 방식으로 해결: 반복문을 사용하여 값을 1부터 시작하여 1일때의 최대 가치, 2일 때의 최대가치를 차근차근 구하여 이전에 얻은 값을 다음에 얻을 값을 계산할때 이용한다. 값이 가장 작을 때 그 값을 구성할수 있는 경우는 오직 한가지 뿐임을 이용한것. 예를들어 숫자 50을 쪼개는 방법은 여러가지다..

티스토리툴바