봉황대 in CS

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Proof of Correctness of Sorting 'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가? - 입력 값 : a[0], a[1], ... , a[n-1] - sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1] 조건 1: 값이 없어지거나, 새로 생기면 안된다. (집합 조건) {a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]} 조건 2: 값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다. b[0] < b[1] < ... < b[n-1] Merge Sort Merge ..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Proof of Correctness of Sorting 'Sorting이 되었다'라고 말할 수 있으려면 어떠한 조건들이 만족되어야 하는가? - 입력 값 : a[0], a[1], ... , a[n-1] - sorting이 끝난 후 배열에 저장된 값 : b[0], b[1], ... , b[n-1] 조건 1: 값이 없어지거나, 새로 생기면 안된다. (집합 조건) {a[0], a[1], ... , a[n-1]} = {b[0], b[1], ... , b[n-1]} 조건 2: 값 기준, 오름차순 정렬된 순서로 저장되어 있어야 한다. b[0] < b[1] < ... < b[n-1] Selection Sort by..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. - 입력 배열 arr에는 같은 값이 존재하지 않으며, 값 기준 오름차순 정렬되어서 저장되어 있다고 가정하자. - x는 우리가 찾으려고 하는 값이다. Binary Search by While Loop int binarySearch(const int arr[], int size, int x) { int left = 0; int right = size - 1; while (left x이라는 것은, x 값이 arr[0], arr[1], ... , arr[mid-1] 중에 존재한다는 것과 같다. → binarySearch(arr, mid, x)가 정확하다고 가정한다면, 이는 i를 반드시 return 한다. → ..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Mathematical Induction, 수학적 귀납법 'P(n)이 모든 자연수 n에 대해서 참이다'라는 것을 보이기 위해 사용하는 증명 방법 중 하나이다. 수학적 귀납법의 기본형 P(1)이 참이고, P(n-1) → P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다. Base: P(1) Step: P(n-1) → P(n) 수학적 귀납법의 강한 형태 P(1)이 참이고, P(1) ∧ P(2) ∧ ... ∧ P(n-1) → P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다. Base: P(1) Step: P(1) ∧ P(2) ∧ ... ∧ P(n-1) → P(n) 명제 P → Q의 의..

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. The Halting Problem 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행을 시킨다면(M(X)) 이 프로그램은 종료하는가? 'Halting Problem을 푼다'는 것은 M과 X의 모든 경우에, 어떠한 프로그램이 반드시 종료하는지, 아니면 영원히 수행될지(e.g., 무한 루프)를 해당 프로그램을 돌려보기 전에 판별할 수 있다고 하는 것과 같다. → Halting Problem은 풀 수 없다. The Proof by. Alan Turing 가정: 프로그램 D는 존재한다 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 이것이 종료할지, 아니면 영원히 수행될..