보통 리눅스/유닉스에서 파일의 읽기/쓰기 등의 권한 설정을 할 때 chmod 명령어를 사용합니다. 보통 모든 권한을 줄 때 chmod 777 [이름]를 입력합니다.

리눅스에서 권한은 총 10자리로 표시됩니다. ls -al 명령어를 이용하여 다음과 같이 권한을 확인할 수 있습니다.

drwxr-xr-x 4 root root        4096 2011-03-12 14:58 .
drwxr-xr-x 7 root root        4096 2011-03-12 15:37 ..
drwxr-xr-x 2 root root        6364 2011-03-12 14:32 CSC
-r-xr-xr-x 1 root root        23110 2011-03-12 14:32 build.sh

여기서 맨 앞부분에 있는 drwxr-xr-x와 같은 부분이 권한 표시 부분입니다.

각각의 알파벳들은 다음과 같은 권한을 의미합니다.

• d : 디렉토리 구분 (d이면 디렉토리, -이면 파일)
• r : 읽기 권한
• w : 쓰기 권한
• x : 실행 권한

그리고 맨 앞자리는 디렉토리인지 아닌지 여부, 그 다음 각 3자리씩은 소유자 권한, 그룹 권한, 전체 권한을 표현하고 있습니다.

즉,

를 나타냅니다.

리눅스에서 권한 설정은 chmod 명령어를 이용하면 변경할 수 있습니다. 예를 들어 chmod 777 snowdeer라고 할 때, 777이라는 값은 다음과 같은 규칙을 갖고 있습니다. 권한을 나타내는 rwx 각각은 r(4), w(2), x(1)의 값을 가지고 있습니다. 즉, r + w + x의 값은 7이 됩니다.

결국 777은 소유자, 그룹, 전체 권한을 모두 rwx로 바꾸겠다는 뜻입니다.

카운팅 정렬(Counting Sort)는 O(N) 성능을 가지는 정렬 알고리즘입니다. 그리고 구현까지 간단해서 알아두면 좋습니다. 흔히 성능을 위해 많이 사용하는 Cache와 비슷한 성격을 갖고 있습니다. O(N) 성능이라고 하면, 그냥 데이터들을 한 번 읽고 지나가면 정렬이 되는 속도라고 볼 수 있습니다.

일반적으로 많이 쓰는 정렬 알고리즘들인 Quick Sort나 Merge Sort가 O(N log N)임을 생각하면 상당히 훌륭한 편입니다. 하지만, 이런 엄청난 속도임에도 정렬 알고리즘의 대표적인 예시가 되지 못하는 이유는 특수한 환경에서만 쓸 수 있는 알고리즘이기 때문입니다.

일단, 원리를 알아보도록 하겠습니다.

원리

Counting Sort의 원리는 다음과 같습니다.

카운팅하고자 하는 숫자 값중 가장 큰 값 만큼의 배열을 하나 만듭니다. 예를 들어서 정렬하고자 하는 값이

{ 5, 14, 2, 7, 11, 3, 6, 10, 9, 18 }

라고 하면, 이 중에서 가장 큰 값이 18이므로 18만큼의 배열을 하나 만듭니다. 넉넉하게 크기 20짜리 배열을 하나 만들어보겠습니다. 저는 아래 코드에서는 result 라는 배열로 만들었습니다. 그리고 데이터를 처음부터 읽으면서 그 값을 인덱스로 하는 칸에 +1 합니다. 예를 들어, 데이터가 숫자 5인 경우는 result[5]를 +1 해주면 됩니다.

이렇게 모든 데이터를 읽어 들인 후, 그 다음에는 result 배열을 처음부터 읽으면서 그 값이 0보다 큰 경우에만 출력을 해주면 됩니다.

코드로 살펴보겠습니다.

코드

const int MAX = 10;
int data[MAX] = { 5, 14, 2, 7, 11, 3, 6, 10, 9, 18, };
int result[20];

int main(int argc, char**argv) {
  for(int i = 0; i < MAX; i++) {
    int index = data[i];
    result[index]++;
  }

  for(int i = 0; i <= 20; i++) {
    if(result[i] > 0) {
      printf("%d ", i);
    }
  }
  printf("\n");

  return 0;
}

주의점

성능이 O(N)이긴 하지만, 항상 Quick Sort나 Merger Sort 보다 더 좋은 성능이 나오지는 않습니다. 예를 들어, N = 2, 데이터는 {1, 999999} 라는 데이터가 있으면 카운팅 정렬을 쓸 경우 훨씬 더 안 좋은 성능이 나올 것입니다.

하지만, 일반적인 실 생활에서나 알고리즘 대회 등에서는 카운팅 정렬을 사용할 기회가 많이 있습니다. { 1, 3, 2, 3, 2, 1, 3, 2, 1, } 와 같이 최대값이 적은 경우는 아주 효과가 큽니다. 그리고 꼭 자연수일 필요는 없습니다. 음수일 경우 모든 값에 특정 값을 더해서 양수로 만들어서 적용할 수도 있고, 소수일 경우엔 특정 값을 곱해서 정수처럼 만들어서 사용할 수도 있습니다. 구현도 쉽기 때문에 정렬이 필요할 때 제일 먼저 카운팅 정렬을 떠올려보고 적용이 가능한지 판단해보는 것도 좋을 것 같습니다.

터미널에서 Tab을 누르면 기본적으로 그 알파벳으로 시작하는 폴더, 파일, 패키지 등을 자동으로 완성해주는 역할을 합니다. 만약, 후보군이 여러 개 있을 때는 그 목록을 보여줍니다.

그런데, 가끔씩 apt-get 명령어를 이용해서 패키지 인스톨을 할 때, Tab을 눌러도 자동 완성이 되지 않는 경우가 있습니다.

이런 경우에는 터미널에서

source /etc/bash_completion

를 입력하면 그 다음부터 자동 완성 기능이 활성화됩니다.

알고리즘 공부를 하다보면 간단한 정렬 알고리즘 하나 정도는 알아두는 편이 좋습니다. 그런데, 정렬 알고리즘들은 정말 다양하게 존재합니다. 물론, 성능도 제각각입니다. 그럼 어떤 알고리즘을 알아두는 것이 좋을까요?

보통 후보로 뽑히는 알고리즘은 Quick Sort 또는 Merge Sort입니다. 둘 다 분할 정복(Divide & Conquer) 기반 알고리즘이며 성능도 O(N log N)으로 비슷합니다. 취향에 따라 선택하면 되지만, Merge Sort가 좀 더 구현하기 쉬워서 개인적으로는 후자를 추천합니다.

Quick Sort와 Merge Sort를 비교해보면 다음과 같습니다.

• Quick Sort는 Worst Case에서 O(N^2)의 속도를 가진다.
• Merge Sort는 Worst Case에서도 O(N log N) 속도를 유지한다.
• 대신 Merge Sort는 더 큰 메모리 공간이 필요하고 메모리 할당/복사/삭제가 빈번해서 Quick Sort보다 속도가 좀 더 느린 경우도 종종 있다. (평균적으로는 비슷하다.)
• Merge Sort는 같은 값들의 순서가 정렬 후에도 유지되는 stable 한 성격을 갖고 있고, Quick Sort는 그러지 않다.

참고로 C++ 표준 라이브러리인 STL 에서는 2가지의 sort 함수를 제공하고 있는데, 일반적인 sort는 Quick Sort, stable_sort는 Merge Sort를 사용하고 있다고 합니다.

자, 그럼 MergeSort에 대해서 단계적으로 살펴보도록 하겠습니다.

분할

분할 정복 기반의 알고리즘이기 때문에 일단 분할을 합니다. 다음과 같이 1/2씩 나누기만 하면 됩니다.

정합

이렇게 나누어진 값들을 이제 합치면서 정렬을 해줍니다.

정렬 방법은 다음과 같습니다.

코드

실제 코드로 확인해보도록 하겠습니다. 다음은 C++ 코드입니다.

int temp[MAX];

void mergeSort(int*arr, int left, int right) {
  // 종료 조건: 나눌 수 없을 때까지 나눈다.
  if(left >= right) {
    return;
  }

  // 분할
  int mid = (left + right) / 2;
  mergeSort(arr, left, mid);
  mergeSort(arr, mid + 1, right);

  // 정합
  int length = right - left + 1;
  int offset = 0, offset1 = left, offset2 = mid + 1;

  while((offset1 <= mid) || (offset2 <= right)) {
    if(offset1 > mid) {
      temp[offset++] = arr[offset2++];
      continue;
    }
    if(offset2 > right) {
      temp[offset++] = arr[offset1++];
      continue;
    }
    if(arr[offset1] <= arr[offset2]) {
      temp[offset++] = arr[offset1++];
      continue;
    } else {
      temp[offset++] = arr[offset2++];
      continue;
    }
  }

  for(int i = 0; i < length; i++) {
    arr[left + i] = temp[i];
  }
}

마크다운(Markdown) 문법에 대해서 간단히 포스팅해봅니다.
웹페이지에 접속해서 글을 작성하는 것이 아니라, 메모장 등의 일반 에디터기를 이용해서 블로그 글을 작성할 수 있습니다. 자신이 익숙한 에디터기가 있다면 상당히 편리합니다. 대신 수동으로 각종 태그들을 직접 입력해야 한다는 점에서 어느 정도 장벽이 있습니다. 하지만, 태그 몇 가지만 익히면 편리하고 빠르게 글을 작성할 수 있습니다.

여기서는 필수적인 문법 몇 가지만 언급하도록 하겠습니다.

제목

제목은 다음과 같이 사용할 수 있습니다.

# 큰 제목 (H1)
## 두번째 제목 (H2)
### 세번째 제목 (H3)
...

줄바꿈

마크다운에서 줄바꿈은 문장 맨 끝에 스페이스 두 번을 넣으면 됩니다.

안녕하세요.  
오랜만입니다.

문단 나누기

문단을 나누고자 할 때는 한 줄을 비우면 됩니다.

문단을 나누고 싶으시면 이렇게

한 줄을 비우시면 됩니다.

이탤릭체, 볼드체, 취소선

*이탤릭체*, _이탤릭체_
**볼드체**, __볼드체__
~~취소선~~

인용

> 인용하는 문구

테이블

Header | Header
------ | ------
Cell   | Cell  

Keyboard

<kbd>Ctrl</kbd> + <kbd>Alt</kbd> + <kbd>Del</kbd>

하이퍼링크

[단어](주소)

이미지 삽입

![사진 이름](주소)