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

PPoPP '20 XIndex | Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming PPoPP '20: Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming February 2020 454 pages Copyright © 2020 ACM Permission to make digital or hard copies of all or part of this work for personal or classroom use is dl.acm.org Learned Index T..

2022 IEEE 38th IDCE Separation or Not: On Handing Out-of-Order Time-Series Data in Leveled LSM-Tree LSM-Tree is widely adopted for storing time-series data in Internet of Things. According to conventional policy (denoted by $\pi_{c}$ ), when writing, the ieeexplore.ieee.org Apache IoTDB - leveled LSM-Tree based, high-performance data engine tailored for time-series data - separation policy (πs, ..

안녕하시와요 거의 4달 만에 블로그를 쓰는데.. 그동안 많은 일이 있었지만 줄줄이 쓰기에는 시간 아까우니 요약하자면. 그동안 그저 막연하게 백엔드 서버 개발자를 향했던 것에서 벗어나 대학원이라는 선택지를 열어두게 되었고, 이번 여름방학부터 DCCL(Data Centric Computing Lab)에서 학부 연구생으로 살고 있다. 7월 3일부터 출근을 시작했으니 연구 생활을 시작한 지 이제 한 달 반 정도가 지난 것인데 이전까지 교수님께서 매주 보내주시는 LSM-Tree 관련 논문들을 읽고 분석하고 있었고, 2주 전부터 주제를 받아서 연구를 진행하고 있다. 그동안 논문들을 읽으면서 들었던 생각은 다음과 같다. 1. 해결법들은 생각보다 거창하지 않다. (알고 있던 자료구조들을 응용 또는 새로운 protoco..

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

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