봉황대 in CS

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. Greedy Algorithms 답을 찾기 위해서 선택을 반복하는 알고리즘이다. 비교적 간단한 기준으로 답을 계속 골라 담고, 이를 바꾸지 않는다. Minimum Spanning Tree 모든 node를 포함하며, edge cost가 최소가 되는 connected acyclic graph 찾기! Given a Graph, find Subset of Edges so that a Connected Graph results with Minimum Sum of Edge Costs. - minimum : edge cost가 최소가 되는 - spanning : 전체를 덮는, 즉 모든 node를 포함하는 Input..

* 본 글은 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)를 실행하면 이것이 종료할지, 아니면 영원히 수행될..

백준 2224번을 풀며 플로이드-와샬 알고리즘을 사용할 때 주의해야 할 점을 깨닫게 되었고, 이를 잊지 않기 위해서 이렇게 글로 남긴다. 플로이드-와샬 알고리즘 이 알고리즘이 무엇인지에 대해서는 이전에 작성한 글을 참고하길 바란다. [알고리즘] 플로이드-와샬(Floyd-Warshall) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 '거쳐가는 정점'을 기준으로 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘이다. ( ↔︎ 다익스트라 : 하나의 정점에서 출발했을 때 다른 모 eunajung01.tistory.com 문제 2224번: 명제 증명 첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전..

정렬 알고리즘들에 대하여 알아보던 중, 합병 정렬(merge sort)과 퀵 정렬(quick sort)이 분할 정복 알고리즘 중 하나임을 깨닫고 먼저 분할 정복에 대해 정리하기 위하여 이 글을 작성한다. 분할 정복 (Divide-and-Conquer) '쪼개서 풀고 합하기' : 문제를 잘게 쪼개는 분할(Divide) + 문제를 풀어서 합하는 정복(Conquer) 분할 정복이란, 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 즉, 문제를 작은 2개의 문제로 분리한 후 각각을 해결한 다음, 그 결과들을 모아서 원래의 문제를 해결하는 전략을 말한다. (Top-down, 하향식 접근법) 조건 1. 문제를 쪼개 나가는 과정에서, 큰 문제와 작은 문제의 구조가 동일하거나 비슷해야 한다. =..