본문 바로가기

분류 전체보기

 (401)
배낭채우기 문제 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을 쪼개는 방법은 여러가지다..
동적프로그래밍의 개념과 기본 개념을 잡아주는 피보나치 문제 동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻이 아니라 테이블을 만든다는 뜻입니다. 그리고 전혀 다이나믹하지도 않습니다. 그래서 어떤 서울대 교수님은 동적 프로그래밍 대신 기억하기 프로그래밍이라는 용어를 쓰기도 합니다. 재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해 이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법입니다. 메모이제이션이 동적 프로그래밍 중 하나입니다. 알고리즘을 짤 때 분할정복 기법을 사용하는 경우가 많습니다. 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법인데요. 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사..
파이썬의 출력형식과 기타자잘자잘 한것. 꼭 익숙히 하고 있을것! 보통 print문으로 출력을 할때는 형식이 없게 결과값이 나올수도 있고 형식을 갖추어 결과값이 나올수도 있다. 하지만 한가지 확실한 것은 for i in graph 와 같은 for문에서 i 에 오는 것은 작은따옴표와 같은 형식이 없는 문자가 i자리에 온다는 것이다. 예시와 그의 결과를 첨부한다. graph={'A': {('B',29),('F',10)}, 'B':{('A',29),('C',16),('G',15)}, 'C':{('B',16),('D',12)}, 'D':{('C',12),('E',22),('G',18)}, 'E':{('D',22),('F',27),('G',25)}, 'F':{('A',10),('E',27)}, 'G':{('B',15),('D',18),('E',25)} } def testing(..
Shortest Path(최단경로)알고리즘: 다익스트라(Dijkstra), 벨만-포드(Bellman-Ford), 플로이드 와샤(Floyd Warshall) 보호되어 있는 글입니다.
Union-Find집합 자료구조와 MST의 크루스칼, 프림 알고리즘 1. 크루스칼 알고리즘이란? "사이클을 이루지 않는 선에서 n-1개 간선을 탐욕적으로(가중치 순으로) 선택해 나가는 MST알고리즘. 사이클형성여부는 Union-find집합 자료구조로 판별 2. 프림 알고리즘이란? "정점을 탐욕적으로 n개 선택해 나가는 알고리즘이다. 구체적인 방법은 처음에 임의의 정점을 선택하고 선택된 정점을 중심으로 dist배열을 매번갱신하는 것이다." " 이렇게 기억해 둔다. 좀 더 자세히는 최소신장트리를 해결하는 탐욕적 알고리즘의 하나로 n-1개의 간선을 선택할때까지 가중치 순으로 정렬된 간선을 사이클을 이루지 않는 선에서 하나씩 선택해 가는 알고리즘이다. 여기서 사이클을 이루는지의 여부는 Union-Find집합 자료구조로 알수있다. 크루스칼 알고리즘=굳이 그래프를 만들 필요 없음...

티스토리툴바