waca's field

# 셸 정렬 개념 및 원리 셸 정렬(shell sort)은 Donald L. Shell 이 제안한 방법으로 삽입 정렬이 어느 정도 정렬 되어 있는 배열에 대해서는 대단히 빠르다는 점을 이용해 만든 방법이다. 셸 정렬은 삽입 정렬의 시간 복잡도 $O(n^2)$보다 빠르다. 삽입 정렬의 문제점은 요소들일 삽입될 때, 이웃한 위치로 한 칸씩만 이동한다는 점이다. // 제 블로그에 삽입 정렬로 검색하시면 관련 설명과 알고리즘을 확인해보실 수 있습니다. 삽입 정렬은 for 루프를 이용해 인접한 위치부터 한 칸씩 이동하며 삽입할 위치를 탐색하므로 만약 삽입할 원소가 들어갈 자리가 멀리 떨어져 있다면 한 칸씩 이동하는 설계 때문에 불필요하게 많은 반복과 비교를 해야 한다는 단점이 있습니다. 셸 정렬에서는 요소들이 멀..

# 해싱이란? 대부분의 탐색 방법들은 탐색 키를 저장된 키 값과 반복적으로 비교하면서 탐색을 원하는 항목에 접근한다. 반면 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 이렇게 키 값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(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..

# 행렬의 안장점의 존재 여부와 그 위치, 값을 구하는 문제 문제) $m*n$ 행렬에서 어떤 원소 $a[i][j]$가 $i$행에서 가장 작은 값이고 $j$열에서 가장 큰 값일 때, 이 행렬은 안장점(saddle point)을 갖는다고 말한다. 안장점이 존재한다고 할 때 이 안장점의 위치를 결정하는 C함수를 작성하라. 작성한 함수의 연산 시간은 얼마인가? # 풀이 문제에서는 행렬의 안장점(saddle point)이 존재한다고 가정했지만, 직접 프로그래밍을 할 때는 예외상황에 대한 처리 또한 해주는 것이 좋다. 안장점(saddle point)이 있다면 어디 위치의 무슨 값이고, 만약 없다면 존재하지 않는다고 출력할 수 있는 프로그램을 작성해보자. 안장점(saddle point)은 행에서 가장 작고, 열에서 ..

# 배열 뒤집기 문제 문제) 주어진 배열 $a[n]$을 가지고 $z[0] = a[n-1]$, $z[1] = a[n-2]$, $...$, $z[n-2] = a[1]$, $z[n-1] = a[0]$의 성질을 만족하는 배열 $z[n]$을 작성하라. 이 때, 최소의 기억장소를 사용하여 만들어라. # 풀이 비교적 간단한 문제에 속한다. 임의의 원소를 만들어 준 후에, 반복문을 이용하여 인덱스에 약간의 연산만 추가해 주어 값을 복사한다. /************************************************* ** 배열의 원소를 거꾸로 갖는 새로운 배열 제작 *************************************************/ #include #define MAX_SIZE 3..

공용체(union)를 학습하기 전에 먼저 구조체에 대한 부분이 학습이 되어 있어야 한다. 구조체 포스팅에서 다뤘던 human 구조체를 기본으로 공용체를 설명하려 한다. 먼저 공용체가 등장한 기본 아이디어부터 살펴보도록 하자. human이라는 구조체를 남자와 여자로 구분하려 한다. 남자라면, 수염이 있는지 없는지 여부를 물을 수 있을 것이고 여자라면, 아이가 몇 명 있는지 등의 질문을 할 수 있을 것이다. 구분하는 방법은 다양하다. 주민번호 앞자리가 1인지 2인지에 따라 구분할 수도 있을 것이다. 그러나 항상 비교연산 등을 통해야 여부를 알 수 있으므로 이렇게 비교하는 건 불편하다. 더 쉽게 구분할 수 있는 방법은 없을까? 위의 아이디어로부터 등장한 개념이 바로 공용체(union)다. 공용체의 선언은 구조..

배열(Array)은 같은 타입의 데이터를 한 데 묶어 관리하게 해주는 자료구조라면, 구조체(Struct)는 서로 다른 타입의 데이터를 한 데 묶어 관리할 수 있게 해주는 자료구조다. 구조체(struct)는 다른 프로그래밍 언어에서 레코드(record)라고 불리기도 한다. 구조체의 예를 한 번 살펴보자. struct { char name[10]; int age; float salary; } person; 구조체 문법을 통해 3개의 항목(fields)를 가지는 변수(variable) person을 만들었다. 구조체가 있기 전에는 변수라 하면, int형 혹은 float형 등 단일 변수를 의미했지만 이제는 다양한 자료를 한 데 묶어 하나의 변수로 취급할 수 있게 됐다. 위 구조체 변수 person이 가지는 3개..