I about me

BFSDFS queue(FIFO)부모의 관계를 체크stack(FILO)Back edge를 신경(=사이클) - 앞 친구 이웃 다 넣음? - 걔 빼고 - 또 앞 친구 이웃 다 넣음? - 깊숙히- undirected graph → tree edge & back edge- directed graph →  tree, forward, back, cross edge// 코드 이해 // 코드는 cheating paper에 넣을 것// 코드는 cheating paper에 넣을 것 1. Shortest path on unweighted graph, undirected// 코드2. Finding Connected components// 코드3. Two-coloring graphs (biopartite)부모랑 반대, 같은 색..

그래프 알고리즘 내용그래프 데이터 구조종류매트릭스인접 리스트그래프 탐색BFS 및 응용DFS 및 응용탐욕적 그래프 알고리즘DP 그래프 알고리즘인접 메트릭스1) 그래프가 directed일 때, 2) 그래프가 undirected일 때, undirected 그래프의 경우, 각 노드 사이에 연결이 있으면 두 번의 표기만으로 충분함즉, (i, j)와 (j, i) 요소를 모두 채워넣을 필요가 없음그러므로 sparse(희소)하다인접 리스트1) 그래프가 directed일 때, 2) 그래프가 undirected일 때, 인접리스트 코드는 chatting paper에 그냥 적어둘 것!(수업 시간 언급을 거의 안 했기 정리는 안 할래... 그러나 혹시 모르니까) 인접 메트릭스 vs. 인접 리스트인접 메트릭스O(n^2)  인접 ..

그래프 알고리즘 내용그래프 데이터 구조종류매트릭스인접 리스트그래프 탐색BFS 및 응용DFS 및 응용탐욕적 그래프 알고리즘DP 그래프 알고리즘그래프그래프는 컴퓨터 과학의 통일 주제 중 하나입니다.그래프 G = (V, E)는 정점 집합 V와 V에서 온 순서 있는 또는 없는 정점 쌍으로 구성된 간선 집합 E로 정의됩니다.그래프와 네트워크의 예:도로 네트워크 모델링에서 정점은 도시나 교차점을 나타내며, 이들 중 일부 쌍은 도로/간선으로 연결됩니다.전자 회로에서, 교차점은 정점으로, 구성 요소는 간선으로 나타냅니다.소셜 네트워크월드 와이드 웹컴퓨터 프로그램 내의 제어 흐름항목 간의 쌍별 유사성'그래프 용어무방향 그래프에서 경로는 각 정점과 그 후속 정점 사이에 간선이 있는 정점의 시퀀스입니다.무방향 그래프는 모든..

Objectivespriority 큐 추상적 데이터 구조 및 그 동작에 대해 알아보자힙을 기반으로 한 우선 순위 대기열 작업의 복잡성에 대해 알아보자Greedy 프로그래밍 기법 설명문제 해결을 위한 Greedy 접근법 vs. Divide and ConquerGreedy 프로그래밍을 사용하여 문제를 해결해야 할 때를 식별Greedy 알고리즘이 최적의 솔루션을 제공한다는 것을 증명/반증Greedy 접근법을 사용하여 최적화 문제 해결ContentPriority QueueGreedy Approaches for Scheduling ProblemMinimizing Total Time in the SystemScheduling with DeadlinesHuffman code for data compressionGra..

예상문제 1. Divide and Conquer과 Dynamic Programming의 차이점을 서술하시오. Divide and Conquer Dynamic Programming공통점큰 문제를 작게큰 문제를 작게차이점- Top-down 접근 방식- 상호 관련이 없는 경우에 효율적근데 관련 있으면 비효율적- Bottom-up -  재 컴퓨팅 xx -> 저장 + look it up그러니까 관련 있는 거할 때 효율적예시Merge Sort, Quick SortLongest Common Subsequence, Matrix Chain Multiplication 예상문제 2. LCS(Longest Common Subsequence)시간복잡도: O(mn) - 여기서 m과 n은 각각 두 문자열의 길이를 나타냄- 두 문자..

Merge Sort만약에 코드가 주어주면 시간 복잡도를 도출할 수 있는가?MergeSort(Array, p, r): if p > r return q = (p+r)/2 mergeSort(Array, p, q) # A[p...q]를 모두 나누기 -> 정렬 mergeSort(Array, q+1, r)# B[q+1...r]를 모두 나누기 -> 정렬 merge(Array, p, q, r) # 병합 (1) divide - and - Conquer 이론과 연결지어 설명할 수 있는가?Divide-and-Conquer에 기반하여 Merge하여 정렬하는 방법시간 복잡도와 관련하여 각각 단계를 설명하면 다음과 같다.Divide - Conquer 배열을 두 개의 하위 배열로 나누고, ..

Sorting컴퓨터 과학 및 알고리즘 분야에서 중요한 개념으로, 주어진 데이터를 특정한 기준에 따라 순서대로 재배열하는 작업 Sorting의 응용예상문제 1. sorting 기반과 divide-and-conquer 기반의 큰 맥락  sortingdivide-and-conquer시간복잡도예시BestAverageWorstSearchLinear SearchOXO(1) O(n) O(n)1D Closest Pair (1차원 가장 가까운 쌍)Element Uniqueness (요소 고유성)Median and Selection(중앙값과 선택)Mode(최빈값)Binary SearchOOO(1)O(log n)O(log n)Convex hulls (볼록 껍질) 아래에 자세한 내용들을 정리해두었으니 참고해둘 것!더보기Lin..

Master Theorem재귀적인 방식으로 문제를 해결하는 경우에 자주 사용되는데, 특히 even split 알고리즘에 대한 재귀식을 다룰 때 유용어떤 알고리즘의 시간 복잡도 함수 T(n)이 다음과 같은 형태일 때,  다음의 1, 2, 3을 직관적으로 보면, 1. g(n)이 무거우면 g(n)이 수행 시간을 결정한다.2. g(n) 과 f(n)이 같은 무게이면 g(n)에 logn을 곱한 것이 수행 시간이 된다.3. f(n)이 무거우면 f(n)이 수행 시간을 결정한다. g(n)을 사용하는 이유)하나씩 차근히 살펴보자!ExampleMaster Theorem을 사용하여 주어진 재귀식을 해결해라.T(1) = 1 and T(n) = 8T(n/2) + n^2T(1) = 1 and T(n) = T(3n/4) + 10T(..

교재 예시 1번교재 예시 2번. factorial교재 예시 3번 과제 6번과제 7번

예상문제 - 기본 개념 문제: 답을 찾기 위해 제기된 질문ex) 리스트 S의 n개의 숫자를 오름차순으로 정렬하십시오. 매개변수: 문제의 설명에서 특정 값을 할당받지 않은 변수, 주로 문제의 입력 인스턴스: 입력 매개변수에 값이 할당된 특정 지정ex) S = [10, 7, 11, 5, 13, 8], n = 6 // 길이가 6인 S의 배열에 값 할당 해결책: 문제에 대한 답변ex) [10, 7, 11, 5, 13, 8] → [5, 7, 8, 10, 11, 13] 해결책· 문제를 해결하는 단계별 절차· 컴퓨터 프로그램의 아이디어· 언어(C++, 파스칼, 파이썬)나 환경(Mac, Windows, Linux 등)에 관계없이 항상 동일· 흥미로운 알고리즘은 일반적으로 지정된 문제를 해결해야함(구체화된 일반적 문제)..