정렬

[백준] 11931. 수 정렬하기 4 (Java)

문제 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 알고리즘 정렬 풀이 N개의 원소를 리스트에 저장하고, Collections.sort()를 이용하여 내림차순으로 정렬한다. Collections.sort()는 O(nlogn)의 시간복잡도를 갖는 tim sort를 사용한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; i..

[백준] 1202. 보석 도둑 (Java)

문제 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 알고리즘 그리디 알고리즘, 정렬, 우선순위 큐 풀이 N과 K가 30만으로 굉장히 크기 때문에 O(n2) 의 미만의 시간 복잡도로 해결해야한다. 이를 위해서 정렬과 우선순위 큐를 사용한다. 준비물 1. 남아있는 보석을 저장할 우선순위 큐 remains (무게 기준 오름차순 정렬) 2. 담을 수 있는 보석을 저장할 우선순위 큐 avails (비용 기준 내림차순 정렬) 3. 가방을 저장할 리스트 bag..

[백준] 2170. 선 긋기 (Java)

문제 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 알고리즘 정렬, 스위핑 풀이 좌표를 x를 기준으로 정렬하면 현재 좌표가 그어진 선보다 x 값이 크거나 같은 것이 보장되기 때문에 그어진 선의 x 값을 신경쓰지 않고 계산을 할 수 있다. 따라서 다음 세 가지를 고려하며 선분의 길이를 늘려주면 된다. 1. 포함되는 경우 2. 일부 겹치는 경우 3. 아예 겹치지 않는 경우 코드 import java.io.BufferedReader; import java.io.IOException; ..

[백준] 8980. 택배 (Java)

문제 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 알고리즘 정렬, 그리디 알고리즘 풀이 택배를 받는 마을 번호을 기준으로 오름차순 정렬하면 항상 최적의 해를 보장한다. 현재 배송 가능한 택배 중 가장 가까운 마을에 배송할 수 있는 택배부터 담는게 가장 효율적이기 때문이다. 현재 담은 택배들의 정보를 바탕으로 각 마을을 지날 때 어느정도의 택배를 가지고있을 지 계산하여 다음 택배를 얼마나 담을지 계산한다. 다음은 예제 1을 [받는 마을 번호 기준 오름차순 정렬]한 것이다. 보내는 마을은 ..

[백준] 17140. 이차원 배열과 연산 (Java)

🔒 문제 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 🔑 알고리즘 구현, 정렬, 해시맵(HashMap) 💡 풀이 각 행과 열의 원소들을 배열에 저장할 수도 있고, 리스트에 저장할 수도 있을 것이다. 배열에 저장하면 임의 접근은 쉬우나 문제 특성 상 각 행과 열의 크기가 달라지기 때문에 크기를 지정하는데 어려움이 있고, 리스트에 저장하면 행과 열의 크기가 변화해도 지장이 없으나 임의 접근이 불가능하므로 행, 열 두 가지 정렬을 모두 수행할 수 없다. (1 ≤ r, c, k ≤ 100) 행 또는 열..

[백준] 21276. 계보 복원가 호석 (Java)

🔒 문제 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 🔑 알고리즘 위상 정렬, 해시맵, 정렬 💡 풀이 조상과 자손이라는 정해진 순서가 있고 사이클이 없고, 방향 그래프이므로 위상 정렬을 사용하였다. 이름을 리스트에 저장하고 정렬한다. 정렬한 순서대로 인덱스를 부여하고 이름을 Key, 인덱스를 Value로 하여 HashMap에 삽입한다. 조상과 자손의 정보가 주어지면 그래프에 연결하고 자손의 진입 차수를 1 늘린다. 진입 차수가 0이면 조상이 없음을 의미하므로 시조 리스트에 넣고 위상 정렬 큐에 ..

[백준] 11004. K번째 수 (Java)

🔒 문제 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 🔑 알고리즘 정렬 💡 풀이 원소의 개수 N이 최대 5백만이므로 O(N^2)이 아닌 O(NlogN)의 시간 복잡도를 가지는 정렬 방식을 사용해야한다. Arrays.sort()의 경우 dual pivot quick sort를 사용하여 최악의 경우 O(N^2)의 시간 복잡도를 갖지만 Collections.sort()의 경우 tim sort를 사용하여 최악의 경우에도 O(NlogN)의 시간 복잡도를 갖는다. K가 1부터 시작하므로 K-1번째 원소를 출력한다. ✏️ 코드 import java.io.BufferedRe..