하루에 하나씩 개발 공부

chaining node structure 이의 구성은 각각의 vertex를 설정한 후에 link각각의 vertex에 따른 link 또한 설정한다. bfs, dfs dfs는 preorder 형식으로 VLR 형태로 순환한다. bfs는 levelorder 형식으로 너비우선탐색을 진행한다. 스패닝 트리 minimum cost spanning tree은 세가지 algoritm에 사용된다. - Kurscal's algoritm 가중치가 작은 간선중에 사이클이 만들어지지 않을 때에만 연결한다. - Prim's algoritm 루트 노드 부터 시작해서 가중치가 작은 노드만을 연결해서 나간다. disjoint union 분리 집합 트리들을 합칠 때에 있어서 부모 노드 끼리 연결을 함으로서 합쳐주는 방식이다. aoe,a..

graph는 트리와 구성요소가 같지만, 사이클을 이루는 자료구조이다. 그래프에는 두가지 종류가 있는데, undirected graph와 directed graph가 있다. undirected graph는 방향성이 없는 그래프이고, directed graph는 방향성이 있는 그래프를 말한다. completed graph는 모든 node(vertex)들이 연결되어 있는 그래프를 뜻한다. 따라서 completed graph의 edge, 간선의 최대 개수는 undirected의 경우에는 방향이 없으므로 노드개수가 n이라고 하였을때에, n(n-1)/2로 나타낼수 있다. 방향이 있는 경우에는 최대 개수가 n(n-1)이다. 표현 같은 경우에는 아래와 같이 나타낸다. multi graph : 두 꼭짓점 사이에 여러 간..

complete binary tree : 마지막 level을 제외하고 모두 채워져 있고, 왼쪽 부터 차례로 채워진 경우를 뜻한다. full binary tree : 모든 노드가 0 아니면 2의 값을 가지도 있는 경우를 말한다. 따라서 leaf 노드를 제외한 모든 노드들이 자식을 두개씩 가지고 있다는 뜻이다. perfect binary tree : 마지막 level 까지 완벽하게 채워진 경우를 뜻한다. skewed binary tree : 한 쪽으로 치우진 노드를 뜻한다. Tree Traversal - inorder traversal : LVR - preorder traversal : VLR - postorder traversal : LRV 이를 재귀적으로 수행한다. 따라서 위와 같은 트리의 경우에는 po..

합병정렬이란 퀵정렬을 보완해서 나온 정렬 방법이라고 생각된다. 퀵 정렬은 기준값을 세운 후 왼쪽 오른쪽에 각각에 나누면서 정렬을 한다. 따라서 나누면서 이진트리 형태를 띄게 된다. 이에 최악의 경우에는 시간복잡도가 N^2이다. 이를 개선하여 처음부터 나누어진 수들을 합치면서 정렬을 한다. 나뉜상태에서 하기 때문에 NlogN으로 시간 복잡도가 일정하다. 코드로 표현하자면 위의 설명과 같이 시간 복잡도는 NlogN이다.

#include #include #include using namespace std; int N; int M; vector numbers; int flag[8]; int answer[8]; void makeCombination(int cnt) { if (cnt == M) { for (int i = 0; i > numbers[i]; } sort(numbers.begin(), numbers.end()); makeCombination(0); return 0; }

합병정렬이란 퀵정렬을 보완해서 나온 정렬 방법이라고 생각된다. 퀵 정렬은 기준값을 세운 후 왼쪽 오른쪽에 각각에 나누면서 정렬을 한다. 따라서 나누면서 이진트리 형태를 띄게 된다. 이에 최악의 경우에는 시간복잡도가 N^2이다. 이를 개선하여 처음부터 나누어진 수들을 합치면서 정렬을 한다. 나뉜상태에서 하기 때문에 NlogN으로 시간 복잡도가 일정하다. 코드로 표현하자면 위의 설명과 같이 시간 복잡도는 NlogN이다.

오늘은 퀵 정렬 알고리즘에 대해 알아보았다. 퀵 정렬 알고리즘의 아이디어는 기준(피벗)을 잡은 후 에 오름차순 정렬 기준으로 왼쪽에는 기준보다 작은 값, 오른쪽에는 기준보다 큰값을 배치 시켜 정렬시키는 것이다. 이를 토대로 코드를 구현해보자 붙여 설명하자면 맨 앞의 값을 기준점으로 잡은 후에 왼쪽에서 올라오면서 기준 보다 작은값을 탐색하고, 오른쪽에서 부터 내려오면서 기준값보다 큰 값을 탐색한다. 그리고 각각의 조건에 벗어나는 값들의 위치를 바꾼다. 이 동작을 각각 왼쪽, 오른쪽에서 내려오는 인덱스 값이 엇갈릴때 까지 진행한다. 엇갈리면 그지점의 값과 기준값의 위치(맨 처음)를 바꾼후에 그 바꾼 위치의 오른쪽 왼쪽 각각에 다시 똑같이 실행을 시킨다. 이 알고리즘에 시간복잡도는 반으로 쪼개서 왼쪽과 오른쪽..

오늘은 버블정렬을 공부하였다. 버블정렬은 선택정렬과 아주 유사한 방법을 사용한다. 선택정렬은 오름차순으로 정렬할때에 가장 작은 값을 가장 앞으로 가져온다는 해결방법을 사용했다. 이와 유사하게 버블 정렬은 나의 옆(주로 오른쪽)의 값과 비교하여 더 작은 값을 앞으로 배치하는 것이다. 예를 들어서 5 4 3 2 1 이라는 배열에서 위의 내용을 한번 하게 되면 결과값은 4 5 3 2 1 이렇게 5와 4 두 값만을 비교한 후에 그 두개의 위치만 바꾸는 것이다. 이를 배열을 한 번 다 순회를 하면 가장 큰 값이 가장 뒤로 가게 된다. 따라서 선택정렬은 가장 작은 값을 가장 앞으로 배치하는 것 이였지만, 버블정렬은 반대로 가장 큰 값들을 가장 뒤로 보낸다 라고 생각해도 될것 같다. 따라서 코드를 작성해 본다면 이렇..

오늘은 선택적 정렬 알고리즘에 대해 알아보겠다. 선택적 정렬은 오름차순으로 정렬한다는 것으로 생각했을때 "가장 작은것을 선택해서 제일 앞으로 보낸다"는 생각에 기초한다. 이 알고리즘을 간단히 작성한다 위의 알고리즘은 처음에 말했듯이 가장 작은 값을 가장 맨앞으로 라는 생각에 기초하여 반복문 두개를 돌면서 맨처음 부터 끝까지, 그다음 두번째 부터 끝까지 이렇게 시작하는 인덱스값을 1씩 증가시키면서 끝까지 돌면서 가장 작은 값을 앞으로 오게 하면서 오름차순 정렬을 이끌어냈다. 시간복잡도는 반복문을 두번 돌기 때문에 N^2 이다.