포도가게의 개발일지

신장트리(spanning tree)란? - 간선의 개수 E가 노드(V)의 개수 n보다 n-1인 graph를 의미 한다. 왼쪽 그래프는 V(노드)의 개수가 5개지만 edge(간선)의 개수가 7개 이며 cyclic graph이다 출처 : 유투브 주니온TV https://www.youtube.com/watch?v=jQH2wrz04io 왼쪽 그래프는 간선의 개수가 3개를 지워 노드의 개수가 5이며 간선의 개수가 4인 acyclic graph이다 출처 : 유투브 주니온TV MST(Minimum cost spannig tree)란 가중치가 있는 간선이 있을때 cyclic graph -> acyclic graph로 만들기 위한 간선의 최소 가중치를 찾는 방법이다. 최적을 선택하는 방법으로는 프림 알고리즘과 크루스칼..

LCS란? - Longest Common Subsequence 최장 공통 부분 수열, 최장 문자열을 찾는 것이다 - X[ ~ ], Y[ ~ ], Z[ ~ ] 일때 - Xm = Yn이면 Zk = Xm = Yn이고 Z(k-1)은 X(m-1)과 Y(n-1)의 LCS이다 첫번째 정의로 인해 = (1+matrix(i-1][j-1]) = 1 + max(LCS(X(m-1)),LCS(Y(n-1))) - Xm /= Yn이면, Zk /= Xm은 Z가 X(m-1)과 Y의 LCS임을 의미한다. - Xm /= Yn이면, Zk /= Yn은 Z가 Y(n-1)과 X의 LCS임을 의미한다. 두 정의로 인해 = max(matrix[i][j-1],matrix[i-1][j]) https://www.acmicpc.net/problem/925..

다이나믹 프로그래밍이란? - 큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법 - 작은 문제의 값을 재활용 하여 상당한 시간복잡도를 줄 일 수 있다 - 대신 메모리를 사용하여 메모리 사용량이 증가한다 - 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization) - F(n) = F(n-1) + F(n-2)과 같이 점화식 또는 수학적 귀납법으로 적용되는 문제에 적용 할 수 있다. 대표적인 문제로는 피보나치 수열이 있다. 접근 방법으로는 top->down 형식과 bottom -> up 형식이 있다. 피포나치 수열이란? 1 = 1 2 = 2 3 = 3 = 1 + 2 4 = 3 + 2 = 1 + 2 + 2 와 같이 F(n) = F(n-1) + F(n-2)를 수학..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 1. 위상정렬 - 정해진 순서에 위반되지 않는 경우의 수를 정렬 - DAG(directed acyclic graph) 형태에서만 사용 가능하다(순환되면 안된다.) - 선행된 조건이 이루어지지 않으면 발생할 수 없음 - 자동차를 만들기 위해 a,b부품이 필요할때 a 부품을 만들려면 또 다른 순서를 이행하여 조립하여야 한다. 때문에 자동차를 만들기 위해서는 ..

def bfs(graph, start_node): visit = list() queue = list() queue.append(start_node) while queue: node = queue.pop(0) if node not in visit: visit.append(node) queue.extend(graph[node]) return visit def dfs(graph, start_node): visit = list() stack = list() stack.append(start_node) while stack: node = stack.pop() print(node) if node not in visit: visit.append(node) stack.extend(graph[node]) return v..

합병 정렬(merge sort) 알고리즘의 구체적인 개념 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 합병 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. 합병 정렬의 과정 추가적인 리스트가 필요하다. 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. 합병 정렬에서 실제로 정렬이 이루어지는 ..

퀵정렬은 분할과 정복의 알고리즘이다 1. 특정값(pivot)을 기준으로 작은값과 큰값을 나누면서 정렬을 하는 방법 2. 시간복잡도 : O(nlogn) 3. 특정값을 한쪽으로 치우쳐져 잡거나 잘못 잡으면 O(n^2)에 수렴된다 ## 배열 swap 함수 def swap(arr, a,b): temp = arr[a] arr[a] = arr[b] arr[b] = temp ## 퀵 정렬 def Quicksort(arr, start, end): if start >= end: ##더 이상 나눌게 없으면 리턴으로 마무리 return pivot = start ##pivot 변수를 가장 좌측으로 시작했음 기준이 되는 값 left = start + 1 ##이미지와 달리 저는 pivot값을 좌측 끝으로 시작했습니다. right..

더보기 #include #include struct node{ int data; struct node *next; }; void addFirst(struct node *head1, int data) // head1 head노드의 주소값 { struct node *newNode = malloc(sizeof(struct node)); newNode->next = head1->next; //1번 2번노드 연결되어잇을때 1.5번노드를 사이에 넣어주기위해 1번노드에 저장되있던2번주소를 1.5번에 넣어줌 head1->next = newNode;//1.5번주소를 1번 next에 넣어줌 newNode->data = data;//1.5번 data 입력 } int main(void) { struct node *head =..