목록알고리즘/기타 (25)

키베이루's diary

[C++] 백준 1021번 회전하는 큐

1) 문제설명 2) 아이디어 STL의 덱을 사용하여 문제를 해결하였다. 덱에 1~N까지 숫자를 차례대로 저장하고 내가 찾고자 하는 숫자의 인덱스를 저장하고 그 값이 덱 사이즈의 절반보다 작다면 2번 연산을 실행, 절반보다 크다면 3번 연산을 실행하고 그 횟수를 카운트하여 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; deque dq; int n, m; int k; int arr[51]; int cnt = 0; void secal() { // 왼쪽으로 한 칸 이동시키는 함수 int temp; temp = dq.front(); dq.pop_front(); dq.push..
알고리즘/기타 2022. 9. 30. 09:50
[C++] 백준 2805번 나무 자르기

1) 문제설명 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 2) 아이디어 m미터의 나무를 잘라서 가져가야 하므로 이진 탐색을 이용하여 입력받은 배열들에서 mid를 빼고 그 값들(temp)을 다 더해 필요한 양만큼 가져가야 한다. 가져가야 할 양보다 temp 가 더 작다면 나무를 더 작게 잘라야 하고 가져가야 할 양보다 temp가 크거나 같다면 나무를 더 크게 잘라야 한다. 이분 탐색을 계속 돌면서 높이..
알고리즘/기타 2022. 7. 19. 23:39
[C++] 백준 1654번 랜선 자르기

1) 문제설명 2) 아이디어 입력받은 값들 중 가장 큰 값을 1부터 이분 탐색을 실시한다. 1과 가장 큰 값의 중간값으로 배열의 값을 나누어 그 몫의 합이 n보다 작다면 적 은값으로 다시 이분 탐색을 실시하고 크다면 큰 값으로 이분탐색을 실시한다. 이분탐색을 진행하며 중간값의 최댓값을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long arr[1000001]; long long k, n; // k : 잘라야하는 랜선의 갯수, n : 필요한 랜선의 갯수 long long result; void binary_search(long long start, lon..
알고리즘/기타 2022. 7. 18. 22:34
[C++] 백준 10816번 숫자 카드 2

1) 문제설명 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 2) 아이디어 이분 탐색을 이용하여 배열 안의 키 값을 찾는다. 단 겹치는 숫자카드의 개수를 세어야 하므로 이분 탐색을 실행하면서 찾고자 하는 키값들 중 배열의 맨 처음 인덱스와 마지막 인덱스의 차이를 출력한다면 그 키값이 배열 안에 몇 개 있는지 알 수 있으므로 이를 이용한다. up_binary_search : 배열 안의 키값의 맨 마지막 인덱스를..
알고리즘/기타 2022. 7. 16. 18:17
[C++] 백준 2559번 수열

1) 문제설명 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 2) 아이디어 입력받은 배열의 누적합을 sum배열에 저장한다. 누적합에서 k번째 이후만큼을 빼주면 k일의 연속적인 날짜의 수의 누적합이 나온다. 이후 k일의 연속적인 날짜의 수의 누적 합의 최댓값을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include334 using name..
알고리즘/기타 2022. 7. 8. 13:38
[C++] 백준 11659번 구간 합 구하기 4

1) 문제설명 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 2) 아이디어 for문을 2번 사용하여 구간의 합을 구 할 경우 O(N^2)의 시간이 걸리기 때문에 O(N+M)의 시간 안에 문제를 해결해야 한다. 구간의 합을 배열로 설정한 후 미리 구하여 b번째의 합에서 a-1번째의 합까지를 빼면 구간 a~b까지의 구간의 합을 구할 수 있다. 3) 코드 #include #include #include #include #in..
알고리즘/기타 2022. 7. 6. 12:30
[C++] 백준 1920번 수 찾기

1) 문제설명 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 2) 아이디어 입력받은 배열을 오름차순으로 배열하고 이진 탐색으로 찾는다. 이번에는 이진 탐색을 직접 구현하지 않고 STL을 사용해서 해결하였다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr..
알고리즘/기타 2022. 7. 5. 09:51
[C++] 백준 10815번 숫자 카드

1) 문제설명 2) 아이디어 상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬하고 이분 탐색을 통해 숫자카드를 가지고 있으면 1을 출력, 가지고 있지 않으면 0을 출력한다. 기본적인 이분 탐색 알고리즘을 알고 있다면 쉽게 풀 수 있다. printf, scanf 함수를 사용해서 시간 초과가 나지 않도록 주의한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; int arr[500001]; int brr[500001]; int search(int start, int end, int key) { if (start == end) { if (arr[start] == key) { //..
알고리즘/기타 2022. 7. 5. 08:37
Prev 1 2 3 4 Next