본문 바로가기

정렬5

[백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이 문제) 백준 - 우선수위 큐 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다. C+.. 2022. 3. 17.
[백준] 14400번 - 편의점 2 (C++) 문제 및 풀이 문제) 백준 - 정렬 - 편의점 2 https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 거리의 최소를 구하는 문제였습니다. 거리의 최소는 x 좌표와 y좌표의 중간값을 고르면 구할 수 있습니다. C++ 소스 코드) 2022. 2. 26.
[백준] 20495번 - 수열과 헌팅 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 수열과 헌팅 https://www.acmicpc.net/problem/20495 20495번: 수열과 헌팅 예제에서, 수열의 수들을 차례로 x1, x2, x3이라 하자. -10 ≤ x1 ≤ 30, 25 ≤ x2 ≤ 55, 55 ≤ x3 ≤ 85이다. 만약 (x1, x2, x3) = (28, 25, 70)이라면, x2가 첫번째, x1이 두번째, x3이 세 번째 수가 된다. 또, (x1, x2 www.acmicpc.net 최대, 최소를 배열과 벡터에 저장합니다. 배열에 있는 수는 탐색할 숫자이며 벡터에 있는 수는 정렬을 하여 탐색할 범위입니다. 최솟값을 최댓값이 정렬된 벡터의 lower_bound, 최댓값을 최솟값이 정렬된 벡터의 upper_bound를 통해 인덱스를 구합니다... 2022. 2. 23.
[백준] 18870번 - 좌표 압축 (C++) 문제 및 풀이 문제) 백준 - 정렬(Sorting) - 좌표 압축 -> https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net n이 최대 100만이기 때문에 O(nlogn)으로 짜야한다. 좌표의 값과 인덱스를 저장 후 값에 대하여 오름차순으로 정렬한다. 그 후 ans에 압축 적용된 값을 넣는다. C++ 소스 코드) 2021. 6. 29.
[백준] 1181번 - 단어 정렬 (C++/파이썬) 문제 및 풀이 문제) 백준 - 정렬(Sort) - 단어 정렬 -> www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 길이가 짧은 순으로 정렬해주되, 길이가 같을 경우 사전 순으로 정렬한다. 자신이 사용하는 언어의 정렬 Tool을 잘 활용한다면 어렵지 않은 문제. C++ 소스 코드) 파이썬 소스 코드) 2021. 4. 14.
반응형

티스토리툴바