우주수첩의 우주먼지

Deque 양 끝 부분에 원소를 추가, 삭제를 평균 O(1)시간에 할 수 있는 자료구조 push_back : 끝부분에 추가 pop_back : 끝부분 삭제 push_front : 처음 부분에 추가 pop_front : 처음부분 삭제 insert : 중간에 추가 O(n) Doubled linked list에 비해서 access가 빠르다는 장점이 있다. 근데 링크드 리스크 자체를 경진대회에서 거의 안쓴다는 왈ㄹ랄라가 있지. #include // 헤더 파일 스윽 써주께에 deque d; d.push_back(5); //5 d.push_back(2); //5 2 d.push_front(3); // 3 5 2 d.pop_back(); // 3 5 d.pop_front();// 5

Vector 일반적인 dynamic array와 비슷하게 사용 가능하다. push_back : 맨 마지막 위치에 원소를 삽입 pop_back : 맨 마지막 위치의 원소를 삭제 위의 두 연산을 평균 O(1)시간에 수행 가능. insert : 원하는 위치에 element를 삽입 O(n)시간 소모. #include // 헤더파일 스윽 써주께에 vector v; v.push_back(3); // v : [3] v.push_back(2); // v : [3, 2] v.push_back(5); // v : [3, 2, 5] vector a(8) // size : 8, initial value == 0 vector b(8,2) // size : 8, initial value == 2 # Vector 에 있는 모든 원..

사이즈가 n인 array A가 있다. 해당 array의 inversion의 개수를 출력하는 프로그램을 작성하여라. #그냥 구현하기 #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int inversion_count = 0; for (int i = 0; i arr[j]) inversion_count++; } } cout arr[j + 1]) { temp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = temp; inversion_count++; } } }..

Insertion Sort 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 매 순서마다 해당 원소를 삽입할 수 있는 적절한 위치를 찾아 해당 위치에 삽입한다. 삽입정렬은 두 번째 자료부터 시작하여 해당 위치 기준 왼쪽의 자료들과 비교하여 삽입할 위치를 지정한다. 이는 기준점의 왼쪽의 자료들은 모두 sorted상태임을 알 수 있다. 처음 key 값은 두번째 자료부터 시작한다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int j; for (int i = 1; i < 10; i++) { int ..

Selection Sort 제자리 정렬 알고리즘 중 하나. 정렬되지 않은 입력 배열 외에 다른 추가 메모리를 요구하지 않는다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘. 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓는 행위를 반복하며 정렬을 수행한다. 1회전을 하고 나면 가장 작은 값의 자료가 맨 앞에 위치. 다음 회전에는 두번째 위치의 배열부터 처리한다. 정렬 과정 주어진 배열에서 최소값을 찾는다. 현재 범위 내에서 맨 앞의 값과 교환한다. 교환한 위치를 제외한 나머지 배열을 같은 방법으로 교체한다. 하나의 원소만 남을 때 까지 반복한다. #include #include using namespace s..

BUBBLE SORT 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 => 인접한 두 개의 원소를 비교하여 순서대로 되어있지 않을 경우 서로 교환한다. => array[3] 제외되는 데이터가 하나씩 늘어난다. #include #include using namespace std; int main(void) { int arr[10] = { 4,5,6,2,3,10,8,1,9,7 }; int temp; for (int i = 0; i arr[j + 1]) { temp = arr[j + 1]; arr[j ..

최소 스패닝 트리(MST)를 만들기 위한 방법 중 하나. (+ 프림알고리즘) 1. 모든 간선들의 가중치를 오름차순으로 정렬한다. 2. 가중치가 가장 작은 간선을 선택한다. 3. 선택한 간선이 연결하려는 2개의 노드가 아직 서로 연결되지 않은 상태라면 2개의 노드를 서로 연결한다. 4. 반복. => 최소가중치를 가진 간선들을 사이클이 발생하지 않게 계속 연결하여 MST를 찾는다. 시간 복잡도 : O(mlog n) 구현 가장 작은 가중치를 갖는 간선이 연결하고자 하는 두 노드가 연결되어있는지 확인해주는 과정에서 많이 사용하는 방식이 Union-Find이다. 이전에 Union_Find를 다룬 적이 있는데 이를 이렇게 적용할 줄이야 하하핳. parent[] 코드 구현시에 대중적으로 많이 사용하는 방법은 pare..

Graph 그래프는 Vertex(정점)들의 집합 V(G)와 두 vertex를 이어주는 edge(간선)들의 집합 E(G)로 구성되어있는 구조 (G = V(G),E(G))로 표기한다. 방향성 그래프의 edge가 방향성이 있는지 없는지에 따라 Directed Graph, Undirected Graph로 나뉜다. Directed Graph : E(G)의 각 원소들은 ordered pair == 방향성이 있음. e=(a,b) != (b,a) : directed pair 는 방향성을 갖고 있기 때문에 vertex 순서도 중요하다. Undirected Graph : E(G)의 각 원소들은 unordered pair == 방향성이 없음. 인접하다 (v,u) 가 E(G)에 속해있을 때 adjacent(인접하다)라고 한다..

아니 수업에서는 C++을 사용하긴 하는데 한국에서는 아직 JAVA를 많이 쓰고 있기에 자바랑 C++이랑 한 번씩 알고리즘을 풀어야 할 것 같아.... 엉엉 ㅠ 아니야 오히려 좋아 자바 라이브러리 함수도 다시 익혀갈 겸 어짜피 다 잊은거... 내가 노력해야지...그치 맞지...? 이전 포스팅에서 사용했던.에라토스테네스의 체를 JAVA로 구현 해 보도록 하게.땨. 사실 1학년 때부터 자바를 접해와서 그랬던건지 이전 포스트에서 써 봐서 그랬던건지 여튼 자바로 구현하는 게 훨씬 더 편했다. 기분탓이라면 뭥... 유감 *^-^* 나름 열심히 구현 하고 실행을 시켰는데 결과가 환상적이다. 아무리 봐도 테네스씨의 체는 구현을 잘 한 것 같은데 왜 그럴까 하고 냅다 디버깅을 해보니. 출력에서 문제가 있더라 망할 형변환..