분류 전체보기 (341) 썸네일형 리스트형 다이나믹 프로그래밍 Dynamic Programming 다이나믹 프로그래밍 Dynamic Programming Dynamic Programming의 개념 큰 문제를 작은 문제로 나누어 문제를 푸는 기법 divide and conquer 기법과 달리 작은 문제의 중복이 발생하지 않는다. 분할된 모든 작은 문제들은 한번만 풀어야 하기 때문에 작은 문제의 정답은 구한 뒤 메모해 둔다. 그리고 큰 문제를 풀다가 동일한 작은 문제가 나타나면 앞에 메모한 작은 문제의 결과값을 이용한다. Dynamic Programming의 조건 작은 문제가 반복적으로 일어나는 경우 같은 문제를 구할 때마다 결과값이 같은 경우 메모이제이션 Memoization 한번 계산한 작은 문제의 결과값을 저장해두는 것 Bottom-up 구현 def fibonacci_bottom_up(n): if .. 이진탐색트리 Binary Search Tree 탐색, 삽입, 삭제, 순회 search, insert, delete, traverse 구현하기 이진탐색트리 Binary Search Tree 이진탐색트리의 개념 각 노드의 왼쪽 서브트리에는 현재 노드보다 작은 값을 가진 노드만 있다. 각 노드의 오른쪽 서브트리에는 현재 노드보다 큰 값을 가진 노드만 있다. 중복 노드가 없다. inorder traverse를 한다 (왼쪽 - 루트 - 오른쪽) → 오름차순 정렬 가능 class Node: def __init__(self,value): self.value = value self.left = None self.right = None class BinarySearchTree: def __init__(self): self.root = None def setRoot(self,value): self.root = Node(value) 탐색 Search class .. Hash Table : open addressing Hash Table : open addressing 성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. open addressing 방식으로 충돌을 해결하는 Hash Table을 C로 구현하였습니다. problem • m = 37 • Hash functions (not exactly same as the previous open address hash functions) linear probing: h(k, i) = (h'(k) + i) mod m where, h'(k) = k mod m quadratic probing: h(k, i) = (h'(k) + c1i + c2i2 ) mod m where, h'(k) = k mod m, c1 = 1, c2 =.. 분할 정복 Divide and Conquer 알고리즘으로 행렬 곱셈 matrix multiplication 풀기 분할 정복 Divide and Conquer : 행렬 곱셈 matrix multiplication problem Program the divide and conquer matrix multiplication using 1) standard algorithm 2) recursion For the two cases 1) and 2), Compare the number of computations (multiplication, addition, and subtraction) between 1), 2) cases. In the matrix computation of C = A×B, matrices A and B are filled with rand()%1000, execute srand(time(NULL)) f.. 연결리스트 삽입, 삭제, 출력 Linked List insert delete print 구현하기 연결리스트 Linked List 성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 들으며 수행한 과제입니다. problem Write functions which perform according to the following descriptions. The input to each function is a linked list of integers. a) insert - Inserts an integer x to the front of a linked list. e.g.) insert(lst, x) where lst is a pointer to a linked list and x is an integer. b) delete - Deletes 2 nd last integer x.. 합병 정렬 : Merge Sort 내림차순으로 구현하기 합병 정렬 Merge Sort 성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. 배열을 내림차순으로 정렬하는 합병 정렬을 C로 구현하였습니다. input and output conditions Test the function with the following three types of integer inputs. int A[100] : filled with rand()%1000, execute srand(time(NULL)) first, (stdlib.h, time.h should be included) (Duplicate keys are ignored.) int A[100] : already sorted (Write a function for fil.. 버블 정렬 Bubble Sort 오름차순으로 구현하기 버블 정렬 Bubble Sort 성균관대학교 소프트웨어학과 조대호 교수님의 2020년도 2학기 알고리즘 수업을 듣고 수행한 과제입니다. 값을 오름차순으로 정렬하는 버블 정렬을 C로 구현한 코드입니다. pseudo code BUBBLE_SORT(A): 1. for i = 0 to A.length 2. for j = 0 to A.length-1 3. if A[j] > A [j+1] 4. swap A[j] and A[j+1] input and output conditions /* - Test the function with the following three types of inputs. 1) int A[100] : filled by rand()%1000, execute srand(time(NULL)) fir.. Hash Table : separate chaining Hash Table : separate chaining 성균관대학교 소프트웨어학과 조대호 교수님의 알고리즘 수업을 들으며 수행했던 과제입니다. rand() 함수로 랜덤 값들을 뽑아 해시 테이블에 적절한 해시 함수를 적용하여 삽입하는 코드입니다. 해시 함수는 전역 변수 N 의 값으로 설정할 수 있습니다. source code #define _CRT_SECURE_NO_WARNINGS #include #include #include typedef struct Node { int key; int value; struct Node* next; } Node; typedef struct listItem { Node* head; Node* tail; int length; } ListItem; ListItem* hash.. 이전 1 ··· 34 35 36 37 38 39 40 ··· 43 다음
