Category: 알고리즘

[알고리즘] Convex Set과 특징 0

[알고리즘] Convex Set과 특징

1. Convex Set Convex Set이란, 집합 `S`에 포함된 어느 두 점 `p`, `q`를 선택하여 점들을 연결하는 직선을 모두 포함하는 덩어리를 의미한다. 즉, 특정 점들의 집합이 아닌, 이를 감싸고 있는 공간이라고 생각하면 된다. 아래의 그림...

[알고리즘] Convex hull과 Graham’s scan 1

[알고리즘] Convex hull과 Graham’s scan

1. Convex hull Convex Hull이란, 점들로 구성된 Set을 모두 포함하는 외각 점들의 집합이다. 아래의 그림을 보자. 출처 : 위키피디아 검은 점들로 구성된 집합 `S`에서 어느 점을 선택하더라도, 파란색 선안에 포함되는 것을 알 수 있다....

[알고리즘] 시간 복잡도 계산 / 마스터 정리 0

[알고리즘] 시간 복잡도 계산 / 마스터 정리

시간 복잡도 계산, Master’s theorem / 마스터 정리 1. 시간 복잡도 시간 복잡도란? 특정한 프로그램의 실제 동작 시간이 아닌, 입력 데이터의 크기 n에 대하여 기본적 연산의 횟수를 측정하는 것을 의미한다.   시간 복잡도를 표현하는...

[알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법 4

[알고리즘] 시간 복잡도, 점근적 분석법 그리고 표기법

1.  시간 복잡도 시간 복잡도 (Time complexity)는 컴퓨터 공학에서 사용되는 알고리즘을 입력의 크기에 관계해서 나타내는 방법이다.   왜 절대 시간을 쓰지 않을까? 절대시간은 사실 컴퓨터 환경 의존성이 심하다. 예를 들어, A 알고리즘은 B 컴퓨터에서 1초동안 100개의...

Translate »