분류 전체보기
문제 번호 10814번 : 나이순 정렬 - JAVA [자바]
문제 번호 10814번 : 나이순 정렬 - JAVA [자바]
2023.03.09https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제 설명 회원의 나이와 이름을 받고 나이순으로 정렬하되 나이가 같으면 가입한 순으로 정렬을 하는 문제입니다. 보고 오기를 추천하는 게시물 https://kkungchan.tistory.com/300 Java - comparable과 comparator에 대해 java에서 정렬을 할 때 빼고 이야기할 수 없는 객체가 Comparable과 Comparator입니다. 이 두 가지를 봤을 때 다른 점은 어렵..
Java - comparable과 comparator에 대해
Java - comparable과 comparator에 대해
2023.03.07java에서 정렬을 할 때 빼고 이야기할 수 없는 객체가 Comparable과 Comparator입니다. 이 두 가지를 봤을 때 다른 점은 어렵지 않으나 java안에서 사용하고 구현하는 것이 쉽지 않고 당황스럽습니다. 저자는 백준 정렬 문제를 풀면서 한 번은 게시해야겠다고 느껴 Comparable과 Comparator에 대해 내가 공부하고 이해한 것을 최대한 쉽게 정리해서 올리려 합니다.. 보통 정렬 하면 어떤 것이 떠오르나요? 숫자로 된 배열을 정렬하는 방식이 떠오릅니다. 그리고 아래 코드는 제가 생각할 때 숫자를 정렬할 때 가장 많이 쓰이는 코드입니다. import java.util.Arrays; public class Main{ public static void main(String[] args) ..
문제 번호 1181번 : 단어 정렬 - JAVA [자바]
문제 번호 1181번 : 단어 정렬 - JAVA [자바]
2023.03.07https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 설명 문자열을 받아 해당 문자열을 기준으로 정렬하는 문제입니다. 단, 같은 문자열의 길이는 문자열의 순서로 출력해야 하고 같은 문자열은 제거해야 합니다. 문제 풀이 해당 문제는 Arrays.sort을 사용해서 풀도록 하겠습니다. 해당 문제는 숫자가 아닙니다. 숫자가 아닌 문제를 해결할 때는 Arrays.sort의 Comparator을 재정의해 사용하면 문자 정렬을 효율적으로 사용할..
문제 번호 11651번 : 좌표 정렬하기 2 - JAVA [자바]
문제 번호 11651번 : 좌표 정렬하기 2 - JAVA [자바]
2023.03.07https://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 문제 설명 좌표를 x축을 기준으로 x축이 같으면 y축으로 비교하여 정렬하는 문제입니다. 문제 풀이 해당 문제는 바로 전 문제의 x,y만 변경하면 바로 풀리는 문제입니다. https://kkungchan.tistory.com/297 문제 번호 11650번 : 좌표 정렬하기 - JAVA [자바] https://www.acmicpc.net/pro..
문제 번호 11650번 : 좌표 정렬하기 - JAVA [자바]
문제 번호 11650번 : 좌표 정렬하기 - JAVA [자바]
2023.03.07https://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축을 기준으로 x축이 같으면 y축으로 비교하여 정렬하는 문제입니다. 보고 오기를 추천하는 게시물 https://kkungchan.tistory.com/300 Java - comparable과 comparator에 대해 java에서 정렬을 할 때 빼고 이야기할 수 없는 객체가 Comparable과 Comparator입니다. 이..
문제 번호 1427번 : 소트인사이드 - JAVA [자바]
문제 번호 1427번 : 소트인사이드 - JAVA [자바]
2023.03.06https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 숫자 하나를 입력받고 자리수의 맞게 정렬하는 문제입니다. 보고 오기를 추천하는 게시물 https://kkungchan.tistory.com/293 자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘 카운팅 정렬은 많은 알고리즘 중에 O(n)에 시간복잡도를 가지는 엄청난 성능을 가진 정렬 방식이다. 보통 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort)이 빠르다는 정렬이지만 데이터끼 kkungchan.tist..
문제 번호 2108번 : 통계학 - JAVA [자바]
문제 번호 2108번 : 통계학 - JAVA [자바]
2023.03.06https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 설명 입력된 값의 산술평균, 중앙값, 최빈값, 범위를 출력하는 문제입니다. 보고 오기를 추천하는 게시물 https://kkungchan.tistory.com/293 자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘 카운팅 정렬은 많은 알고리즘 중에 O(n)에 시간복잡도를 가지는 엄청난 성능을 가진 정렬 방식이다. 보통 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합..
문제 번호 10989번 : 수 정렬하기 3 - JAVA [자바]
문제 번호 10989번 : 수 정렬하기 3 - JAVA [자바]
2023.03.02https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 자바 제안시간 3초 메모리 제안 512MB를 충족하는 정렬을 해야 하는 문제이다. 제안시간이 지금까지 문제와는 TEST 데이터에 비해 확연히 부족하다. 그래서 가장 빠른 카운팅 정렬을 사용해 문제를 풀어야 한다. 문제 풀이 해당 문제에서 가장 중요한 것은 속도입니다. 속도가 걸려서 문제를 풀지 못하는 경우가 많습니다. 제가 아는 빠른 정렬은 합병 정렬과 힙 정렬, 카운팅 정렬입니다. 카운팅 정렬로 문제를 ..
자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘
자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘
2023.03.02카운팅 정렬은 많은 알고리즘 중에 O(n)에 시간복잡도를 가지는 엄청난 성능을 가진 정렬 방식입니다. 보통 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort)이 빠르다는 정렬이지만 데이터끼리 직접 비교를 하기 때문에 O(NlogN)의 시간 복잡도를 가지는것이 한계입니다. 그렇다면 카운팅 정렬은 어떻게 속도의 한계를 극복할 수 있었을까요? 그리고 이렇게 빠른 속도임에도 불구하고 O(NlogN)의 시간 복잡도를 가지는 알고리즘을 사용하는 것일까요? 카운팅 정렬은 말 그대로 해당 숫자가 얼마나 출연했는지 카운팅 하면서 정렬하는 방식입니다. 1. 정렬 해야하는 원소의 범위만큼의 배열을 만든다. 2. 만든 배열 인덱스에 해당하는 수가 정렬해야 하는 배열에 있는 만큼 값을..
문제 번호 2751번 : 수 정렬하기 2 - JAVA [자바]
문제 번호 2751번 : 수 정렬하기 2 - JAVA [자바]
2023.02.27https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 수를 정렬 한 후 출력하는 문제입니다. 문제 풀이 해당 문제에서 가장 중요한 것은 속도입니다. 속도가 걸려서 문제를 풀지 못하는 경우가 많습니다. 제가 아는 빠른 정렬은 합병 정렬과 힙 정렬, 카운팅 정렬입니다. 지금 포스팅 되어 있는 정렬은 합병 정렬임으로 합병 정렬로 해당 문제를 해결해 보겠습니다. 합병 정렬에 관해서는 이 글에서 참고하시면 됩니다. import java...
자바로 구현한 셀 정렬(Shell Sort) 알고리즘
자바로 구현한 셀 정렬(Shell Sort) 알고리즘
2023.02.23셀 정렬은 삽입 정렬을 기반으로 단점은 최소화하고 장점은 최대화 한 정렬 방식입니다. 만약에 삽입 정렬에 대해 모르신다면 삽입 정렬글을 읽고 오시는 것을 추천드립니다. https://kkungchan.tistory.com/287 자바로 구현한 삽입 정렬 알고리즘 삽입 정렬은 Target 인덱스를 정해서 올바른 인덱스에 삽입해 주는 정렬 방식입니다. 삽입 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 kkungchan.tistory.com 삽입 정렬의 단점은 역순으로 정렬되어 있다면 교환이 너무 많이 생겨 시간이 최악의 경우 O(N2)의 시간 복잡도를 가진다는 것입니다. 반대로 삽입 정렬의 장점은 정렬이 어느 정도 되어 있다면 O(N)으로..
문제 번호 25305번 : 커트라인 - JAVA [자바]
문제 번호 25305번 : 커트라인 - JAVA [자바]
2023.02.23https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net 문제 설명 간단하게 수를 정렬하여 두번째 입력값 번째의 수를 찾아내는 문제입니다. 문제 풀이 해당 문제는 버블 정렬을 사용해서 풀도록 하겠습니다. 삽입 정렬에 대한 내용은 버블 정렬을 참고해주세요. 정렬에 대한 이해가 있다면 어렵지 않은 문제일 것입니다. import java.util.Scanner; public class Number_25305 { public static void main(String[] args) { Scanner sc = new Scanner(..