전체 글

[Model Checking] Designing Reliable Distributed Systems

TODO Ch. 2 : 자연수, 정수, list, binary tree, multiset 등 data type 정의 Ch. 3 : equational specification이 만족하는지 확인 Ch. 8 : rewrite logic을 사용해서 concurrent behavior 작성 방법을 설명 Ch. 9 : rewriting logic을 사용해서 system의 동작 하나를 분석하는 방법 FREE Ch. 10 : concurrent Ch. 11 : communication Ch. 12 : TCP와 같은 transport protocol 모델링 Ch. 13 : distributed DB 모델링 Ch. 2 Data Types Module fmod MODULE_NAME is MODULE_BODY endfm o..

기타 면접대비 질문

간단한 자기소개지원동기장단점나의 비전 : 사람들에게 긍정적인 영향을 줄 수 있는 사람이 되는 것.프로젝트 하면서 어려움 극복 : bizkicks 얘기?회사에 대해 궁금한 점협업 방식각 프로젝트인성   개발지식객체지향더보기정의class vs instance특징 4가지장단점더보기객체들의 상호작용으로 프로그램을 구현하는 방법.객체는 어떤 개념을 추상화하고 모델링한 요소. state와 behavior를 가짐.- 추상화란 불필요한 정보는 숨기고 중요한 정보만을 보여주는 것(컴퓨터 과학)class : 설계도, instance : class로 만들어진 메모리에 올라간 실체. 특징abstraction : OOP에서 abstraction은 불필요한 정보는 private으로 숨기고 중요한 정보를 public으로 노출하고,..

자료구조 면접대비 질문

Hash Table 더보기 정의 collision 해결 방식 hash function 더보기 어떤 key가 주어졌을 때 hash function으로 매핑하고, 거기에 값을 저장하는 key-value store. 메모리에 쓰는 경우, 값이 유한하기 때문에 collision이 발생한다. separate chaining : 해당 bucket에 linked list 추가하는 방식. 쏠릴 수 있어 worst O(n) open addressing : 해당 위치가 아니라 빈 공간을 사용하는 방식. 예외가 많아 어렵다. hash function은 임의의 길이 data를 고정 길이 data로 매핑하는 함수. Quick Sort 더보기 pivot 기준으로 왼쪽에는 작은 수, 오른쪽에는 큰 수 둔다. pivot은 적당한 값..

네트워크 면접대비 질문

URL vs URI더보기URL : uniform resource locator, resource의 위치URI : uniform resource identifier, resource의 식별자 HTTP더보기정의특징http request message / response message에 들어가는 것들더보기hypertext transfer protocol의 약자client-server model, TCP 사용, stateless(상태 저장 x) 등의 특징이 있다.stateless를 해결하기 위해 cookie나 session을 사용한다. HTTP request message에는 request, header, body가 있다.method는 GET, POST, PUT, PATCH, DELETE 등이 있다.GET의 경..

OS 면접대비 질문

Floating Point더보기어떻게 표현하는지case 3개변환방식rounding더보기2진수를 유효숫자 형태로 표현한 것(-1)$^s$M2$^E$s : sign bit. signed integer와 동일하게 0이면 양수, 1이면 음수이다.M : significand(유효숫자). 일반적으로 [1.0, 2.0)의 범위를 가진다.E : exponent(승수). 2의 승수를 나타낸다. Floating Point to Number수를 정해진 형식에 따라 sign bit, exp bit, frac bit로 분류한다.exp bit, frac bit을 이용해 normalized / denormalized / special 분류를 한다.exp bit로 E값을, frac bit로 M값을 구한다. (-1)$^s$M2$^E$..

DB 면접대비 질문

Transaction더보기transaciton의 정의, 특성(ACID)commit / rollbackstate더보기transaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.Consistency : transaction의 실행 결과는 항상 일관성이 있다. (정해둔 규칙을 위배하지 않는다.)Isolation : transaction 사이에 다른 trasnaction이 낄 수 없다.Durability : DBMS가 꺼져도 수행된 transaction은 반영되어 있어야 한다.  commit은 모든 작업이 정상적으로 수행되었다는 명령이며, 실..

DB 기초 - 2

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다. Key 다음 4종류가 있다. Candidate Key : tuple을 unique하게 식별할 수 있는 attribute set. + minimality : attribute 1개를 지우면 식별할 수 없다. Super Key : key의 super set Primary Key : candidate key 중 지정된 것. Foreign Key : 다른 relation을 참조하기 위해 다른 relation의 key를 가져온 것. dangling을 알아서 처리해 준다. Normal Form / Normalization [1NF - 2NF - 3NF - BCNF - 4NF - 5NF] 순서로 더 higher하다...

DB 기초 - 1

이 글은 포스텍 한욱신 교수님의 데이터베이스시스템(CSED421) 강의를 기반으로 재구성한 것입니다. DBMS의 정의 DBMS란 database를 관리/유지시켜주는 소프트웨어이다. 사용 이유는 data independency와 효율적 접근, 보안, 동시 접근을 위해서이다. file system에 비해서 cost는 크지만 redundancy가 없고, constraint를 유지할 수 있다는 장점이 있다.   Transction & ACIDtransaction : DBMS의 상호작용 단위. transaction은 다음 4가지 성질을 가지고 있다.Atomicity : transction은 실행되거나, 실행되지 않거나 둘 중 하나의 상태만 가진다. 중간에 끊기지 않는다.Consistency : transactio..

23.09.25. 풀었던 문제들

Programmers Lv. 3 입국심사, 8분 parametric search. typedef long long ll; vector times; // t시간동안 심사할 수 있는 인원 수 ll calculateNumPass(ll t){ ll num_pass = 0; for(int time : times){ num_pass += ((ll) t / time); } return num_pass; } long long solution(int n, vector t) { ll start = 0, end = 1e18; times = t; while(start = n..

23.09.24. 풀었던 문제들

Programmers Lv. 3 보석 쇼핑, 19분 two-pointer를 활용하면 되는 문제. 유의할 점은 start와 end 사이에 있는 보석 개수를 세야 하는데, map으로 숫자를 세면 count에 O(보석 개수)만큼의 시간이 걸리고, multiset을 쓰면 identical한 보석 개수를 셀 수 없기 때문에 map과 set을 같이 썼다. set cur_gems; int num; map cur_gem_count; bool isContainAll(){ return cur_gems.size() == num; } void insert(string gem){ cur_gem_count[gem]++; cur_gems.insert(gem); } void erase(string gem){ cur_gem_count..

23.09.23. 풀었던 문제들

Programmers Lv. 3 불량 사용자, 28분 문제 자체는 주어진 것만 풀면 되는 문제. input size가 8이므로 최대 8!의 시간 복잡도이며, 따라서 backtrack(순열)로 풀면 된다. 단, 유의할 점은 `제재 아이디 목록을 구했을 때 아이디들이 나열된 순서와 상관없이 아이디 목록의 내용이 동일하면 같은 것으로 처리한다`이기 때문에, 이를 잘 처리해야 한다. 모든 banned_id에 대해 가능한 user_id의 후보군들을 나열하고, permutation/backtrack으로 가능한 모든 조합을 나열하고, 해당 조합에서 겹치는 것을 빼면 되겠네. 위 3가지 flow로 쉽게 처리할 수 있다. // banned_id와 user_id가 일치하는지 bool isBanned(string banne..

23.09.20. 취준계획 - 끝!

진짜 너무너무 바쁘다. 수업 과제는 뭐... 받자마자 하루컷 낸다 쳐도, 나머지가 끊임없이 이어진다. 일단 쓰고 싶은 데는 다 쓰는 게 맞는 것 같다.어차피 막학기 아니니까 여유 가져도 되긴 하는데, 미리 한 번 겪어보고 싶다. 근데 말도 안되게 바쁜게, 졸업과제 ← 얘가 진짜 너무 트롤이다. 1학점짜리가 아니라 한 5-6 되는 듯. 지금, 자소서도 써야하고 코테공부도 해야하고 면접공부도 해야 하는데... 근데 과제연구를 주에 적어도 6시간은 써야 한다. SD 과제도 있고... 병렬컴퓨팅 과제도 있고.. 시험기간이 되면 교양 레포트도 나오고... 크아아아악. 끔찍하다. 취준 계획 - 코테 일단 내가 쓴 곳들 중 코테를 보는 곳이 [LG CNS完, 넥토리얼, 베이글코드完] 이렇게 3군데이다. - 다 끝났다..

23.09.19. 풀었던 문제들

Programmers Lv. 3 여행경로, 17분 그냥 DFS 돌리면 되는 문제. 단 각각의 vertex가 string으로 표현되는 점과 [사용한 표]를 어떻게 표기할지에 대해 유의해야 한다. 뭐.. 정석 DFS처럼 각 ticket의 index를 visit했는지 안했는지를 표기할 수 있긴 한데. 결국 alphabet 순서로 DFS + edges를 만들어야 하기 때문에 map을 사용해야 할 것 같다. 처음에는 multiset을 썼었는데, DFS를 위해 multiset에서 element를 빼고 넣는 과정에서 계속 같은 위치를 참조하는 것 같았다. (무한루프) 그래서 map of map을 썼다. edges[i]는 i에 인접한 공항들의 map 목록이고, 이것은 [도착지 이름, 같은 표가 몇 개인지]를 나타낸다...

[Model Checking] 과제연구 주제 정리

지도교수님과 여러 가지 이야기를 나눴고, [특정 모델 체킹 언어를 사용해, 특정 시스템의 모델 체킹을 해 보기]를 주제로 과제연구를 진행하기로 했다. 대충 flow는 아래와 같다. 특정한 model checking 언어를 공부한다. 어떤 system을 체킹할 지 확인하기 distributed key-value store (cloud DB) RAFT consensus algorithm 위 2개를 추천받았는데, 모델링하기 위해서는 해당 system의 동작 방식을 알아야 한다. 일단 백엔드로 갈 거니까 분산 DB를 공부하는 게 좋아보인다. safety, fairness 등 어떤 property를 모델링할지 결정하기 Model Checking 언어 공부 model checking tool은 몇 가지가 있는데, ..

[Model Checking] Linear Time Properties

이 글은 RWTH AACHEN 대학교 Joost-Pieter Katoen 교수님의 2018년 1학기 Introduction to Model Checking 강의와 Principles of Model Checking을 기반으로 재구성한 것입니다. model checking의 주된 알고리즘은 transition system과 requirement를 model checker에 넣어, 해당 transition system이 requirement를 만족하는지 여부를 확인하는 방법이다. 그래서 지금까지 transition system을 모델링하는 방법을 살펴봤었고, 지금부터는 requirement를 모델링하는 방법을 살펴볼 것이다. 이 포스트에서는 크게 4가지를 살핀다. state-based and linear t..

23.09.17. 풀었던 문제들

Programmers Lv. 3 베스트앨범, 15분 그냥 풀면 되는 구현 문제. 장르별 재생회수의 순서 장르 내부에서 재생회수의 순서 위 2가지에 대해 정렬되어 있어야 하기 때문에 map을 2개 써야 한다. 그냥 뭐.. map에 genre를 key로 넣어 재생회수 합계와 해당 genre에 속한 노래들의 {재생회수, index}를 저장하면 된다. int len; struct Info{ int play, index; }; struct cmp{ // 조건 1. play가 큰 것. // 조건 2. index가 작은 것. bool operator()(Info &a, Info &b){ if(a.play == b.play) return a.index > b.index; return a.play < b.play; } ..

23.09.14. 풀었던 문제들

프로그래머스 Lv. 2 최댓값과 최솟값, 4분 30초 c++에서 delimiter를 사용해 string을 파싱할 줄 알면 바로 풀리는 문제. iss 쓰고 while getline으로 풀면 된다! string solution(string s) { int min_v = INT_MAX; int max_v = INT_MIN; istringstream iss(s); string buffer; while(getline(iss, buffer, ' ')){ int v; if(buffer[0] == '-'){ v = stoi(buffer.substr(1)); v *= -1; } else{ v = stoi(buffer); } min_v = min(min_v, v); max_v = max(max_v, v); } return..

[Model Checking] Modeling Concurrent System

이 글은 RWTH AACHEN 대학교 Joost-Pieter Katoen 교수님의 2018년 1학기 Introduction to Model Checking 강의와 Principles of Model Checking을 기반으로 재구성한 것입니다. 지난 글에서는 Transition System과 Program Graph, 그리고 Program Graph를 Transition System으로 변환하는 방법을 살펴 봤다. 여기서 살폈었던 것들은 닫힌 계로써, 단 하나의 프로그램만 모델링하는 방법이었다. 이제 총 n개의 parallel system P$_1$, P$_2$, ... P$_n$ 이 있을 때를 모델링하고자 한다. 이 때 각 thread의 행동은 아래 3가지 중 하나이다. no communication ..

23.09.12. 풀었던 문제들

Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique, 30분 첫 접근 그냥 주는 대로 풀었다. 일단 각 char이 몇 번 나오는지 알아둬야 하니까 map같은 걸 써야 하는데, 이 문제의 경우 알파벳 소문자만 나오기 때문에 vector(26, 0)을 map처럼 쓰면 된다. 이후, 내림차순으로 정렬한다. 정렬한 후, 만약 겹치는 값이 있는 경우에는 해당 값을 1 줄이고, 해당 문을 다시 반복한다. 이 접근이 문제될 때는, 2 2 2와 같은 예시를 보자. 2 2 2에서 index 1이 2 1 2로 바뀐다. index 1에서 같은 값의 비교는 앞의 값만 보기 때문에 pass. index 2에서 앞의 값만 보기 때문에 pass한다. 문제가 ..

23.09.11. 풀었던 문제들

Leetcode 1282. Group the People Given the Group Size They Belong To, 30분 문제 자체는 빨리 풀었는데, 여러 개선을 한다고 시간이 좀 걸렸다. 첫 번째 접근 최대한 생각나는 대로 구현했다. groupMap은 특정 size를 가지고 있는 모든 group의 정보를 가지고 있다. 때문에 구현은 단순하다. 입력으로 받은 size의 group이 없는 경우 생성한다. 입력으로 받은 size의 group이 있는 경우, 해당 group이 존재하지만 아직 size만큼 차지 못하는 경우 - 해당 group에 현재 인원을 넣어준다. 해당 group이 있고, size만큼 찬 경우 - 새로운 group을 넣어준다. 이렇게 푸니까 runtime 22ms, beats 8.5%..