봉황대 in CS

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

* 본 글은 '컴퓨터 네트워킹: 하향식 접근 (Computer Networking: A Top-Down Approach) 8th edition'의 내용과 2023학년도 1학기에 수강한 '컴퓨터 네트워크' 과목 강의 내용을 함께 정리하여 작성하였습니다. 현재 수강하고 있는 '컴퓨터 네트워크' 강의에서 소켓에 대한 교수님의 설명을 듣고, 소켓과 포트의 관계에 대해서 머리가 빙글 뱅글 돌게 되었다. 지난 학기에 '네트워크 프로그래밍' 과목을 먼저 수강한.. 어쩌다 보니 선수 과목들을 역순으로 듣고 있는 나는(다들 엇학기는 하지 마세요) 소켓과 포트에 대한 어느 정도의 기본 지식이 있었지만, 그 개념들이 다 꼬이게 되었다. 그래서 중간고사 이전에 관련 내용들을 찾아보고 다시 정리하였고, 중간고사가 끝난 이 시점..

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

* 본 글은 '헤드퍼스트 디자인패턴(Head First Design Patterns) 개정판'의 내용을 참고하여 작성하였습니다. Chapter 3. 데코레이터 패턴에서의 예제 코드를 보며, 궁금증이 생겨 시도를 한 과정과 그것을 통해 깨달은 바들을 여기에 작성하려 한다. Decorator Pattern 데코레이터 패턴이 무엇인지에 대해서는 다음의 링크들을 참고하길 바란다. 1. 김베어씨 정리 GitHub - IT-Book-Organization/HeadFirst-DesignPattern Contribute to IT-Book-Organization/HeadFirst-DesignPattern development by creating an account on GitHub. github.com 2. 내 정리..

* 본 글은 '헤드퍼스트 디자인패턴(Head First Design Patterns) 개정판'의 내용을 함께 정리하여 작성하였습니다. GitHub - IT-Book-Organization/HeadFirst-DesignPattern: 'Head First Design Pattern'을 읽고 공부하며 정리하는 저장소 'Head First Design Pattern'을 읽고 공부하며 정리하는 저장소입니다. Contribute to IT-Book-Organization/HeadFirst-DesignPattern development by creating an account on GitHub. github.com 소프트웨어 개발 불변의 진리 아무리 디자인을 잘한 애플리케이션이라도 시간이 지남에 따라 변화하고 성장..

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