# 해싱이란? 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 부르고, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다. 키들의 비교에 의한 탐색 방법은 정렬이 안 되어 있다면 $O(n)$이고 정렬이 되어 있다면 $O(log_2n)$이다. 정렬되어 있는 경우의 시간 복잡도가 $O(log_2n)$인 건 이진 탐색 알고리즘 혹은 이진 탐색 트리의 탐색 알고리즘의 시간복잡도를 생각하면 된다. 잘 모르겠다면 이진 탐색 또는 이진 탐색 트리 ..
# random walk 술취한 바퀴벌레 문제 // 문제가 길다. 집중해서 살펴보자. 수학 분야에서 "random walk"로 불리워지며 오랫동안 관심의 대상이 되었던 많은 문제들이 있다. 이러한 문제 중 지극히 간단한 것조차도 해결하기 매우 어렵기 때문에 대부분의 문제들이 해결되지 못한 채 남아 있다. 그 하나의 예가 '술취한 바퀴벌레 문제'다. 한 (술취한) 바퀴벌레가 $m$$\times$$n$ 크기의 직사각형 방 중간의 한 타일 위에 있다. 바퀴벌레는 임의로 타일에서 타일로 이동한다. 바퀴벌레가 현재 타일에서 그 주위 8개의 타일(벽 옆에 있지 않은 경우에 한해)로 같은 확률을 가지고 움직인다고 가정하자. 이 때 적어도 한 번씩 방의 모든 타일을 지나가는 데 걸리는 시간은 얼마인가? 순수한 확률 이..
# 정방 밴드 행렬 문제 문제) 정방 밴드 행렬(square band matrix) $D_{n,a}$ 란 0이 아닌 모든 항들이 주대각선을 중심으로 한 밴드에 있는 $n$$\times$$n$ 행렬이다. 밴드는 아래의 그림과 같이 주대각선과 주대각선의 위와 아래에 $a-1$ 개의 대각선을 포함한다. $D_{n,a}$의 밴드 안에 있는 원소의 개수를 구하는 식을 작성해보아라. 또한 $D_{n,a}$의 밴드 안에 있는 원소 $d_{i,j}$에서 i와 j는 어떤 관계인지도 서술해라. # 풀이 이 문제 또한 손으로 직접 써 보다 보면 규칙성이 보이는 문제고, 그 규칙성을 식으로 정리하면 된다. 주대각선의 특징부터 살펴 보면, 행렬의 크기가 $n$이라고 했을 때, $n$개의 원소를 갖는다. 주대각선을 제외하고, 그..
# 3원 대각 행렬 문제 문제) 3원 대각 행렬(tridiagonal matrix)은 아래와 같이 정방 행렬(square matrix)에서 주대각선(major diagonal)과 이 주대각선의 바로 위 아래의 대각선에 있는 원소를 제외한 다른 모든 원소가 0인 행렬이다. 이 세 개의 대각선 위에 있는 원소들이 배열 $b$에, $a[ 0 ][ 0 ]$은 $b[ 0 ]$에 저장된다. 배열 $b$에서 a[ i ][ j ] $(0$$\leq$i, $j
# 삼각행렬의 원소의 주소를 구하는 문제 문제) 정방행렬의 대각선 위나 아래의 모든 원소들이 0일 때 그 행렬을 삼각행렬(triangular matrix)이라 한다. 아래의 그림은 하삼각행렬(lower triangular matrix)과 상삼각행렬(upper triangular matrix)을 나타낸다. $n$개의 행을 가진 하삼각행렬에서 0이 아닌 $i$행의 원소는 최대 $i + 1$개 이다. 따라서 0이 아닌 항의 총계는 다음과 같다. // $i$는 0부터 시작한다. 하삼각행렬의 0번째 행의 원소의 개수는 1개이고, 그 아래의 행을 따라가면서 원소의 개수를 세면 도출 가능한 규칙이다. $d =$$\sum_{i=0}^{n-1} {i+1}$$=$$\frac{n(n+1)} {2}$ // $d$는 dista..
- Total
- Today
- Yesterday