본문 바로가기

정렬23

[백준] 2217번 : 로프 – JAVA [자바] https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 문제 문제 풀이 백준 2217번 로프는 실버 4 난이도의 수학 및 그리디 문제이다. 이 문제에서는 들 수 있는 물체의 중량이 다를 수 있는 로프 N개가 주어진다. 그리고 로프를 병렬로 연결하면 로프에 걸리는 중량을 나눌 수 있다. 이 문제에서 k개의 로프를 사용하여 중량이 w인 물체를 들어 올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다고 주어졌다. 이때 로프 N.. 2023. 4. 25.
[백준] 1931번 : 회의실 배정 – JAVA [자바] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 문제 풀이 백준 1931번 회의실 배정은 실버 1 난이도의 그리디 및 정렬 문제이다. 항상 그리디 문제들을 공부하고 풀어야지 풀어야지 생각만 했다가 학교에서 CSE2310 Algorithm Design이라는 과목에서 그리디 알고리즘에 대해 배우고 시험도 끝난 다음에 드디어 문제들을 조금 풀게 되었다. 이 문제는 그리디에서 가장 기본적인 문제인 거 같다. 학교에서도 그리디를 처음 배울 때 접했던 문제가 이런 문제였다. 학교에서 배울 때 이런 문제를 'Interval Scheduling'이라고 한다고 배웠다. .. 2023. 4. 25.
[백준] 2693번 : N번째 큰 수 – JAVA [자바] https://www.acmicpc.net/problem/2693 2693번: N번째 큰 수 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000 www.acmicpc.net 문제 문제 풀이 백준 2693번 N번째 큰 수는 브론즈 1 난이도의 정렬 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 우선 입력으로 주어진다. 그리고 T 줄에서 10개의 수가 주어진다. 이때 각 테스트 케이스마다 3번째로 큰 값을 출력하면 된다. 이 문제에서는 우선 배열에 입력으로 주어지는 10개의 수를 저장하고 배열을 오름차순으로 정렬을 해야 한다. 이 이유는 3.. 2022. 8. 10.
[알고리즘] 계수 정렬 (Counting Sort) 목차 계수 정렬이란? 계수 정렬은 데이터 값을 직접 비교하지 않고, 단순하게 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬하는 알고리즘이다. 기존의 정렬 알고리즘들은 위치를 바꾸며 정렬을 했는데, 계수 정렬에서는 크기를 기준으로 개수만 세면 되기 때문에 위치를 변경할 필요가 없다. 계수 정렬의 큰 특징은 값 비교가 일어나지 않기 때문에 속도가 빠르다는 것이다. 하지만, 개수를 저장하는 배열을 사용해야 하기 때문에 추가 공간이 필요하다. 그래서, 정렬해야 할 수의 범위가 작을 때에만 유리하다. 이 이유는 예를 보면서 설명하겠다. EX) 0, 100, 2, 10, 10000 오름차순으로 정렬하기 예를 들어서 정렬해야 할 수가 0, 100, 2, 10, 10000이면 고작 5개의 수를 정렬하는데 0부.. 2022. 7. 29.
반응형

티스토리툴바