Algorithm
-
Prim AlgorithmAlgorithm 2020. 11. 11. 13:54
[Algorithm] Prim Algorithm Kruskal과의 차이 : 프림 알고리즘은 한 정점을 기점으로 확장한다. (kruskal은 간선의 가중치 중심) Time Complexity pq에 간선은 각각 1번씩 삽입/삭제된다. O(ElogE) / Insert : O(logE) , Delete : O(logE) Flow 하나의 정점을 선택하여 최소 신장 트리에 추가한다. 최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중, 비용이 가장 작은것을 최소 신장 트리에 추가한다. ⇒ 해당 간선의 최소 신장 트리에 포함되지 않은 정점도 추가한다. 간선이 V-1개가 될 때까지 2를 반복한다. Implementation : 프림 알고리즘은 Heap으로 구현해야 Time Com..
-
Kruskal AlgorithmAlgorithm 2020. 11. 11. 13:54
[Algorithm] Kruskal Algorithm greedy하게 최소 신장트리를 구성한다. Greedy? 그 당시 순간에 최적의 선택을 하는것. 전체적인 관점으로 최종 결정이 최종이라는 보장은 없다. Time Complexity O(ElogE) : 간선 E개를 퀵정렬같은 알고리즘으로 정렬할 경우 신장트리 주어진 방향성이 없는 그래프의 subgraph들 중에서 모든 정점을 포함하는 트리. 조건 모든 정점을 포함한다. 트리구조이다. ( 사이클이 없고, 연결된 그래프이다. 그래프의 정점이 V개일때, 간선은 V-1개이다 ) SubGraph : 주어진 그래프에서 일부 정점과 간선만을 선택해서 만든 새로운 그래프. 최소 신장 트리 : 간선의 합이 최소인 트리 ( 동일한 그래프에서 여러가지로 나타낼 수 있다.)..
-
[Sort] Bubble SortAlgorithm/Sort 2020. 11. 11. 13:52
[Sort] Bubble Sort 매번 연속된 두개의 인덱스를 비교하여 조건에 맞게 위치를 바꾸는 정렬. Time Complexity O(N^2) Space Complexity O(N) FLOW 현재 인덱스 값과 바로 이전 인덱스 값을 비교한다. 이전 idx에 있는 원소가 더 크면 둘의 위치를 변경한다. 현재 idx가 더 크면, 다음 idx로 넘어가서 두개를 다시 비교한다. for(int i=0; i sorted flag를 사용하면 개선 가능하다. 중간에 한번이라도 원소의 교환이 일어나면 flag의 상태를 변경해준다. 바뀌지 않았으면, 교환이 일어나지 않은 정렬된 상태이다. => 만약 정렬된 상태의 배열이 들어오면 Θ(n)만에 수행 가능하다. for(int i=0; i
-
[BOJ] #1946 신입 사원Algorithm 2020. 11. 11. 13:50
[BOJ] #1946 신입 사원 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로..
-
[BOJ] #1700 멀티탭 스케줄링Algorithm 2020. 11. 11. 13:50
[BOJ] #1700 멀티탭 스케줄링 문제 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다. 예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 키보드 헤어드라이기 핸드폰 충전기 디지털 카메라 충전기 키보드 헤어드라이기 키보드, 헤어드라이기, 핸드폰 충전기의 플..
-
Two Pointer AlgorithmAlgorithm 2020. 11. 11. 13:49
[Two Pointer Algorithm] 직관적으로 보았을 때, O(N^2) 이상으로 해결해야 하는 문제를, O(N)에 해결 가능하다. 조건 연속되는 value들을 이용하여 특정 목표에 맞는 값을 찾아주는 알고리즘. 연속성을 활용하는 것이 특징이다. 주어진 값들을 그대로 활용하거나, 정렬을 통해서 연속성을 추가해줄 수 있는 경우에 사용 가능하다. Example - 배열의 구간합이 특정 값을 만족해야하는 경우 배열의 원소가 모두 양수라면, 구간을 증가시킬 경우 구간합도 증가한다. 만약 계속 커지다가 특정 수를 초과하면? ⇒ left pointer를 증가시킨다. FLOW left = 0, right = 0, sum = 0, num = 달성해야 하는 구간 합으로 설정한다. while(1) 내에서 if(sum..
-
Dijkstra AlgorithmAlgorithm 2020. 11. 11. 13:48
[Algorithm] Dijkstra Algorithm 모든 간선 가중치가 음이 아닌 경우, 최단 경로를 구할 수 있다. 단일 시작점 최단 경로 알고리즘이다. 입력 그래프 G = (V,E)에서 간선들의 가중치가 모두 0 이상인 경우의 최단 경로 알고리즘이다. //pseudo code Dijkstra(G,r){ // G = Graph, r = start node S = {}; // 정점의 집합 for each u in V { d[u] = INF; //무한으로 초기화 } d[r] = 0; while(S != V){ u 정점의 최단거리가 INF가 아닌 수에서 갱신이 되는것은, 이미 경로는 발견되었지만 가중치의 값이 더 짧아졌을 때 이다. Priority Queue(Heap)을 사용하여 구현 가능하다. Time..
-
[STL] C++ STL - DequeAlgorithm 2020. 11. 11. 13:47
C++ STL - Deque vector의 단점을 보완하기 위해 만들어진 컨테이너. deque도 vector와 마찬가지로, 배열 기반의 자료구조이다. vector는 새로운 원소가 추가될 경우 메모리 재할당 이전 원소 복사 를 진행하므로 삽입시에 성능이 저하한다. Deque는 메모리가 부족할때마다 일정 크기의 새 메모리 블록을 할당한다. (이전원소를 복사하는 방식이 아님) ⇒ 여러개의 일정 크기 메모리블록을 할당하고, 하나의 블록처럼 여기는 것이다. d.at(idx); // idx번째 원소를 참조한다. == d[idx] d.front(); d.push_front(idx); d.pop_front(); d.push_back(idx); d.pop_back(); d.clear(); deque는 중간 삽입도 가능하..