전체 글130 [백준 알고리즘][자바] 11651번 : 좌표 정렬하기2 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이번 문제는 11650번 : 좌표 정렬하기에서는 x좌표를 첫 번째 기준 y좌표를 두 번째 기준으로 했다면, 반대로 y좌표가 첫 번째 기준 x좌표가 두번째 기준입니다. 2022.06.22 - [Algorithm/Baekjoon] - [백준 알고리즘][자바] 11650번 : 좌표 정렬하기 [백준 알고리즘][자바] 11650번 : 좌표 정렬하기 .. 2022. 6. 22. [백준 알고리즘][자바] 11650번 : 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이번 문제는 좌표를 사용하여 첫 번째는 x좌표 기준으로 오름차순으로 정렬하고, 같은 숫자가 존재할 때 y좌표 기준으로 오름차순을 하는 문제입니다. 여러 가지 정렬 알고리즘에다가 x좌표가 같은 숫자일 때 y좌표 기준으로 정렬하는 부분을 추가해주면 해결할 수 있습니다. 다만 제한시간이 1초이기 때문에 시간 복잡도가 중요합니다. 우선, 단순 삽입 정.. 2022. 6. 22. [백준 알고리즘][자바] 1427번 : 소트인사이드 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 개행되어서 숫자가 주어지는 것이 아닌, 한 번에 숫자가 주어지고 각 자릿수를 뽑아내서 정렬을 해야 하는 문제입니다. 다양한 정렬을 사용하여 문제를 해결할 수 있는데 이번 포스팅에서는 이때까지 많이 사용했던 카운팅 정렬과 Arrays.sort()를 사용해서 해결해보겠습니다. 2022.05.07 - [Algorithm/Theory] - [Java] Counting Sort(카운팅 정렬) [Java] Counting Sort(카운팅 정렬) Counting Sort는 일반적인 .. 2022. 6. 15. [백준 알고리즘][자바] 2108번 : 통계학(카운팅 정렬) https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 이번 문제를 해결할 때는 카운팅 정렬을 사용합니다. 2022.05.07 - [Algorithm/Theory] - [Java] Counting Sort(카운팅 정렬) [Java] Counting Sort(카운팅 정렬) Counting Sort는 일반적인 정렬 알고리즘과 달리 데이터를 서로 비교하지 않고, 데이터의 값을 카운팅 하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n)인데, 빠른 정렬 알고리즘으로 알려져.. 2022. 6. 14. [Java] 자바 람다식(Lambda Expression)이란? 자바 8부터 추가된 스트림(Stream)을 사용하기 위해서는 람다식(Lambda Expression)의 이해가 필수적입니다. 이번 포스팅에서는 람다식에 대해 알아보도록 하겠습니다. 람다식(Lambda Expression) 이란? 람다식(Lambda Expression)이란 메서드를 하나의 식으로 표현한 것입니다. 메서드를 식으로 표현한다면 메서드의 이름이 필요 없기 때문에 람다식은 익명 함수(Anonymous Function)의 한 종류로 볼 수 있습니다. 기존의 메서드들은 아래와 같이 사용하였습니다. public static void main(String[] args) { system.out.println(hello()); } public static String hello() { return "hel.. 2022. 6. 8. [백준 알고리즘][자바] 10989번 : 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 기본적인 수 정렬하기 시리즈 마지막 문제입니다. 이번 문제에서는 아래의 3가지 방법을 사용하여 풀어보도록 하겠습니다. 직접 구현한 Counting Sort를 사용 Arrays.sort()를 사용 Collections.sort()를 사용 2022.05.07 - [Algorithm/Theory] - [Java] Counting Sort(카운팅 정렬) [Java] Counting Sort(카운팅 정렬) Counting S.. 2022. 5. 7. [Java] Counting Sort(카운팅 정렬) Counting Sort는 일반적인 정렬 알고리즘과 달리 데이터를 서로 비교하지 않고, 데이터의 값을 카운팅 하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n)인데, 빠른 정렬 알고리즘으로 알려져 있는 Quick Sort, Merge Sort, Heap Sort 등의 시간 복잡도가 O(nlogn)라는 것을 생각하면 Counting Sort의 속도가 엄청나다는 것을 알 수 있습니다. 그럼 왜 Counting Sort는 사용하지 않는 것일까요? Counting Sort는 정렬 할 배열의 최댓값의 +1만큼 새로운 카운팅 배열을 생성해줘야 하는데, 수의 범위가 크다면 메모리를 많이 낭비하기 때문에 자주 사용하지 않습니다. 과정 1. 먼저 정렬할 배열의 데이터의 최댓값의 +1 크기의 카운팅 배열을 생성합니다. .. 2022. 5. 7. [백준 알고리즘][자바] 2751번 : 수 정렬하기 2 https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 이번 문제는 자바에 내장되어 있는 정렬 함수를 사용하여 푸는 문제이다. 자바에 내장되어 있는 정렬 함수는 Arrays.sort() 와 Collections.sort()가 있다.(자바 8기준) 2022.04.30 - [Programming/Java] - [Java] 자바 내장 정렬 함수 - Arrays.sort() [Java] 자바 내장 정렬 함수 - Arrays.sort() 데이터들을 .. 2022. 5. 3. [Java] 자바 내장 정렬 함수 - Arrays.sort() 데이터들을 정렬시킬 때, 어떤 정렬 알고리즘을 사용해야 하는지 판단하는 중요한 요소중 하나는 시간 복잡도입니다. 자바 내부에서 사용하는 정렬은 시간 복잡도가 얼마인지 알 필요성이 있다고 생각합니다. 이번 포스팅에서는 자바의 내장 정렬 함수 중 하나인 Arrays.sort()를 알아보도록 하겠습니다.(JAVA 8 기준) java.util.Arrays.sort() Arrays.sort()는 내부적으로 DualPivotQuicksort.sort()를 호출한다. 퀵 정렬의 시간 복잡도는 일반적으로 최선의 경우에는 O(nlogn)을 가지고, 최악의 경우에는 O(n^2)를 가진다. 주석을 해석해보면 DualPivotQuicksort.sort()는 최악의 시간 복잡도를 갖게 하는 많은 데이터 셋들에 대해서도 O(nl.. 2022. 4. 30. 이전 1 2 3 4 5 6 ··· 15 다음 반응형
