코딩뚠뚠

풀이 일시 : 2020-08-06 ​ 크루스칼알고리즘 : 가장 적은비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 최소비용신장트리를 만들기 위한 대표적인 알고리즘. ​ 문제 : 크루스칼 알고리즘으로 최소 비용을 계산하라 ​ 풀이 : 간선을 거리가 짧은 순서대로 그래프에 포함시키자 (간선정보를 오름차순 정렬후에 그래프에 포함) 1. 정렬된 순서에 맞게 그래프에 포함시킨다. 2. 포함시키기 전에는 사이클 테이블을 확인한다. 3. 사이클을 형성하는 경우 간선을 포함하지 않는다. #include #include #include using namespace std; //부모노드를 가져옴 int getParent(int set[], int x) { if (set[x] == x) return x; retu..

풀이 일시 : 2020-08-05 ​ 큐 : first in first out ​dbstndi6316.tistory.com/27?category=953970 [개념정리] queue queue란 자료구조의 한가지로 FIFO구조로 데이터를 저장하는 방식 ​ queue의 사용 #include 선언 queue변수; queue q1; 사용 q1.push(element) //큐에 원소를 추가한다. (뒤에 추가하는것) q1.pop() //큐.. dbstndi6316.tistory.com 문제 : queue를 선언하고 q.push q.pop 사용 풀이 : #include #include using namespace std; int main() { queue q; q.push(7); q.push(5); q.push(4)..

풀이 일시 : 2020-08-05 ​ 스택 : 개념정리 dbstndi6316.tistory.com/26 [개념정리] stack stack이란 LIFO(Last In First Out) 형식의 자료구조이다. ​ stack사용 #include 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다 ​ 선언 stack변수; stack s1; 사용 s1.push(element) //.. dbstndi6316.tistory.com 문제 : stack을 선언하고 stack의 push와 pop을 사용해보자 풀이 : #include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6..

풀이 일시 : 2020-08-04 ​ 계수정렬 : 크기를 기준으로 세는 알고리즘이다. 그 크기에 맞는 숫자들의 갯수를 세는 것 ​ 문제 : 132432531234435123523143512111 을 정렬하라 풀이 : #include int main(void) { int count[6]; int array[30] = { 1,3,2,3,2,5,3,1,2,3,3,5,1,2,3,5,2,3,1,3,5,1,2,1,1,1 }; for (int i = 1; i

풀이 일시 : 2020-08-04 ​ 삽입정렬 : 거의 정렬되어있을때 빠른 알고리즘이다. 각 숫자를 필요할때만 적절한 위치에 삽입하는 방법이다. ​O(N^2) 문제 : 1,10,5,8,7,6,4,3,2,9를 오름차순으로 정렬하시오 ​ 풀이 : #include int main() { int array[] = { 1,10,5,8,7,6,4,3,2,9 }; int i, j, temp; for (i = 0; i = 0 && array[j] > array[j + 1]) { //현재값이 다음값보다 크면 SWAP temp = array[j]; array[j] = array[j + 1]; array[j + 1] ..

풀이 일시 : 2020-08-04 ​ 힙정렬 : 힙 트리구조를 이용하는 정렬방법이다. 힙정렬을 하려면 정해진 데이터를 힙구조를 가지도록 만들어야 한다. ( 힙은 최솟값이나 최댓값을 빠르게 찾아내기 위해 완전 이진트리를 기반으로 하는 트리이다. 최대힙은 부모노드가 자식노드보다 큰 힙이다. ) 힙생성 알고리즘 - 큰 자식과 자신의 위치를 바꾸는 것이다. 즉 O(logN) 전체 트리를 힙구조로 만드는 복잡도는 결국 O(N*logN) 이를 가지고 루트의 값을 가장 뒤쪽으로 보내면서 힙트리의 크기를 1씩 빼준다. 가장 뒤쪽으로 보낸 것은 정렬이 된 것이고 다시 나머지에 대해 힙생성 알고리즘을 수행해준다. 결국 전체 힙 정렬의 복잡도는 O(N*logN) 문제를 보면서 이해해보도록 하자. ​ 문제 : 7 6 5 8 ..

풀이 일시 : 2020-07-30 ​ 병합정렬 : 합병정렬 또는 병합정렬로 불린다. O(N*logN) 보장한다. 분할정복 알고리즘의 하나이다. -> middle을 기준으로 반으로 나눈다. (이를 재귀형식으로 계속 나눈다.) -> 나눈 것을 병합하며 정렬한다. -> 병합하는 중 남은 데이터들이 있다면 나머지를 다 넣어주는 과정이 필요하다. ​ 문제 : 76584591 을 오름차순으로 정렬하시오 ​ #define number 8 #include int size; int sorted[8]; int count = 0; void merge(int a[], int m, int middle, int n) { //합칠 때 숫자를 비교하여 합치는 부분 int i = m; //첫번째 배열의 맨 앞 int j = middl..

풀이 일시 : 2020-07-28 ​ 퀵정렬 -> 피벗값을 설정하고 나눈다. 보통 첫번째 원소를 피벗으로 설정 -> 피벗값보다 큰 값을 왼쪽부터 찾고 피벗보다 작은값을 오른쪽부터 찾는다. -> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 크면 값끼리자리바꿈 -> 피벗값보다 작은값,큰값찾으면 : 작은값의 인덱스가 큰 값의 인덱스보다 작으면 피벗과 작은값 자리바꿈. 시간복잡도는 O(N*logN) ​ 문제 : 1 10 5 8 7 6 4 3 2 9 다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하시오 풀이 : #include int number = 10; int data[] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 }; void quickSort(int* data..