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

키베이루's diary

[C++] 백준 16953번 A -> B

1) 문제설명 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A > a ..
알고리즘/기타 2022. 6. 21. 23:35
[C++] 백준 1655번 가운데를 말해요

1) 문제설명 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 2) 아이디어 우선순위 큐의 최대 힙과 최소 힙을 둘 다 사용하여 가운데 값을 구해야 한다. 1. 홀수번째 수 일 경우 최대 힙에 값을 넣고 2. 짝수번째 수 일 경우 최소 힙에 값을 넣는다. 3. 최대 힙의 최댓값이 최소 힙의 최솟값보다 작을 경우 두 원소를 바꿔준다. 3) 코드 실패한 코드 : 시간 초과 #include #include #include #inclu..
알고리즘/기타 2022. 6. 20. 19:48
[C++] 백준 11286번 절댓값 힙

1) 문제설명 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2) 아이디어 우선순위 큐를 선언하고 비교 연산자를 호출하여 절댓값이 작은것이 우선순위가 되도록 swap을 하였다. 만약 절대값이 같은 경우, 둘 중 값이 작은 것이 우선순위가 되도록 swap 하였다. 3) 코드 #include #include #include #include #include #include #include #include using namesp..
알고리즘/기타 2022. 6. 9. 09:05
[C++] Vector

Vector는 자동으로 메모리가 할당되는 배열로서 데이터의 끝에서 삽입과 삭제가 이루어진다. 배열처럼 연속되는 저장 위치를 사용하므로 데이터의 추가 및 삭제가 간단하게 처리가 된다. 또한 배열과는 다르게 크기는 동적으로 변경이 되므로 메모리의 사용을 줄일 수 있다. 하지만 중간의 데이터를 삭제할 경우 효율적이지 못하므로 삭제가 자주 이루어질경우 리스트를 사용하는 것이 좋다. Vector의 헤더 #include // 벡터의 헤더파일 Vector의 선언 vector v1 // vector 변수명 vector v1 // 2차원 벡터 생성 Vector의 멤버함수 1) 접근 v.begin() : 벡터의 첫번째 데이터 위치 반환 v.end() : 벡터의 마지막 데이터 위치 반환 v.front() : 벡터의 첫번째 ..
알고리즘/기타 2022. 6. 3. 22:16
[C++] 백준 18870번 좌표압축

1) 문제설명 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2) 해결방법 2개의 벡터에 인덱스와 값을 저장해서 값을 변환 한 뒤 인덱스에 맞게 다시 정렬하는 방법을 사용했다. pair를 사용하여 두 개의 벡터 (v1, v2)를 선언, v1의 값을 오름차순으로 정렬한다. 오름차순으로 정렬한 v1에서 첫 번째 값과 두 번째 값이 같다면 같은 순위이고 두번째 값이 더 크다면 순위가 +1 되기 때문..
알고리즘/기타 2022. 5. 26. 16:42
[C++] 백준 10610번 30

1) 문제설명 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 2) 해결방법 입력을 하나씩 char형으로 받은 후에 int 형으로 변환한다. 그 후 입력받은 값의 합을 저장한 후에 내림차순으로 정렬한다. 입력받은 값의 합이 3의 배수이면 내림차순으로 출력하고 3의 배수가 아니면 -1을 출력한다. 3) 코드 #include #include #include #include #include #include #include #include using n..
알고리즘/기타 2022. 5. 26. 03:36
[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
Prev 1 2 3 4 Next