JPS 알고리즘 개요 이전에 우리는 A* 알고리즘에 대해서 공부해보았다. 하지만 이러한 A* 알고리즘 역시 기본적으로 BFS에 가까운 알고리즘이고 매칸 마다 그다음 노드들을 탐색해야하기에 너무나 많은 시간이 걸린다. 이전 시간에 포스팅한 A* 알고리즘으로 탐색한 내용이다. 보면 알겠지만 BFS로 전체를 탐색한 것과 크게 차이가 나지 않아보인다...

A * 알고리즘 가장 대표적인 길찾기 알고리즘 중 하나이다. 기존에 있던 다익스트라 알고리즘 기반으로 개량된 알고리즘으로 스타크래프트가 이러한 A* 알고리즘을 이용하여 각 유닛의 길찾기를 구현했다고 알려져있기도하다. 이 알고리즘은 평가함수로 해당 경로를 갈지 말지를 평가하게 되는데 이 평가함수 f(N)은 다음과 같다. [f(N) = g(N)+h^...

#알고리즘 알고리즘은 어떤 방식을 해결하고자 하는 방식이다. 사실 기본적인 알고리즘은 이미 컴퓨터 기초 영역에서 다루었다. 하지만 좀 더 깊은 알고리즘을 컴퓨터 기초영역에서 다루려고하니 따로 항목을 분리하는게 좋을 것 같아서 별도의 항목을 신설했다. 대략 아래의 목차대로 진행할 예정이다. 물론 아래의 목차는 자주 업데이트 될 예정이며 삭제 및...

1. 우선순위 평가 (1) 인접행렬 ① 개념 요소간의 연결 관계를 나타내는 정사각행렬 (수학적으로 엄밀한 정의는 아님) ex) ② 권위벡터와 허브벡터 $n \times n$ 인접행렬 $A=(a_{ij})$에 대하여 \(\begin{pmatrix} \sum_{i=1}^{n}a_{i1} \\ \sum_{i=1}^{n}a_{i2} \\ \vdot...

1. 곡선 적합 (1) 보간법 ① 개념 주어진 특정 점을 포함하는 함수를 구하는 방법 정리) 좌표평면에 있는 임의의 서로 다른 n개의 점을 지나는 k차 다항함수는 유일하게 존재한다. (단, k는 k<n인 자연수) ② 사례 네점 (1,3),(2,-2),(3,-5),(4,0)을 모두 지나는 3차 함수 $f(x)=a_{0}+a_{1}+a_{2...

1. 복소 벡터공간 (1) 정의 복소수체 C에 대한 가군, 즉, 적당한 집합 V에 대해 벡터공간 (V, C, +, ·)을 복소벡터공간이라 한다. 또한 모든 복소 n-튜플 $(v_{1},v_{2},v_{3},…,v_{n})$ 의 집합을 복소 n-공간이라 하고 $C^{n}$으로 표시한다. (2) 복소켤레 $C^{n}$의 임의의 벡터 $v = (v_{...

1. 고윳값과 벡터 (1) 정의 체 F에 대한 벡터공간 V위의 선형사상 $L: V \to V$에 대하여 다음 두 조건 $v \neq \overrightarrow{0}$ $L(v) = \lambda v$ 를 만족하는 $\lambda \in F$와 $v \in V$를 각각 고윳값과 고유벡터라고 한다. ex) \(v = (2,3), L \to...

1. 선형 사상 (1) 선형사상 ① 정의 선형 사상은 관례적으로 L로 표기한다 (Linear map) F-벡터공간 V,W에 대하여 V의 성질을 보존하는, 다음 두 조건을 만족하는 사상 L : V -> W 1) 가산성 : $L(u+v) = L(u) + L(v) (u,v \in V)$ 2) 동차성 : $L(kv) = kL(v)v (k \in...

선택공리 (1) 선택함수 집합 \(X \left ( \neq \varnothing \right )\)의 부분집합들의 집합족을 \(\left\{ A_{i} \right\}\)이라 할때 \(\forall _i \in I, f(A_{i})\in A_{i}\) 인 \(f : \left\{ A_{i} \right\} \to X\) (2) 선택공리 공집합이 ...

부분순서집합 (1) 정의 ① 부분순서관계 (Partial Order Relation) 반사적, 반대칭적, 추이적인 관계 ex 1) 두 집합 A,B에 대하여 $ A \subseteq B$ 반사적 : $A \subseteq A$ 반대칭적 : $A \subseteq B \wedge B \subseteq A => A = B$ 추이적 : $A \s...