Computer Science

권한 권한은 읽기, 쓰기, 실행 권한으로 나뉜다. 말 그대로 읽을 수 있는 권한, 쓸 수 있는 권한, 실행할 수 있는 권한이다.이를 각각 r, w, x 로 표시한다.디렉토리에서 ls를 이용해서 파일 및 디렉토리를 확인하면 각 파일 및 디렉토리 앞에 아래와 같이 나올 것이다.확인할 수 있듯이 가장 앞이 타입에 대한 부분이고, 그 뒤가 사용자, 그 뒤가 그룹, 그 뒤에 기타 사용자에 대한 권한이다. 위 경우 모든 사용자에게 모든 권한이 주어져 있다.이를 숫자로 나타내기도 한다. 특히 chmod, chown, chgrp 등으로 권한을 설정할 때 숫자를 사용하면 편리하다.읽기는 $4$, 쓰기는 $2$, 실행은 $1$로 나타내는데 이진수로는 $100$, $10$, $1$ 이기 때문이다. 이를 활용하여 권한을 더하..

디렉토리 (Directory) 디렉토리설명/루트 디렉토리, 리눅스 파일 시스템의 최상위 디렉토리.현재 디렉토리를 의미./현재 디렉토리에 있는 파일 또는 프로그램을 실행할 때 사용../상위 디렉토리를 의미/bin기본 명령어 실행 파일 저장/boot부팅 관련 파일 저장/dev장치 파일 저장/etc시스템 설정 파일 저장/home사용자 홈 디렉토리/lib공유 라이브러리 저장/media자동 마운트된 외부 저장 장치/mnt관리자가 수동으로 마운트할 때 사용하는 디렉토리/opt추가 소프트웨어 패키지 저장/proc시스템과 프로세스 정보 제공/root관리자(root) 사용자의 홈 디렉토리/sbin시스템 관리 명령어 저장/srv서버 관련 데이터 저장/sys시스템 및 커널 관련 정보를 제공하는 가상 파일 시스템/tmp임시 ..

여러가지 해시 함수 (Hash Function) 제산 함수테이블크기 $ m $ 을 소수로 선택하고, 탐색키를 테이블크기로 나눈 나머지를 사용한다.폴딩 함수탐색키를 여러 부분으로 나눈 후, 이동 폴딩(shift folding) 또는 경계 폴딩(boundary folding) 방식으로 결합한다.중간제곱 함수탐색키를 제곱한 뒤, 결과의 중간 몇 개 비트를 추출하여 해시 주소로 사용한다.비트추출 함수탐색키를 이진수로 변환한 후, 임의의 위치에서 $ k $ 개의 비트를 선택해 해시 주소로 만든다.숫자 분석 방법탐색키의 편중되지 않는 숫자들을 적절히 조합하여 테이블크기에 맞는 주소를 생성한다. 충돌 (Collision) 서로 다른 탐색키를 갖는 항목들이 같은 해시 주소를 가진다면 문제가 생길 것이고, 이를 충돌이라..

해시테이블  해시테이블이랑 해시를 이용하여 키(key)에 대응되는 값(value)을 저장하는 자료구조이다. 키에 대응되는 값에 빠르게 접근하는 것이 특징인데, 이는 해시 함수(hash function)를 이용하여 키에 대응되는 해시 주소(hash address), 즉 인덱스(index)를 생성하고, 이 인덱스를 통해 배열(버켓, bucket)에 값을 저장하기 때문이다. 배열에 저장하기 때문에 임의접근(ramdom access)이 가능하고, 따라서 잘 만들어진 해시테이블에서 키를 이용하여 값에 접근하는 것의 시간복잡도는 $ \mathcal{O}(1) $ 이다.해시 함수를 이용하여 키를 테이블 인덱스로 바꾸는 것을 해싱이라 하는데, 이 해싱을 어떻게 할 것이냐가 해시테이블의 접근 성능을 판가름한다. 당연히 ..

2-3 트리  차수가 2 또는 3인 트리, 즉 하위 노드의 개수가 두 개 혹은 세 개인 트리이다. 2-노드라면 이진 탐색 트리처럼 한 개의 데이터와 두 개의 자식 노드를 가지고, 3-노드라면 두 개의 데이터와 세 개의 자식 노드를 가진다.왼쪽 서브 트리에 있는 데이터들은 모두 첫 번째 데이터보다 작은 값이고, 중간 서브 트리에 있는 값들은 모두 첫 번째 데이터보다 크고, 두 번째 데이터보다 작아야 한다. 오른쪽 서브 트리에 있는 값들은 두 번째 데이터보다 커야 한다. 즉 이진 탐색 트리와 유사하게 정렬되어 있어야 한다.즉 트리가 위와 같다면 왼쪽 서브 트리의 값은 모두 $ k $ 보다 작고, 오른쪽 서브 트리의 값은 모두 $k $ 보다 크다.트리가 위와 같다면 왼쪽 서브 트리의 값은 $ k_1 $ 보다 ..

균형 이진 탐색 트리  이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조를 가지는데, 이진 탐색의 대상은 배열이므로 삽입과 삭제가 비효율적이지만 이진 탐색 트리에서 삽입과 삭제는 효율적이다. 단 이진 탐색 트리는 불균형인 경우 탐색의 시간복잡도가 $ \mathcal{O}(n) $ 이 되는 단점이 있다.이를 이진 탐색과 마찬가지로 효율적으로 탐색하기 위해서는 트리가 균형 트리여야 한다. 즉 이진 트리이면서 이진 탐색과 마찬가지로 왼쪽 서브트리 값이 노드 값보다 작게, 오른쪽 서브트리 값이 노드 값보다 크게 오도록 하며, 균형잡혀 있다면균형 이진 탐색 트리이다.간선의 수, 높이 등은 이진 트리(링크)의 속성을 일부 따른다. 노드가 $ n $ 개일 때 간선은 $ n -1 $ 개이고, 높이는..

보간 탐색  정렬된 리스트에서 탐색 범위를 줄여나가며 탐색하는 방식인데, 이진 탐색은 그냥 중앙을 탐색 위치로 지정하고 비교했다면 보간 탐색은 아래와 같은 공식을 이용해서 탐색 위치를 결정한다. 즉 이진 탐색이 균등 분할하였다면 보간 탐색은 불균등 분할하여 탐색한다.$$ \dfrac{\text{key} - \text{list}[\text{low}]}{\text{list}[\text{high}] - \text{list}[\text{low}]} \times (\text{high} - \text{low}) + \text{low} $$예를 들어 설명한다면 1400페이지의 전화번호부에서 하정우라는 이름을 찾는다고 해보자. 성에 ㅎ 이 들어가니까 당연히 중앙을 보는 것보다 1300페이지쯤부터 찾아보는 것이 효율적일..

순차 탐색  말 그대로 순차적으로 탐색하는 방법이다. 주어진 리스트의 시작부터 끝까지 찾으려는 값인 탐색키와 비교하면서, 탐색키와 같으면 반환, 다르면 다음 값을 탐색한다. 정렬되지 않은 경우 최선의 방법일 수 있다.값이 존재한다면 평균 비교 횟수는 $ (n+1) / 2 $ 이고, 값이 존재하지 않는다면 $ n $ 으로 시간복잡도는 $ \mathcal{O} (n) $ 이다.조금 개선된 순환 탐색 방법으로는 탐색 대상 리스트의 끝에 탐색키를 삽입하고 탐색키와 같은 값을 찾을 때까지 탐색한 후 탐색된 값의 인덱스가 삽입한 리스트의 인덱스라면 탐색 실패로 처리하는 방법이 있다. 구현 | C int sequential_search(int list[], int key, int low, int high) { ..

기수 정렬  여러 정렬들이 각 값을 비교한 후 알맞은 위치를 찾아가는 것과 다르게 어떤 정렬들은 값을 비교하지 않고 정렬한다. 기수 정렬이 대표적인 예시이다.사용하는 진법에 맞게 버킷을 만들고, 버킷에 차례대로 넣고, 작은 순서대로 꺼내면 정렬이 된다. 한자리 수들로 이루어진 리스트를 정렬하는 경우 버킷에 넣다 빼는 것을 한번만 하면 되지만, 두자리 수가 있다면 두번, 세자리 수가 있다면 세번 넣었다 빼야한다. 즉 리스트의 길이에 큰 영향을 받는 다른 정렬 방식과 다르게 리스트 내 최대값의 자리수에 영향을 더 많이 받는다는 특징이 있다. 예시 예를 들어 위와 같은 리스트를 정렬한다고 해보자. 먼저 아래와 같이 버킷을 만들어주어야 한다.가장 낮은 1의 자리를 기준으로 버킷에 차례로 담아준다.$$ \vdot..

병합 정렬   리스트를 균등하게 분할하고, 병합하면서 정렬하는 방법이다. 분할 정복 알고리즘의 대표적 예시 중 하나이다. 합병 정렬이라고도 한다.정렬은 데이터를 크기가 1이 될때까지 분할하고 다시 병합하면서 일어난다. 병합할 때 분할된 왼쪽 부분 리스트와 오른쪽 부분 리스트의 첫번째 값부터 차례대로 읽으면서 작은 값을 임의의 리스트에 넣어 정렬하는 것이다. 그렇게 병합이 된다면, 다시 상위의 부분 리스트와 병합하여 정렬하고, 다시 상위의 부분 리스트와 병합하여 정렬하여 최종적으로 분할된 모든 리스트를 병합하면 정렬이 끝난다. 이때 분할에서 재귀가 사용된다.새로운 리스트를 만들어서 병합 과정에서 사용하기 때문에 별도의 메모리 공간이 필요하고, 각 분할을 재귀로 구현해야하기 때문에 스택 메모리도 많이 사용한..