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

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net upper_bound(), lower_bound() [C++] lower_bound, upper_bound (이진탐색)/ 예제 헤더파일 #include lower_bound 찾으려는 value 값보다 같거나 큰 숫자가 배열에서 처음 등장하는 위치 리턴 사용 조건 : 탐색을 진행할 배열 또는 벡터가 오름차순 정렬되어 있어야 함 사용법 lower_bound( deve..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 해결 방법 상근이가 가지고 있는 카드를 정렬해준다 이분탐색을 사용한다 #include using namespace std; int n, m; vector a, b; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i=0; i> x; a.push_back(x); } sort(a.beg..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 유의사항 자른 길이의 합을 구할때 나무가 자르는 길이보다 큰 경우에만 수행이 되도록 조건을 넣어주어야 한다 자른 길이와 길이의 합은 long long int 형으로 선언해주어야 한다 #include using namespace std; int n, m; vector v; int main(void) { ios::sync_with_stdio(0); cin.tie..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net dfs를 활용하여 풀었다 #include using namespace std; int n; int graph[26][26]; vector num; int sum = 0; bool dfs(int x, int y){ // 범위 밖인 경우 if(x=n || y=n){ return false; } if(graph[x][y] == 1){ // 집인 경우 sum += 1; // 집 수 +1 graph[x][y..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 방법 길이는 int 형의 범위를 넘어가기 때문에 long long int 형으로 선언해준다 (개수는 상관없음) 문제에서 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 의 예시를 보면, 만들어지는 랜선의 개수를 셀 때 랜선의 길이를 빼는것이 아니라 나눈 몫을 더해주어야 한..

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,..