이동식 저장소

Graph 그래프란 하나 이상의 정점이 0개 이상의 간선으로 이어진 것을 말한다. 간선은 양방향일 수도, 단방향일 수도 있다. 간선이 단방향이라면 간선을 통해 한쪽 방향으로만 이동할 수 있으며, 반대로는 이동할 수 없다. 간선에는 가중치가 있을 수도 있다. 일반적으로 가중치란 간선을 지나가는 비용 또는 정점 간의 거리를 의미한다. 그래프와 관련된 알고리즘으로는 최단 거리 알고리즘과 SCC 등이 있다. Tree 생각해 보니 Heap보다 Tree를 먼저 정리해야 했는데... 뭐 어쩔 수 없지. 사이클이 없는 그래프를 Tree라고 부른다. 사이클이란 정점에서 출발하여 서로 다른 간선을 지나 자기 자신으로 돌아오는 경로이다. 트리의 맨 위에 있는 노드를 루트 노드라고 한다. 반대로 맨 밑에 있는 노드를 리프 노..

Array 배열은 같은 타입의 자료 여러 개를 일직선으로 저장하는 자료구조이다. 메모리 공간에도 연속적으로 저장되는 특성 때문에 대량의 비트 연산을 쉽게 수행할 수 있다. 모든 자료가 연속적으로 저장되므로, 첫 번째 원소의 주소만 알면 상수 시간에 모든 원소에 접근할 수 있다. 그러나 (맨 뒤에 삽입하는 경우를 제외하면) 삽입과 삭제 연산을 처리하는 데 선형 시간이 걸린다. 삽입 또는 삭제하는 위치 뒤에 있는 요소들을 뒤로 밀거나(삽입) 앞으로 당겨와야(삭제) 하기 때문이다. 배열이 꽉 찼다면 메모리를 추가로 할당받아야 한다. 운이 나쁘다면 아예 다른 위치로 값을 옮겨야 할 수도 있다. LinkedList 값을 연속해서 저장하지 않고, 다음 값의 주소만을 가리키는 방식으로 저장한다. 메모리 상에 연속해서..

$N$개의 수를 오름차순으로 정렬하는 알고리즘에 대해 알아보자. 내림차순이나 커스텀 정렬은 비교하는 기준만 바꾸면 된다. 버블 정렬 버블 정렬은 인접한 두 수를 비교하며 정렬하는 알고리즘이다. 다음을 반복한다. 첫 원소부터 시작하여 인접한 두 개의 원소를 비교한다. 앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 바꾼다. 같은 방법으로 총 $N-1$번의 비교를 수행한다. 이렇게 하면 가장 큰 수를 맨 뒤로 보낼 수 있다. 모든 수가 정렬될 때까지 1~3번을 반복한다. 위의 시행을 한 번 시행할 때마다 수를 하나씩 정렬할 수 있다. 구체적으로 $i$번째 시행에서 $i$번째로 큰 수가 정렬된다. 따라서 위의 시행을 최대 $N$번 반복하면 배열을 정렬할 수 있다. 이름이 버블 정렬인 이유는 정렬되는 과정이..

맥스웰의 악마 비트는 에너지를 가지고 있다. 비트를 저장하고 처리하는 데 에너지가 들기 때문이다. 그러면 $E=m{c}^2$에 의해 비트 하나가 갖는 무게를 알 수 있다. 어쨌든 비트는 에너지를 갖는다. 그렇다면 무게가 $t$ 그램인 블랙홀은 몇 개의 비트로 표현될까? 참고로 블랙홀은 표면적과 최대 질량이 비례한다. 블랙홀의 표면적의 일부분 $s$마다 비트가 할당될 텐데, 놀랍게도 $s$는 플랑크 길이의 제곱과 같다. 즉 플랑크 길이의 제곱에 해당하는 면적마다 비트를 하나씩 할당하면 된다. 이쯤되면 의심하지 않을 수 없다. 도대체 플랑크 길이는 무엇인가? 우주는 정말로 디지털인가? 파동이 입자로 바뀌는 순간 코펜하겐 해석에 따르면 파동은 측정되는 순간 입자로 바뀐다. 그 입자의 위치를 제외한 다른 모든 ..

1. 사용자 정의 함수 1.1 함수 정의 방법 func = function(arg1, arg2, ...) { ... } 한 줄짜리 함수는 중괄호를 안 써도 된다. my.sum = function(x, y) x + y 1.2 매개변수 매개변수에는 디폴트 값을 줄 수 있다. 디폴트 값이 주어진 매개변수는 함수 호출 시 생략해도 된다. func = function(x, conf=0.95) { ... } func(c(1, 2)) # OK func(c(1, 2), conf=0.9) # OK 기존의 함수를 이용하여 함수를 정의할 때 생략 부호 ...을 이용하면 매우 편리하다. 일반적으로 생략 부호는 함수의 마지막 매개변수로 지정한다. 함수를 호출할 때 ... 부분에 사용한 매개변수는 모두 기존 함수로 전달된다. f..