CS (21) 썸네일형 리스트형 [COSE214] Data structures for disjoint sets disjoint set이란 intersection이 공집합인, 서로 공통된 원소를 가지지 않은 두 개 이상의 집합을 말하는 것으로 disjoint set data structure은 collection of disjoint set을 의미한다. disjoint set data structure은 3가지 연산을 제공하는데, make-set(x)는 x를 멤버로 하는 new set을 만드는 연산이고, union(x,y)는 x와 y를 각각 가지는 두 집합을 하나로 합치는 연산이며, find-set(x)는 x를 포함하는 집합을 찾아 그 집합의 대표 원소를 반환하는 연산을 말한다. 이 때 이 연산들의 time complexity는 항상 2개의 parameter m, n에 의해 정의된다. n은 make-set ope.. [COSE214] Matroid A matroid and greedy algorithms optimization problem의 구조가 matroid라면, 그 문제는 greedy algorithm을 통해 최적해를 찾을 수 있다. 그러나 optimization problem이 greedy algorithm을 통해 해결된다고 해서 해당 문제의 구조가 항상 matroid 인 것은 아니다. Unit task scheduling problemunit task scheduling problem이란 a1부터 an까지 작업시간이 1이 걸리면서 각각 다른 deadline과 지키지 못했을 때 발생하는 penalties가 존재하는 여러 unit task들이 있을 때, penalties의 합이 최소화 되도록 작업 순서를 설계하는 것을 말한다. 이러한 uni.. [COSE214] Dynamic Programming, Greedy Algorithm Dynamic Programming으로 문제를 해결하기 위해 문제가 갖춰야 할 structural properties에 대해서 서술하고, DP로 해결할 수 있는 문제의 예시에 대해 서술하시오. Dynamic Programming으로 해결할 수 있는 문제의 예시에는 두 개 이상의 assembly line에서 여러 작업들을 수행하여 최소 시간 또는 비용으로 제품을 완성하는 문제인 Assembly line scheduling problem, 여러 개의 행렬을 곱하는 과정에서 최소한의 곱셈 연산을 수행하는 최적의 순서를 찾는 문제인 Matrix chain multiplication problem , 한정된 용량을 가진 배낭에 최대한 가치 있는 물건을 넣는 문제인 knapsack problem 등이 있다. DP.. [COSE214[] Heap Sort Max Heap의 조건과 구조에 대해 서술하시오. Max heap이 되기 위해서는 먼저 1) heap의 shape이 binary tree의 무조건 앞쪽에서부터 순서대로 노드를 채우는 almost complete binary tree 형태여야 한다. 2) 그리고 항상 위쪽 node가 아래쪽 node보다 큰 max heap property를 갖추어야 한다. 이렇게 형성된 almost CBT의 index로는 특정 node의 번호가 i라고 할 때 parent node는 i/2, left node는 2i, right node는 2i+1이라는 index를 가진다. 또한 height of a node는 leaf에서 0이고, upwards로 가며 숫자가 커진다. depth of a node의 경우 root에서 0이고.. [COSE214] Tree, Graph 정의 [COSE214] Hiring problem hiring problem은 computational problem은 아니지만 randomized algorithms의 아이디어를 이용하는 문제이다. 회사에서 n명의 candidate를 인터뷰하여 hire할지, fire할지를 정한다고 하자. 이 때 모든 candidate는 모두 distinct competitiveness를 가지고 있고, 우리는 회사가 hire 시 지불해야하는 총 비용을 계산하고자 한다. 인터뷰 비용: Ci / hire 비용: Ch / fire 비용: 0best case: nCi + 1 Ch : 첫번째 면접자가 가장 competitive 한 경우worst case: nCi + n Ch : 마지막 면접자가 가장 competitive 한 경우 이 때 평균적으로 얼마나 많은 candidat.. [COSE214] Sort: Merge Sort, Quick Sort Divide&Conquer approach로 알고리즘을 디자인 하는 방법에 대해서 서술하시오. Divide&Conquer 접근은 문제를 나눌 수 없을 때까지 나누어서 각각을 푼 후 다시 합병하여 문제의 답을 얻는 알고리즘이다. 이는 1) Divide 단계에서 문제를 더 이상 나눌 수 없을 때까지 분할하여 작은 부분문제들을 만든다. 2) Conquer 단계에서 분할된 부분 문제를 재귀적으로 해결하며, 3) Combine 단계에서 분할된 부분 문제를 결합하여 최종 해결책을 도출한다. Divide&Conquer 원리를 이용한 알고리즘에는 대표적으로 merge sort, quick sort가 있다. Merge Sort란 하나의 배열을 두 개의 균등한 크기로 분할하고, 두 부분을 합치면서 배열을 정렬하여 전체.. [COSE214] 알고리즘 기초 개념 알고리즘이란 무엇이며, 이가 가지는 특성과 구성요소에 대해 서술하시오. 알고리즘을 통해 모든 computational problem을 solve 할 수 있는가?Computational problem은 어떠한 input이 주어졌을 때 어떠한 output이 기대되는지를 명확하게 specification 한다. 이 때 computational problem은 여러 가지 형태의 입력 데이터인 instance를 가질 수 있다. 알고리즘이란 computational problem에서 정확한 output을 계산하기 위해 수행해야 할 작업에 대한 명확한 설명으로, 1) finiteness를 가져 유한한 단계의 수를 가져야 하며, 2) 주어진 문제의 모든 instance에 대해 올바른 output을 계산하기 위한 cor.. 이전 1 2 3 다음
