페이지 부재 과정 : MMU가 OS에게 제어권을 넘겨 Disk(보조기억장치)에서 가져오는 과정 실행되는 Process에서 필요한 프레임(페이지)를 가져오기 위해 Page Table을 봤는데, i(invalid)로 되어있으면, OS에게 페이지를 찾아올 것을 요청 OS가 디스크에서 필요한 페이지의 위치 찾음 페이지를 가져온다. ...
Git 델타와 스냅샷
Git: 델타와 스냅샷 : git에서 커밋을 저장하는 방식 과거에는 오픈소스 프로젝트를 diff와 patch를 통해 개발했다. 코드를 수정하고 diff 프로그램으로 델타를 생성해 전달하고 patch 프로그램으로 메인 코드에 적용했다고 한다. 현재는 git을 사용하면 스냅샷과 델타를 통해 변화된 사항을 관리한다. 한 ...
Squash로 commit 통합하기
Rebase를 해야하는데, rebase적용해야할 source 브랜치 커밋이 긴 경우, 그리고 충돌이 많을 것 같을때 하나하나 컨플릭 해결하는 것은 너무 많은 일을 해야한다. Rebase 말고 그냥 merge 기존 commit을 Squash해, 하나의 커밋으로 통합하고 rebase 위 두 가지 방...
비밀번호 대신 PAT(Personal Access Token) 받아 사용하기
깃헙 레포지토리에 push했더니 위와같은 에러가 있었는데, 알고 보니 21년 8/13 이후로 깃헙이 더이상 비밀번호 인증방식을 사용하지 않는 것 같다. 1. 액세스 토큰 받기 1) 깃헙 로그인 후 Settings - developer settings Personal access tokens ...
코딩 인터뷰 완전분석 - 트리(Tree)와 그래프(Graph)
: 그래프의 한 종류로, Root 노드를 기준으로 노드간 Edge로 연결된 트리모양의 자료구조 트리 조건 하나의 루트노드를 갖는다. 0개 이상의 자식 node를 갖는다. 자식 node는 또 재귀적으로 0개 이상의 자식 node를 갖는다. cycle이 존재하지 않는다. 서로 다른 두 node간 경...
코딩 인터뷰 완전분석 - 연결 리스트(Linked list)
특징 삽입, 삭제가 O(1)시간에 가능하다는 장점 조회에는 O(n)의 선형시간 (최악의 경우) 단방향, 양방향 연결 리스트 가능 해시 테이블의 chaining 기법은 해싱한 한 Key에 대해 value 리스트(여러 value)를 갖는데, 연결리스트를 이용하는 것 Runner 기법 : current 노드를 가리키는 포인터와...
코딩 인터뷰 완전분석 - 해시 테이블
: 효율적으로 탐색을 하기 위한 알고리즘. Key - Value 쌍의 자료구조 일반적으로 Chaining을 통해 구현한 해시테이블을 말한다. 충돌이 발생한다면 최악의 경우 O(N)(연결리스트를 가정)이 된다.(N은 버킷 내의 키값 개수) 일반적으로 충돌이 발생하지 않도록 구현해 O(1) 과정: 키...
Red Black Tree
: 이진 탐색 트리(BST)는 조회, 삽입, 삭제시 O(logN)== O(h) == O(depth) 의 시간이 걸린다. 그런데, 운이 좋지 않아 편향된 모양을 갖게 되면 될수록 시간복잡도는 O(N)에 가까워진다. 따라서 균형잡힌 이진탐색트리를 유지하는게 좋은데, 그 중 하나로 대표적인게 RBT이다. 특징 자가 균형잡힌 이진트리 실 사용...
이진 탐색 트리(BST)
: 이진 트리의 일종이고, 효율적인 탐색을 위한 자료구조 규칙 각 노드의 키는 유일하다. 부모가 왼 자식보다 크고, 오른 자식보다 작다. 각 서브노드도 이진탐색트리이다. 탐색 : root부터 시작해, 원하는 key가 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동 시간복잡도: O(log n) . 정확히는 O(h)...
이진트리(Binary Tree)
: Root를 중심으로 두 개의 서브 트리로 나뉘는 트리. 이 때 나눠진 두 서브트리도 이진트리여야 한다. leaf node에 도달했을 때 해당 leaf node를 root로 하는 (마지막의) 서브트리도 이진트리여야 하기 때문에 Node 하나인 것도 이진 트리. -> 같은 논리로 공집합도 이진 트리. ...