Closest pair Computational Geometry직관과 심하게 충돌하는 경우 많음주어진 점들 중에서 가장 가까우 쌍을 찾기(2차원)Usually Input is given by Coordinates좌표 형태로 입력이 들어온다. (a,b), (c,d)가 주어진다면 -> \(\sqrt{(a-c)^2 + (b-d)^2}\) 을 모든 쌍에 대해서 하면 \(n^2\)개가 생기고 이 중에 제일 작은거 찾으면 됨sqrt()라는 함수로 루트를 계산할 수 있지만, 무리수이기 때문에 정확한 계산이 불가능하다.  1 - Dimensional Versionsorting 후, 가장 옆에것과의 거리를 비교하여 가장 짧은 것을 고르면 됨Divide and ConquerFirst, Sort by x coordinate..

O notation에서 상수가 차이가 나기 때문에, 이 안에서 어떤게 더 좋을지 판단할 수 있다. 그런 류의 아주 복잡한 문제를 Quick Sort가 만들어낸다.  앞으로 이야기 하는 이야기에서는 Quick Sort가 그렇게 좋지 못하다는 것을 알게 될 것임. *Worst일 때는 merge sort가 더 좋다. 우리는 이걸 O(NlogN)으로 만들고 싶다.실제로는 merge보다 quick이 빠르다. 따라서 worst case만 고치면 O(NlogN)이 되면서 merge보다 빠르게 될 것이다. In Quick Sort : can we Find the Best Pivot?if we can do it in O(N), Quick Sort will run in Worst Case O(NlogN) time따라서, ..

Divide and Conquer입력을 나누어,더 작은 문제를 풀고작은 문제들의 답을 조합하여전체 문제듸 답을 만든다.아주 작은 문제는 어쨌는 풀 수 있다.  수 하나가 주어질 때도, 값이 큰지 작은지에 따라 다르다.어떤 문제든지 간에 size라는 것이 있고, 문제를 작게 나누어서 작은 문제를 풀고 이러한 답을 큰 문제를 푼다.이러한 작은 문제들은 재귀를 사용할 수 있다.  Recursive Merge Sortn개가 있다면, n/2로 나누고, 그것을 또 나누고.. 이를 반복하여 하나씩 남을 때까지 나눈다.이를 나누어서 목적지 배열에 Merge Alg를 사용해서 sorting을 한다. Merge Alg -> O(n) 왼쪽부터 하나씩 보면서 움직이는 것이므로 n번 걸린다.  https://m-in-zu.ti..

Problem Definition1차원으로 된 테이브에 내가 원하는 것을 찾으러 가는 것이 굉장히 오래걸림N Data Items, Parameters \(L_i\), \(F_i\)\(L_i\) : Size of data = Length on Tape\(F_i\) : Frequency of Usage Read and Write Data on a TapeWrite once, everythingRead many timesEach read starts from the Beginning of Tape>> 어떤 순서로 배치하면 좋을까?idea) 큰게 앞에 있으면 뒤에를 읽으러 갈 때마다 큰거를 읽으면서 가야한다. 즉, 큰게 앞에 있으면 좋지 않다자주 쓰는게 앞에 있어야한다.  Algorithm Just Store ..

Problem DefinitionN Jobs, \(J_1\), \(J_2\). ..., \(J_N\)Each \(J_i\) = (\(D_i\), \(P_i\)) > \(D_i\) : Deadline, \(P_i\) : ProfitThere are time slots where you can schedule jobsEach job takes 1 slot to finishprofit은 이익, deadline 전에 끝내야한다.  어떠한 1차원 배열이 있다고 생각하고, 어떤 job가 slot에 들어가는지 생각해보자 ex) {(2,2), (1,3), (1,1)}deadline이 1인게 2개 있기 때문에, 그 중 하나밖에 할 수 없다. 최대 profit은 5가 된다.  AssumptionAll deadlines a..

BFSFrom BFS에서 시작하여 다익스트라를 증명할 수 있다.모든 엣지의 weight가 1이라고 할 때 shortest path를 찾을 수 있다.  queue를 사용함src에서 시작을 해서 src를 0으로 하고, 거리를 아는 것을 다 queue에 넣음.이후, 또 인접하는걸 모두 넣는다.거리가 1인 얘들이 전부 queue에 들어가야 거리가 2인 애들이 전부 queue에 들어갈 수 있다. 1이 전부 나와야 2가 전부 들어갈 수 있다. 2,3,4도 모두 같은 방식으로 queue에 들어왔다가 나옴  찾을 수 있지만 굉장히 느리다. edge weight를 1로 만들기 위해서 dummy node를 중간 중간에 넣어 모든 edge의 weight가 1이 되도록 한다.> 그래프가 매우 커지고 느려진다.  S에 가까운 ..

Dijkstra AlgorithmVersion of DijkstraOnly Shortest Path Length for each Node 경로를 구하는 것이 아니라 길이를 구하는 것Actual Path for each Node also 패스 노드까지 구함All possible Shortest Paths for each Node 모든 shortest path를 구함 - compact하게 표현하는 방법이 필요함Alternate ExplanationsAs a Variation of BFSSelect from Nearest to Furthest계속 짧은 길을 붙여나가는 방식은 shortest path를 찾을 것 같지만, 그렇지 않다. Shortest Path기 때문에 prim 처럼 풀 수 없다.  Shortes..

Prim을 위해 만들어야할 것priority queue노드 Marking 배열그래프#include #include using namespace std;//TRI를 만들 것 노드, 노드 , wight 형태로 저장되는 것class TRI {public: int a, b, w;};//priority queueclass PQ {public: int n; TRI Arr[1000]; PQ(); //생성자 TRI Delete(); //삭제 void Insert(TRI x); //삽입 int isEmpty(); //비어있는지 확인};PQ::PQ(){ n = 0;}int PQ::isEmpty(){ return n == 0; //n에 들어있는게 없다면 0을 리턴}//prio..

Greedy Alogrithms답을 찾기 위해 선택을 반복하는 알고리즘비교적 간단한 방법으로 선택선택한 후 바꾸지 않는 알고리즘ex) selection sort -> greedy 전체에서 가장 작은걸 찾아서 새 배열의 첫번째 배열로 "선택"하여 옮김 선택하는 것은 가장 작은것을 고름 (선택을 한 쪽의 배열에서는 없어졌다고 생각)남은곳에서 또 제일 작은 것을 고르는 과정을 반복 Shortest path ideaS에서 B까지 가는 가장 짧은 길을 찾는다고 하자* S에서 A까지 가는 가장 짧은 길 등등을 찾는것과 같다. 해당 짧은 길을 찾으려면 많은 가장 짧은 길을 찾아야한다. S에서 나가는 것 중에 제일 작은 것은 5이고 C에 도착C까지 가는 5보다 짧은 길이 있는가? -> 없음 : 다른 길을 가는 순간 이..

인터넷 : TCP / IP를 사용하는데 이는 transport layer / network layer이다.IP addressing32-bit identifier for host and router interface8bit.8bit.8bit.8bit로 나타내며 .을 통해 구분됨router의 각 port들의 ip address들을 표현했고, 그 밖은 host들의 ip address이다. 왼쪽 세개의 호스트와 라우터 인터페이스는 233.1.1.xxx 형식의 IP 주소를 가진다.4개의 인터페이스가 중계하는 라우터 없이, 하나의 네트워크에 연결되어있는 것이다. (LAN or AP로 연결)세 호스트들의 인터페이스와 하나의 라우터 인터페이스가 subnet을 구성하는 것이다.따라서 233.1.1은 subnet 구분을 ..