정렬 알고리즘 (Sorting Algorithm) 정렬 알고리즘은 크게 비교 방식(Comparisons)과 미비교 방식(Non-Comparisons)으로 나눌 수 있다. 비교 기반 정렬 알고리즘에는 거품 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬이 있다. 미비교 기반 정렬 알고리즘에는 기수 정렬과 계수 정렬이 있다. 거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 수행 과정 1회전에 첫번째 원소부터 마지막 원소까지 인접한 원소끼리 대소를 비교하여 조건에 맞춰 서로 교환한다. 1회전이 끝나면 가장 큰 원소가 맨 뒤에 위치해 있으므로 2회전에는 맨 끝에 있는 원소는 정렬에서 제외한다. 이러한 방식으로 원소..
문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 설명 N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내야 한다. 매번 하나씩 숫자를 비교하면서 탐색할 수 있지만 시간복잡도를 줄이기 위해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이분 탐색을 수행한다. 이분 탐색을 하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있기 때문에 먼저 입력받은 수를 오름차..
문제 https://www.acmicpc.net/problem/1713 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 설명 1. 학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다. 2. 어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다. 3. 비어있는 사진틀이 없는 경우에는 현재까지 추천 받은 횟수가 가장 적은 학생의 사진을 삭제하고, 그 자리에 새롭게 추천받은 학생의 사진을 게시한다. 이때, 현재까지 추천 받은 횟수가 가장 적은 학생이 두 명 이상일 경..
문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 설명 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 알파벳은 총 26개이므로 words 배열의 크기를 26으로 만든다. 주어진 단어에서 해당하는 알파벳 자리에 각 자릿수만큼 10의 거듭제곱을 더해준다. int[] words = new int[26]..
기본 데이터 타입의 정렬 기본 데이터 타입 : char, int, double 등 Arrays 클래스에서 primitive 데이터 타입을 위한 정렬 메소드를 제공한다. import java.util.Arrays; int[] nums = { 1, 3, 5, 2, 4 }; System.out.println(Arrays.toString(nums));// 출력 : [1, 3, 5, 2, 4] // 오름차순으로 정렬 Arrays.sort(nums); System.out.println(Arrays.toString(nums));// 출력 : [1, 2, 3, 4, 5] 객체의 정렬 객체 타입 : String, Character, Integer, Double 등 기본형을 객체로 다루기 위해 사용하는 클래스를 wrapp..
