emzei

계산 복잡도 (Çomputational Complexity)알고리즘의 분석특정 알고리즘의 효율 efficiency측정시간 복잡도 time complexity공간 복잡도 space/memory complexity문제의 분석일반적으로 계산복잡도 분석이라 하는 경우,어떤 문제에 대해 그 문제를 풀수 있는 모든 알고리즘의 하한(lower bound)을 결정 힙정렬 (Heapsort) 알고리즘완전 이진 트리 ( complete binary tree)트리 내부의 모든 노드에는 2개의 자식 노드가 존재하는 이진 트리모든 잎의 depth는 동일실질적 완전 이진트리depth(깊이) d-1까지는 완전이진트리이고,d의 노드는 왼쪽 끝애서부터 채워진 이진 트리힙의 성질 (heap property) : 어떤 마디에 저장된 값은..

Branch and bound ; “ 분기한정법 "공통점 w/ backtracking (되추적법) 문제 해결을 위해 상태공간트리(state space tree)가 사용됨차이점 w/ backtracking트리를 탐색하는 방법에 제한이 없음최적화 문제에서만 사용됨설계 전략노드가 유망한지 결정하기 위해 한 노드에서의 bound 값을 계산해야한다 (bound값 - 미래의 가치를 예측한 값)그 숫자는 해결책의 값의 bound(한정값)으로서, 해당 노드를 넘어 확장하면서 얻을 수도 있는 값만약에 해당 bound값이 현재 최적의 해결책보다 낫지 않은 경우에, 해당 노드는 non-promising(유망하지않음) ; 즉, 더 나은 경우 promising(유망함) Breath-first search (너비 우선 검색)검색..

Backtracking (되추적법) (사전 설명) Depth-First Search (깊이우선 탐색)Root 노드 선 방문 후, 그 후 자식 노드를 차례대로 방문 (Pre-order tree traversal) n-Queen problem(n=4) 4-Queens Problem : 4개의 Queen을 서로 상대방을 위협하지 않도록 4x4 체스판에 두는 문제. 4-queen 문제에 대한 상태 공간 트리 (모든 경우를 표시) 서로 상대방을 위협하지 않기 위해서, 같은 행/열/대각선 상에 위치하지 않아야 함.Brute-force Approach : 각 Queen을 각각 다른 행에 할당한 후, 차례로 점검.State Space Tree (상태공간트리) 를 이용root 노드에서 leaf 노드까지의 경로를 cand..

다이나믹 프로그래밍의 단점 --> 인스턴스를 더 작은 인스턴스로 쪼개어 재귀적으로 무제 해결최적화 문제를 푸는데 적합. 최적화 원칙이 적용되는지를 점검해보기만 하면 됨그러나 때로는 불필요하게 복잡. 0-1 Knapsack 해결 가능. ★ 탐욕적 접근법: 해당 단계에서 최적의 해를 구함 (locally optimal) 결정해야 하는 단계마다 최적의 해를 구하여, 최종적으로도 해답에 도달하고자 함허나, 반드시 local에서의 최적의 해가 global 에서의 최적의 해라고 보장할 수 없음 (항상 최적의 해답인지 검증이 필요함)최적화 문제를 푸는데 적합. 알고리즘이 존재할 경우 효율적. 알고리즘이 최적인지 증명해야함. Knapsack 문제는 풀지만, 0-1 Knapsack 문제는 풀 수 없음. 탐욕적 접근법의 ..

운영체제의 교착상태에 대처하는 방법은 크게 3가지가 있다.교착상태를 발생시키지 않는 것교착상태 발생 후 회복하는 것교착상태를 방지하는 것 이 중에서도, 발생시키지 않는 것은 다시 예방과 회피의 방법으로 나뉜다.예방 --> 교착상태의 발생 조건이 만족되지 않도록 함cf. 교착상태 발생 조건상호배재 (mutual exclusion)점유/대기 (hold and wait)비선점 (no preemption)순환대기 (circular wait)회피 --> 현재 및 미래에 교착상태가 발생하지 않도록 자원할당을 함 은행가 알고리즘은 교착상태 회피 방법 중 하나이다. (deadlock avoidance)교착 상태를 회피하는 것은, 미래의 자원 사용을 파악하여 순환대기 조건이 만족되지 않도록 하는 것이다. 참고 링크 - ..

> 난수를 사용하여 함수의 값을 확률적으로 계산하는 알고리즘.> 계산하려는 값이 닫힌 형식으로 표현되지 않거나 복잡한 경우에 근사적으로 계산할 때 사용 참고 링크 - https://ko.wikipedia.org/wiki/%EB%AA%AC%ED%85%8C%EC%B9%B4%EB%A5%BC%EB%A1%9C_%EB%B0%A9%EB%B2%95- http://statphys.ssu.ac.kr/monte/

동적 프로그래밍 (dynamic programming)분할 정복법과 유사문제를 더 작은 단위로 분할작은 단위를 먼저 해결하고, 결과를 저장하고, 후에 결과가 필요할 때 재계산 하지 않고 결과를 찾아다 씀 상향식 (Bottom Up)작은 단위로 나뉘어진 것들이 상관관계가 있는 경우 적합 (Ex. 반복적 피보나치)재귀적 관계식을 세워서 상향식으로 해결! 이항계수 구하기 (Binomial Coefficient)기본공식 관계식으로 표현된 식 분할정복법으로 구하게 되면 재귀 호출을 수행해야함동적 프로그래밍 설계 전략1단계 : 재귀 관계식 정립 2차원 배열을 만들어서 각 인덱스에 해당하는 값을 저장하여 그 다음 관계식에서 활용2단계 : 상향식 방법으로 문제 해결알고리즘 int bin2(int n, int k) { ..

분할 정복법 (divide-and-conquer)분할 => 해결하기 쉽도록, 문제를 여러개의 작은 부분으로 나눔정복 => 작게 나뉘어진 문제를 해결통합 => 필요에 따라 해결된 답을 모음==>> 하향식(Top-down) 접근법 Binary search using recursive method (이분검색, 재귀알고리즘)문제 : 크기가 n인 정렬된 배열에서 x가 있는지 결정하기입력 : 비내림차순으로 정렬된 배열(1~n), 찾고자하는 항목(x)출력 : x가 존재할 경우 해당 위치, 없는 경우 0 #include int goal; int array[10]={1,2,3,4,5,6,7,8,9,10}; int location(int start, int end) { int mid; if(start > end) retu..

알고리즘의 학습 목표Design알고리즘 설계 기법 학습Analysis알고리즘을 분석하여 시간/공간 복잡도 구함Comutational Complexity문제에 대한 하한을 결정 알고리즘(General) Step-by-step procedure for producing the solution to each instance유한한 단계를 통해서 문제에 대한 답을 구함cf. 연산은 효율성(+간결성)/명확성/종결성/입출력 알고리즘의 표기자연어복잡한 문제를 쓰기 어렵고, 알고리즘 이해가 어려우며, 프로그래밍 언어로 바꾸기 어려움프로그래밍언어자연어의 단점은 극복되었으나, 특정 언어에 종속의사코드 (pseudo-code)알고리즘은 대부분 의사코드로 표현직접 실행할 수 있는 프로그래밍 언어는 아니지만, 실제 프로그램과 가..

algorithm : applying a technique to a problem results in a step-by-step procedure for solving the problem. problem : a question to which we seek answer parameters : variables that are not assigned specific values in the statement of the problem. instance : each specific assignment of values to the parameters. solution : the answer to the question asked by the problem in that instance. key : ofte..