IT세상

#include #define MAX_VALUE 9 using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int cnt[MAX_VALUE +1]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); for(int i=0; i

#include using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; void quickSort(int* target, int start, int end){ if(start >= end) return; int pivot = start; int left = start + 1; int right = end; while(left right) swap(target[pivot], target[right]); else swap(target[left], target[right]); } quickSort(target, start, right-1); quickSort(target, right+1, end); } int main(..

#include using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int main() { ios::sync_with_stdio(0); cin.tie(0); //속도 가속화 for(int i=1; i0; j--){ if(target[j] < target[j-1]){ swap(target[j], target[j-1]); } else break; } } for(int i=0; i

선택 정렬 : 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 시간 복잡도 : O(N^2) #include using namespace std; int n = 10; int target[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; int main() { for(int i=0; i

lower_bound, upper_bound 설명 https://develop-me-z.tistory.com/114 [C++] lower_bound, upper_bound (이진탐색) 헤더파일 #include lower_bound 찾으려는 value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함 사용법 lower_bound( develop-me-z.tistory.com #include using namespace std; int n, x; vector v; //값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수 int countByRange(vector& v, int leftValue,..

파라메트릭 서치(Parametric Search) : 최적화 문제를 결정문제(예/아니오)로 바꾸어 해결하는 기법 #include using namespace std; int n, m; vector arr; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for(int i=0; i> x; arr.push_back(x); } // 이진 탐색을 위한 시작점과 끝점 설정 int start = 0; int end = 1e9; // 이진 탐색 수행(반복적) int result = 0; while(start

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시간 복잡도 : O(logN) binarySearch 함수에서 vector 함수를 가져오는 경우 꼭 & 를 써준다 #include using namespace std; int n, target; vector arr; int binarySearch(vector& arr, int target, int start, int end){ while(start target) end = mid - 1; // 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else start = mid + 1; } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); // 원소의 개수(n)과 ..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 #include using namespace std; int n, m; int graph[201][201]; // 이동할 네가지 방향 정의(상 하 좌 우) int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; int bfs(int x, int y){ // 큐 구현을 위해 queue 라이브러리 사용 queue q; q.push({x,y}); // 큐가 빌 때까지 반복 while(!q.empty()){ int x = q.front().first; int y = q.front().second; q.pop();..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 #include using namespace std; int n, m; int graph[1001][1001]; bool dfs(int x, int y){ // 주어진 범위를 벗어나는 경우 즉시 종료 if(x=n || y=m){ return false; } // 현재 노드를 아직 방문하지 않았다면 if(graph[x][y] == 0){ // 해당 노드 방문 처리 graph[x][y] = 1; // 상하좌우 위치들도 모두 재귀적으로 호출 dfs(x-1, y); dfs(x, y-1); dfs(x+1, y); dfs(x, y+1); return t..

https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 스택 자료구조 설명(선입후출) 스택 동작 예시 스택 구현 예제 stack s; // 선언 s.push(x); s.pop(); 큐 자료구조(선입선출) 큐 구현 예제 queue q; //큐 선언 q.push(x); q.pop(); 재귀함수 설명 재귀 함수의 종료 조건 DFS(Depth-First Search) 깊이 우선 탐색 - 그래프에서 깊은 부분을 우선적으로 탐색 - 스택 자료구조 혹은 재귀 함수 사용 #include using namespace std; bool visited[9]; vector graph[9]; void dfs(int x)..