본문 바로가기

프로그래밍/백준(C++)7

[실3] 2108. 통계학 [출처] : https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 구현을 빡세게 해야되는 문제였다. 좀 까다로웠던 부분은 최빈값 부분이였는데, 우선 로직은 이렇다. 0을 입력받으면 A[0]++ 400을 입력받으면 A[400]++ 이런식으로 그 배열의 인덱스를 이용하여 그 값이 몇번 입력되는지 카운트를 하는 생각을 했다. 그런데 문제에서는 입력값의 범위가 -4000 ~ 4000인데, 배열의 인덱스는 0부터시작하는데 어떻게 해야하지..? 싶었다. 해결방법은 생각보다 .. 2022. 9. 10.
[실2] 2805. 나무 자르기 [출처] https://www.acmicpc.net/problem/2805 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이분탐색을 이용한 문제였다. 나무를 자를 때 최대 높이부터 차근차근 잘라보는 완전탐색을 첨에 생각했는데, 시간초과가 났다. 그래서 시작을 0 끝을 나무최대크기 로 두고 중간부터 잘라보고 만족하면 시작을 mid + 1로 올리고 만족하지않으면 끝을 mid - 1로 낮추면서 이분탐색으로 값을 찾았다. #include #include #include #define endl '\n' using namespace std.. 2022. 9. 9.
[실2] 1874. 스택 수열 [출처] https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net #include #include #include #define endl '\n' using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); vector v; stack s; int count = 1; int n; cin >> n; for (.. 2022. 9. 6.
[실5] 10814. 나이순정렬 [출처] https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 이 문제는 얼핏 보면 단순히 벡터로 입력받아 sort()함수로 정렬해서 출력하면 될것처럼 보이지만 sort()함수로 하면 순서를 보장받지 못하기 때문에 stable_sort()함수를 사용해야 한다. 무슨 말이냐면 sort()함수는 4 2 1 3 4 를 1 2 3 4 4 로 정렬을 시켰을때 4끼리의 순서가 보장받지 못한다. 그러나 stable_sort()함수를 사용하면 4 2 1 3 4 에서의 .. 2022. 8. 31.

티스토리툴바