팀 정렬(Tim sort) 개요 일반적으로 정렬 알고리즘 중에 평균적인 상황에서 가장 빠른 알고리즘은 힙 정렬, 병합 정렬, 퀵 정렬이라고 알고 있을 것이다. 이렇게 빠르다고 알려진 알고리즘을 사용할 때도 주의할 점이 있다. 먼저 최악의 상황에서의 성능이다. 퀵 정렬은 최악의 경우 O($N^{2}$)이다. 물론 메모리는 다른 정렬에 비해서 상대적으...

알파 베타 가지치기 이전의 Minimax 알고리즘으로 전체 경우의 수를 탐색 할 수 있다면 어떤 게임에서도 이길 수 있다고 했다. 그리고 체스만 하더라도 경우의 수가 너무 많기 때문에 전체 탐색을 할 경우 너무 많은 시간이 걸리기 때문에 탐색 깊이 제한을 둬서 응답 시간을 줄이는 방법을 사용한다고 했다. 그런데 굳이 탐색할 필요 없는 부분을 애시...

Mini Max 알고리즘 개요 상대방과 번갈아가면서 수를 두는 형태로 겨루는 게임의 AI를 짜는데 자주 사용되는 알고리즘이다. 최선의 수를 두었을 때의 이득을 계산하는 것이 아닌 실패했을 때 손실을 최소로하는 방향으로 탐색하는 방식이다. 영어로는 Minimax algorithm, 한국어로는 최소최대 알고리즘이라고 한다. 해당 알고리즘을 사용할 수...

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...