Computer Science

(C++) 백준 1260번 [DFS와 BFS]

오랜만에 그래프 문제를 풀었다. 그래서 그런지 조금 낯설었지만 기본적인 문제라 나름 괜찮았다. 아주 전형적이고 기본적인 DFS, BFS문제라 가볍게 풀어보기 좋은 것 같다. 1. 문제 해결방법 구상 - DFS는 스택을 이용, BFS는 큐를 이용. (DFS에서 굳이 스택을 이용하지 않고 재귀를 이용해도 됨, 근데 한번 스택으로 구현해보았다.) - DFS와 BFS의 관건은 언제 노드 방문 처리를 하고, 컨테이너에서 노드를 pop하는 지를 잘 고민해야함. - DFS에서 스택을 이용해서 구현을 한다면, 더 이상 깊은 depth로 갈 수 없을 때( 더이상 edge가 없는 node에 이르렀을 때)를 어떻게 처리해주느냐가 중요. - 뿐만 아니라 부모 노드로 다시 돌아갔을 때, 갈 수 있는 또 다른 node가 있는 지..

(C++) 백준 3613번 [Java vs C++]

오랜만에 알고리즘 포스팅이다. 생각보다 여러 케이스들을 생각하면서 일일이 반례를 찾아주어야 하는 문제라 꽤나 까다로웠던 것 같다. 1. 문제 해결 방법 구상 1. 일단 어떻게 입력이 들어올지 모른다. Java 형식으로 들어올 수도, C++ 형식으로 들어올 수도, 이도저도 아닌 형식으로 들어올 수도 있다. 2. 이도저도 아닌 케이스를 찾아내는 것이 관건이다. - 일일이 다 찾아서 if문으로 걸러내야한다. (1) 첫번째 글자가 _나 대문자로 시작하는 경우 (ex. _asd, Asd) (2) 마지막 글자가 _로 끝나는 경우 (ex. asd_) (3) C++의 경우 _바로 뒤에 대문자가 오는 경우 (ex. asd_Asd) (4) (3)의 경우랑 비슷하긴 하나 _바로 뒤가 아니라 중간 글자가 대문자인 경우 (ex..

[데이터베이스] Introduction

본 포스팅은 부산대학교 정보컴퓨터공학과 이기준 교수님의 수업을 참고하였습니다. Database 란? 데이터베이스는 실세계에 있는 어떠한 정보를 컴퓨터 속으로 집어넣는 것이다. 따라서 그런 정보들을 formal하게 modeling하는 것이 중요하다. (formal 하다는 것은? 수식으로 표현이 될 수도 있고, diagram 이나 algebra로 표현이 될 수 있다.) Database가 Real World 에서 Computer World 로 변환되는 과정은 다음과 같다. 1. 실세계를 정확하게 이해하고 이를 modeling 한다. 2. 구현한다.(design and modeling) 그 후, Computer World로 변환된 database를 3. 적용하여 활용하고 관리한다. (Application and..

[운영체제] File System Implementation

본 내용은 [Operating Systems : Three Easy Pieces] 및 부산대학교 안성용 교수님의 운영체제 수업을 참고하였습니다. 파일 시스템을 구현하려면 어떻게 해야할까. VSFS(Very Simple File System)이라는 가상의 파일 시스템을 예로 들어 이해해보자. VSFS VSFS라는 이 가상의 파일 시스템의 특징을 먼저 살펴보자면, - Disk를 블록 단위로 나눔(한 블록당 4KB) - 블록의 사이즈는 sector size의 배수 - 대부분의 disk block 들은 user data를 저장하기 위해 사용됨 - 아주 작은 부분만 file system의 metadata를 저장하기 위해 사용됨 또, inode를 어떻게 저장할지도 고려를 해야한다. 각각의 inode는 file의 m..

[운영체제] File System

본 내용은 [Operating Systems : Three Easy Pieces] 및 부산대학교 안성용 교수님의 운영체제 수업을 참고하였습니다. power가 꺼진 후에도 data를 보관할 수 있도록 하는 것이 Persisten Storage의 개념이며 대표적으로 - Hard disk drive(HDD) - Solid-state storage device(SSD) 가 있다. CPU와 Memory에 했던 것처럼 이 storage에도 가상화가 필요하다. Storage virtualization의 두 가지 중요한 abstraction은 - File - Directory 이다. 파일과 디렉토리는 익숙한 개념이라 거부감은 들지 않지만 과연 이러한 파일시스템이 어떻게 구현되고, 추상화되는지 한번 알아보자. Abstr..

Data wrangling #3 - Outlier, Data Encoding

저번 시간에 이어 Data Wrangling에 대해서 다뤄볼텐데, 그 전에 outlier란 무엇이고 어떻게 처리하는지 알아보도록 하자. Outlier An outlier is an observation that lies an abnormal distance from other values in a random sample from a population. In a sense this definition leaves it up to the analyst to decide what will be considered abnormal. '이상치'라고 하는 이 outlier는 다른 값들에 비해 비정상적인 값을 갖는데, data wrangling 과정에서 analyst는 이 '비정상'적인 값의 범위를 임의로 판단하..