알고리즘

"알고리즘을 왜 배워야 하는가?"에 대한 해답

고등학교 시절에도 배웠지만, 수학적 귀납법은 알고리즘의 기초이자 명확히 지켜야 할 규칙임.

Greedy Algorithm

Kruskal은 간선을 중심으로 생각한다.

Shortest Path(최단 경로)는 가중치가 있는 그래프에서 어떤 정점에서 다른 정점으로 이동하기까지 가장 짧은 가중치의 합으로 목적지에 도달하는 방법을 찾기 위한 전략이다. Dijkstra Algorithm Red Node / Blue

Deadline Scheduling

Job Scheduling 문제 정의 N개의 일들이 있다. $J{1}, J{2},, ... J_{n}$으로 정의한다. 각각의 일 $J{i} = (S{i}, T_{i})$ $S_{i} = 시작 시간(Deadline)$ $T_{i} = 끝나는 시간(P

Merge sort merge sort는 여러개의 자료를 한번에 정렬하지 않는다. 대신 먼저 작게 나누고, 나눈 자료들을 정렬하며, 정렬한 자료들을 재배치한다. $O(nlogn)$의 시간 복잡도를 가진다. 새로운 배열을 만들어야 한다는 점에서 공간이 많이 들고 어느

Closest Pair Computational Geometry 도형과 기하에 관한 문제들 직관과 심하게 충돌하는 경우 많음 주어진 점들 중에서 가장 가까운 쌍을 찾기 (2차원) 입력은 점들의 좌표들(Coordinates)로 주어짐 $O(n^2) O(n)$ 아무리 빨라도 1차원보다 빠르지 못함. 왜냐하면 1차원을 포함하기 때문 1-Dimensional ...

Convex Hull convex hull은 좌표평면과 도형에 관련한 문제이다. 좌표평면에서 여러가지 점들이 있을 때, 이 점들을 모두 포함하면서 크기(블록)가 제일 작은 도형을 만드는 문제이다.

Matrix Multiplication 2차원 $N^2$배열을 곱하는 과정은 $O(N^3)$의 시간이 소요된다. 한 칸을 만드는데 $O(N)$의 시간이 걸린다. 모두 $N^2$개가 있다. 그러므로 $O(N*N^2) = O(N^3)$ >$O(N^3)$는 너무너무 느리다

배열끼리 곱하는 최적의 수를 구해보자

비슷한 문자열을 비교하는 방법이다

최대 공백 정사각형

동전 거스름 돈 N원의 거스름 돈을 돌려주야 한다. $M{500}, M{100},...,M_{k}$등의 동전들이 있으며, 각각 가격은 500, 100, 등등 이다. 동전들의 종류는 각각 다르다. 최소 개수의 동전을 사용하여 거스름 돈을 돌려주는 방법을 구하여라 예를 들어 1원, 4원, 6원 동전 $M1, M4,M_6$이 무한히 있다. 8원을 거슬러 줘야 하...