어제의 나보다 성장한 오늘의 나

알고리즘 도시를 하나 씩 옮겨가면서 첫 번째 도시~ 현재 도시 중 가장 주유 값이 적은 것을 선택한다. 현재도시~다음 도시 까지의 도로의 길이를 구한다. (첫 번째 도시 ~ 현재도시 중 가장 적은 주유값) * (현재도시~다음 도시 까지의 도로의 길이) 를 total에 더한다. 이 과정을 첫 번째 도시 부터 마지막 도시까지 적용하면 쉽게 구할 수 있다. Coding #include #include using namespace std; int main(int args ,char** argv){ int N ; long long int temp; cin >> N; vector street; vector cost_gas; for(int i = 0 ; i > temp; street..

◎ next , prev 두개의 노드 포인터를 가지고 있다. ◎ Single Linked List에 비해 함수 처리가 더 용이하고 접근성이 더 뛰어나다. ◎ 맨 앞에는 head 노드 , 맨 뒤에는 tail 노드가 있다. ◎ 삽입 / 삭제가 빠르다. 구현 구조체 1) Node Struct struct Node{ int data; // data in Node. Node* prev; // pointing before Node. Node* next; // pointing after Node. }; using pNode = Node*; 2) List Struct struct List{ Node* head; // front of list. Node* tail; // end of list. List(){ head =..

Heap 이란? ◎ complete binary tree (parent node는 2개의 child node를 갖는다.) ◎ parent 와 child 간에 항상 대소 관계가 성립 ◎ parent node가 child node 보다 항상 크면 max heap, 항상 작으면 min heap ◎ max heap일때는 최상위 node가 가장 크고 , min heap일때는 최상위 node가 가장 작다. ◎ array의 index는 1 부터 사용한다. ◎ child index는 (parent_index)*2 , (parent_index)*2+1 ◎ 반대로 parent index는 (child_index) / 2 1. heap 구현 Array를 이용하여 Maxheap을 구현해보았다. 변수 / 생성자 / 소멸자 pr..

c++ 에서 array를 이용하여 stack을 구현하기. c++의 STL 중 하나인 Stack Container를 구현해봤다. Stack의 동작 원리 -LIFO (Last in First Out) : 가장 마지막에 들어온 값이 가장 먼저 나갈 수 있는 형태이다. 반대로 가장 먼저 들어온 값은 가장 마지막에 나갈 수 있다. Stack의 함수 1) empty - stack이 비어있다면 true를 return, 아니라면 false를 return. 2) push - 값을 stack에 집어넣는다. 3) pop - 가장 최근에 들어온 값을 stack에서 빼낸다. 4) top - 가장 최근에 들어온 값을 return. 5) size - stack의 크기를 return. 가 있다. 구현한 코드 설명 1) empty 스..

1. bubble sort 필요한 그림 : (array에 맨앞 index start ,맨 뒤 index end , 움직이는 index : index ) 시간 복잡도 : O(N^2) (오름 차순 정렬일 때,) 가장 큰 값 부터 가장 작은 값 까지 차례로 오른쪽에 한 개씩 정렬해나가는 방법이다. stable sort이다. ※ stable sort 란 같은 값들이 array에 있을 때, sort 전의 같은 값들끼리의 순서가 sort후에도 보장된다는 것이다. 예를 들어 sort 전 1 3 1 2 5 의 어레이가 있다고 했을 때 sort 후 1 1 2 3 5 가 될 텐데 stable sort를 했다면 sort 전 맨 앞의 1 이 sort 후 맨앞의 1 이되고, unstable sort를 했다면 sort 전 맨앞의..