목록분류 전체보기 (96)

키베이루's diary

[C++] 백준 1927번 최소힙

1) 문제설명 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2) 해결방법 O(n)의 시간을 맞춰야 하므로 우선순위 큐를 이용하여 구현한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; /* */ int main() { int n; priority_queue pq; cin >> n; for (..
알고리즘/기타 2022. 5. 23. 23:34
[C++] Deque

Deque는 Queue와 Stack이 자료를 한 방향에서만 처리할 수 있는 것과는 다르게 앞과 뒤에서 모두 데이터를 삽입, 제거할 수 있다. Deque의 삽입과 제거는 Queue, Stack 과 같이 모두 O(1)의 시간이 소요된다. Deque와 비슷한 자료구조로는 List가 있는데 List의 경우 앞 or 뒤에서 데이터를 처리할 경우 O(n)의 시간이 소요되므로 경우에 따라서는 Deque의 성능이 압도적으로 좋아질 수 있다. C++에서의 Deque 사용법 1) deque를 헤더파일에 추가한다. #include 2) deque 선언 deque 이름; 3) deque의 여러 기능 deque dq로 선언 이후 dq.push_front(원소) : dq의 첫 번째 원소 앞에 삽입 dq.push_back(원소) ..
알고리즘/기타 2022. 5. 23. 16:44
[C++] 백준 17298번 오큰수

1) 문제설명 백준 Online Judge 17298번 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 2) 해결방법 배열의 오른쪽 부터 스택에 넣고 스택의 값과 배열의 값을 비교하여 새로운 배열에 큰 수를 집어 넣는다. 3) 코드 #include #include #include #include #include #include #include using namespace std; long long arr[1000001]; long long brr[..
알고리즘/기타 2022. 5. 23. 16:13
[C++] 백준 15903번 카드 합체 놀이

1) 문제설명 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 2) 해결방법 처음 입력값 두 개를 더해서 저장한 후 그 값을 다시 입력값에 저장한다. 이후 반복문을 돌면서 오름차순으로 계속 정렬을 한 후 다시 과정을 반복한다. 3) 코드 #include #include #include #include #include #include using namespace std; long long arr[500002]..
알고리즘/Greedy 2022. 5. 22. 06:47
[C++] 백준 2012번 등수 매기기

1) 문제설명 2) 해결방법 입력값을 오름차순으로 정렬한 뒤 그 값과 그 값의 인덱스 값을 빼주어 더해주었다. 3) 코드 #include #include #include #include #include #include using namespace std; long long arr[500002]; /* 등수 매기기 해결방안 입력값을 오름차순으로 정렬한 뒤 그 값과 그 값의 인덱스 값을 빼주어 더해주었다. */ int main() { long long n; cin >> n; for (int i = 1; i > arr[i]; } sort(arr+1, arr + n+1); long long sum = 0; for (long long i = 1; i i) { sum = sum + arr[i] - i; } else..
알고리즘/Greedy 2022. 5. 22. 03:33
[C++] 백준 11497번 통나무 건너뛰기

1) 문제설명 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 2) 해결방법 입력값 중 가장 큰 값을 중앙에 두고 양옆으로 작아지게 수를 정렬한 후 앞뒤 값의 차이들 중 최댓값을 출력하면 된다. 13 10 12 11 10 11 12 -> 10 11 12 13 12 11 10으로 정렬 한 뒤 | 10 vs 11 | 11 vs 12 |... | 11 vs 10 | 앞뒤 차이들 중 최댓값을 출력한다. 입력값을 오름차순으로 정렬한 뒤 짝수 인덱스를 ..
알고리즘/Greedy 2022. 5. 20. 23:44
[C++] 백준 1912번 연속합

1) 문제설명 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2) 해결방법 입력값 : 2 -> 최대 2 2, 1 -> 최대 2+1 =3 2, 1, -4 -> 최대 2+1 =3 2, 1, -4, 3 -> 최대 2+1 =3 or 3 2, 1, -4, 3, 4 -> 최대 3+4 =7 이와 같이 생각했을 때 (지금까지 입력받았던 합중 최댓값) vs (새로 입력받은 숫자) 중 큰 것으로 dp를 설계하면 된다. 3) 코드 #include #include #incl..
알고리즘/DP 2022. 5. 18. 16:23
[C++] 백준 1463번 1로 만들기

1) 문제설명 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2) 해결방법 문제를 이해하기 위해서 2부터 하나씩 생각해보았다. 2 -> 1 (2로 나누어 떨어진다) 횟수 : 1 3 -> 1 (3으로 나누어 떨어진다) 횟수 : 1 4 -> 2 -> 1 (2로 두 번 나누어 떨어진다) 횟수 : 2 5 -> 4 -> 2 -> 1 (1을 빼고 2로 두번 나누어 떨어진다) 횟수 : 3 6 -> 3 -> 1 or 6 -> 2 -> 1 (2로 나누고 3으로 나눈다 or 3으로 나누고 2로 나눈다) 횟수 : 2 이와 같이 생각하니 (3으로 나눈 것) vs (2로 나눈 것..
알고리즘/DP 2022. 5. 18. 01:57
Prev 1 ··· 9 10 11 12 Next