해나의 컴공생존기

Convex Hull 이란 평면 좌표에서 어떤 점들이 있을 때 모든 점들을 포함 하는 가장 작은 볼록 다각형을 의미한다. (점들의 바깥에서 고무줄을 놨을 때 만들어지는 도형) 점들을 정렬하는 과정이 필요하기 때문에 Convex Hull 을 만드는 알고리즘의 시간 복잡도는 O(nlog n)보다 빠를 수 없다. 1. Count - Clock - Wise (CCW) 이 알고리즘은 세 점이 관계를 표현할 때 유용하다. A(x1,y1), B(x2,y2), C(x3,y3)가 있다고 해보자. A와 B의 기울기 + B와 C의 기울기를 가지고 회전 방향을 알 수 있다. A와 B의 기울기 > B와 C의 기울기 → 우회전 A와 B의 기울기 < B와 C의 기울기 → 좌회전 A와 B의 기울기 = B와 C의 기울기 → 한 직선 ..

1. Closest pair Closest pair은 주어진 점들 중에서 가장 가까운 쌍을 찾는 문제이다. 이 문제는 직관과 심하게 충돌하는 경우가 많다 1차원일 때는 단순하게 sorting 하면 구할 수 있고 2차원일 경우 두 점사이의 거리공식으로 구할 수 있다. 하지만 이 경우에는 O(n^2) 이 필요하다. 이 방법은 어렵지 않다. 우리의 목표는 O(nlogn)이다. 2. Divide and Conquer 먼저 이들을 절반으로 나눈다. (나누는 것은 x 를 기준으로 sorting 한 뒤 나눠주면 된다) 나눠거 각각 가장 최소거리를 구해준다. 왼쪽의 최소걸이는 DL 오른쪽의 최소거리를 DR이라고 하자. D = min(DL , DR) 라고 D를 정의하자. 중심 선으로부터 D만큼의 거리에 선을 그으면 위 ..

1. Selection Problem and Approximate Median quick sort에서 우리는 어떻게 가장 좋은 pivot을 얻을 수 있을까? 만약 우리가 O(N)에 best pivot을 뽑으면 최악의 경우가 O(nlogn)가 되지 않을까? Selection Problem 은 k번째 작은 것들을 찾는 것이다. 이것은 median을 찾는것과 비슷한 시간복잡도는 갖는다. Selection Problem을 O(nlog)으로 구현하는 것은 쉽다. 그냥 sorting 하면되기 때문이다. 하지만 O(nlog)은 필요가 없다. 2. Selection Approximate Median with Quick Sort pivot으로써 Approximate Median을 찾으면 quick sort를 O(nlog..

1. Quick Sort Quick Sort의 알고리즘을 한번 보겠다. 1. 배열에서 하나를 pivot으로 설정한다. 2. 배열의 가장 앞을 가르키는 i와 가장 뒤를 가르키는 j로 설정한다. 3. i와 j가 만날때까지 아래의 과정을 반복한다. 3-1. i가 가르키는 값과 pivot이 가르키는 값을 비교해서 i가 더 작다면 pivot보다 더 큰 숫자를 만날때까지 i를 증가시킨다. 3-2. j가 가르키는 값과 pivot이 가르키는 값을 비교해서 j가 더 크다면 pivot보다 더 작은 숫자를 만날때까지 j를 증가시킨다. 3-3. 둘다 적절한 값을 찾는다면 i가 가르키는 값과 j가 가르키는 값을 바꾼다. 4. 반복문을 나왔다면 pivot값과 j가 가르키는 값을 교환한다. 5. 처음부터 j까지, j 다음부터 끝까..

1. 에이전트의 개념 에이전트란 특정 환경 (environment) 내에 위치하여, 설계된 목적 (objectives)을 만족시 키기 위하여, 자율적(autonomous)으로 유연하게 (flexible) 행동할 능력이 있는 컴퓨터 시스템이다. 인공지능에서의 문제의 주체라고도 할 수 있다. 1.1 지능형 에이전트 지능형 에이전트는 센서로부터 인지된 주변 환경을 인지 (Perception) 하고 효과기(actuator)를 통해 외부환경에 적절한 행동을 취할 수 있는 로봇/기계/소 프트웨어 1.2 다중 에이전트 시스템 각각의 다른 task를 가진 에이전트들끼리 상호작용(interaction)을 통하여 각 에이전트의 목적을 달성하는 시스템이다. 다중 에이전트 시스템이 원활하기 위해서는 아래와 같은 관계가 성립되..

1. Problem Definition N개의 데이터 아이템이 있다. 각 데이터 Di는 (Li ,Fi)로 이루어져 있다. Li은 데이터의 사이즈 , Fi은 사용 빈도수이다. 테이프에는 데이터를 한번만 쓸 수 있고, 읽는것은 무제한이다. 데이터를 읽으러 가는 모든 때의 시작점은 맨 처음이다. (데이터를 읽고나서 매번 맨 앞으로 돌아간다) 직관적으로 보면 크키가 클수록 뒤에 있고 자주 쓰는 것을 앞에 배치하면 좋겠다는 생각이든다. 하지만 자주 쓰는데 크기가 너무 크다면..? 이라는 애매한 상황이 생긴다, 2. Solution F/L 순서대로 저장하면 된다. (greedy) Proof 기대값은 빈도수 * 맨 앞에서 해당 데이터 까지의 L 라고 정의할 수 있다. 귀류법으로 증명을 해보겠다. Assume : Fi..

1. Problem Definition J1, J2,...,JN 이라고 표기되는 N개의 job이 있다. 각 J는 (D,P) 로 쓰이는데, D는 deadline이고 P는Profit 이다. 1시간 단위의 타임슬롯이 있고 모든 일은 1시간이 소요된다 ex) (2,2) , (1,3), (1,1) 또, 이 문제는 아래의 가정을 따른다. 모든 deadlines은 N이하라고 가정한다. (N보다 크면 N으로 생각해도 됨) Job들은 내림차순으로 정렬되어있다. Deadline 이후의 일은 안나온다고 가정한다. 직관적으로 보면, 이익이 큰 것부터 최대한 뒤쪽에 배치하는 것이 효율적인 것을 알 수 있다. 최대한 뒤쪽에 두는것이 다른 Job들에게 방해가 될 가능성이 적어보이기 때문이다. 이것도 Greedy 알고리즘이다. 2...

1. Shortest Path 시작은 한군데지만 모든 목적지로 가는 shortest path를 다 구한다. shortest path의 모든 부분은 shortest path이다. 이는 여러가지 버전이 있다. 길이만 구하기 길이와 Path 구하기 가능한 여러개의 Path 구하기 2. Dijkstra Algorithm 이 알고리즘에 대해 설명해보겠다. 먼저 몇가지 정의를 하고가면 R: 정답이 확정된 노드들의 집합 B: Red Set에 있는 노드들만 거쳐서 갈 수 있는 노드들의 집합 Dmin : 최단거리 1) 먼저 시작 노드부터 각 노드까지의 weight를 dim에 기록한다. 연결이 되어있지 않으면 ∞라고 기록된다. 2) 시작 노드를 R에 넣고 아래의 과정을 반복한다 R 밖에 있는 Dmin(u)들 중 가장 작은..

1. Kruskal Algorithm 크루스칼 알고리즘의 기본 아이디어는 가장 작은 weight의 edge부터 하나씩 추가하는것이다. 단 사이클이 생기면 버리고 다음 weight의 edge를 확인한다. 위으 그림으로 예를 들어보겠다. 가장 작은 비용을 가진 edge는 1노드와 6노드를 잇는 10짜리 노드이다. 이것을 선택한다. 그 뒤로도 작은 순서대로 선택한다. 10, 12, 14, 16 이 다음으로 비용이 적은건 18이지만 18을 선택하면 사이클이 생기기에 그 다음인 22를 선택한다. 위와같이 사이클이 생기지 않게 작은 것들만 골라 spanning tree가 만들어지게 하면 된다. 증명 (proof by induction) 증명하기 전에 몇가지 가정을 이해해야한다. Tmst는 많은 정답 Edge set..

1. greedy Algorithm greedy 알고리즘은 선택을 반복하는 알고리즘들 중 비교적 간단하게 선택하고 선택한 것은 바꾸지 않는 알고리즘이다. 2. Minimum Spanning Tree (MST) Spanning Tree는 그래프의 모든 정점과 간선의 부분집합으로 구성된 부분 그래프이다. MST는 주어진 그래프의 연결 그래프들 중 엣지들의 비용이 최소가 되도록 하는 그래프이다. (단, 사이클을 생성X) 사이클이 있으면 안되는 이유는 사이클이 없어도 되기 때문이다. 사이클이 중 하나를 없애도 연결그래프는 유지가 된다. 게다가 비용까지 감소가 된다. 우리는 '최소'를 찾고 있으므로 사이클이 있을필요가 없다. 아니, 있으면 안된다. 3. Prim Algorithm 프림 알고리즘의 아이디어는 먼저 ..