waca's field

# 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$개의 원소를 갖는다. 주대각선을 제외하고, 그..

# 멱집합 구하는 문제 문제) S가 n개의 원소로 된 집합일 때 S의 멱집합(powerset)은 모든 가능한 S의 부분집합이다. 즉, S = { a, b, c }이면 powerset(S) = { { }, { a }, { b }, { c }, { a, b }, { a, c }, { b, c }, { a, b, c } } 이다. powerset(S)를 구하는 순환 함수를 작성하라. # 풀이 비트 연산을 이용하는 문제다. 순환으로 구현해야 하는 만큼 순환별 규칙을 생각할 필요가 있었고, 값을 하나 증가시키는 걸 그 규칙으로 삼았다. 하나의 순환 안에서의 반복문이 비트연산의 핵심인데, 처음엔 이해가 어려워도 하나하나 손으로 써가면서 확인하면 그 규칙이 눈에 들어올 것이다. /********************..