본문 바로가기

전체 글

 (359)
재귀설계 중요코드모음 & 전수조사 재귀설계 연습의 중요 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집합 자료구조로 알수있다. 크루스칼 알고리즘=굳이 그래프를 만들 필요 없음...
그래프의 탐색으로 부터의 응용: 연결성분(부분그래프,Connected component)과 신장트리(Spanning Tree, 모든 정점을 포함하는 트리) 보통 그래프 탐색의 두가지 방법으로 DFS, BFS를 배우고 나면 배운 탐색방법을 가지고 응용된 문제를 접하게 되는데 그중 널리 알려진 것이 연결성분(부분그래프Connected Component)과 신장트리(그래프의 모든 정점을 포함하는 트리,Spanning Tree)이다. 이번 포스팅은 기본적인 DFS, BFS코드가 응용에 들어가면서 어떻게 변형이 되는지를 중점으로 보려고 한다. #연결성분(부분 그래프)-탐색의 응용1. 탐색하여 부분그래프 리스트들의 리스트를 출력하는 것으로 표현됨 #신장트리-탐색의 응용2. 탐색중에 사용된 간선들을 출력하는 것으로 표현됨 1.부분그래프 (연결성분, Connected component) 우선 기본적인 DFS, BFS코드는 아래와 같다. def dfs(graph, star..
파이썬으로 DFS를 구현할때 SET의 상태변화에 대하여. 책에는 DFS를 아래와 같은 코드로 구성하였지만 graph={"A":{"B","C"},"B":{"A","D"},"C":{"A","D","E"}, "D":{"B","C","F"}, "E":{"C","G","H"}, "F":{"D"},"G":{"E","H"},"H":{"E","G"} } def dfs(graph, start, visited=set()): if start not in visited: visited.add(start) print(start, end=' ') nbr=graph[start]-visited for i in nbr: dfs(graph, i, visited) 내 혼자힘으로 구현한 코드는 아래와 같고 문제 없이 잘 동작하였다. graph={"A":{"B","C"},"B":{"A","D"},..

티스토리툴바