알고리즘/백준 문제 및 정답
문제 번호 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입니다. 이 두 가지를 봤을 때 다른 점은 어렵..
문제 번호 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 데이터에 비해 확연히 부족하다. 그래서 가장 빠른 카운팅 정렬을 사용해 문제를 풀어야 한다. 문제 풀이 해당 문제에서 가장 중요한 것은 속도입니다. 속도가 걸려서 문제를 풀지 못하는 경우가 많습니다. 제가 아는 빠른 정렬은 합병 정렬과 힙 정렬, 카운팅 정렬입니다. 카운팅 정렬로 문제를 ..
문제 번호 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...
문제 번호 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(..
문제 번호 2787번 : 대표값2 - JAVA [자바]
문제 번호 2787번 : 대표값2 - JAVA [자바]
2023.02.22https://www.acmicpc.net/problem/2587 2587번: 대표값2 어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30의 평균은 (10 + 40 + 30 + 60 + www.acmicpc.net 문제 설명 간단하게 수를 정렬하여 중간값을 찾고 평군을 내는 문제입니다. 문제 풀이 해당 문제는 삽입정렬을 사용해서 풀도록 하겠습니다. 삽입 정렬에 대한 내용은 삽입 정렬 참고해주세요. 정렬에 대한 이해가 있다면 어렵지 않은 문제일 것입니다. import java.util.Scanner; public class Main { public static void m..
문제 번호 2750번 : 수 정렬하기 - JAVA [자바]
문제 번호 2750번 : 수 정렬하기 - JAVA [자바]
2023.02.15https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 설명 간단하게 수를 정렬하는 문제입니다 문제 풀이 해당 문제는 선택정렬을 사용해서 풀도록 하겠습니다. 선택정렬에 대한 내용은 해당 글에서 설명되어 있습니다. 정답코드 import java.util.Random; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Sc..
문제 번호 24060번 : 병합 정렬 1 - JAVA [자바]
문제 번호 24060번 : 병합 정렬 1 - JAVA [자바]
2023.01.21https://www.acmicpc.net/problem/24060 24060번: 알고리즘 수업 - 병합 정렬 1 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net 문제 설명 재귀를 사용한 병합 정렬에서 정렬되는 순서에 따른 값을 출력하는 문제입니다. 문제 풀이 문제에서는 병합정렬 로직이 풀이로 나와있지만 해당 언어를 알지 못하거나 병합정렬 알고리즘에 대한 이해가 없으면 풀기가 쉽지 않습니다. 병합 정렬에 대한 내용은 다음 게시물에 올려놓았습니다. 병합정렬이 관하여 자바로 구현한 합병 정렬(병합 정렬) 알고리즘..