코딩뚠뚠

풀이일시 : 2020-08-31 ​ 분할정복 : divide and conquer 로 성질이 똑같은 여러개의 부분문제로 문제를 나누어 해결하는 방법이다. 1. 문제 사례를 하나 이상의 작은 사례로 분할한다. 2. 작은 사례들을 각각 정복(conquer)한다. 재귀를 이용 3. 작은 사례에 대한 해답을 통합하여 원래 사례의 답을 구한다. 장점 - 문제를 나눠 풀어 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결. 단점 - 함수를 재귀적으로 호출하여 오버헤드가 발생, 스택 오버플루우가 발생하거나 과도한 메모리사용 가능성 쓰임 - 이분검색, 최대값찾기 및 여러 알고리즘문제풀이에 쓰인다. 아래는 분할&정복 알고리즘의 대략적인 묘사도이다. ​ 문제와 풀이 : dbstndi6316.tistory.com/10..

풀이일시 : 2020-08-30 ​ DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http://www.aistudy.com/heuristic/depth-first_search.htm ​ 문제 : DFS를 구현하라 ​ 풀이 : recursive하게 구현한다. #include #include #define MAX 9 using namespace std; int d[MAX] = { 0, }; //방문체크하는배열 vector a[MAX]; void dfs(int x) { if (d[x] == 1) return; d[x] = true;//방문체크하기 cout

풀이 일시 : 2020-08-16 ​ 위상정렬 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 큐 사용 ​ 문제 : topology sort 수행 ​ 시간복잡도 : O(V+E) ​ 풀이 : #include #include #include #define MAX 10 using namespace std; int n, inDegree[MAX]; vector a[MAX]; void topologySort() { int result[MAX]; queue q; for (int i = 1; i

풀이 일시 : 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..