선택 정렬 가장 작은 요소부터 선택해 맞는 위치로 옮기면서 순서대로 정렬하는 알고리즘 1. 주어진 배열의 요소들 중에서 최소값을 찾는다. 2. 해당 값을 배열의 맨 앞자리 요소와 교환한다. 3. 맨 앞자리를 뺀 나머지 요소들도 위와 같은 방법으로 교환한다. 즉, 정렬하지 않은 부분에서 최소값을 찾고, 그 값을 정렬하지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다. 최소값을 찾으려고 비교한 횟수가 n-1, n-2, n-3, ... , 2, 1번이므로 시간 복잡도는 O(N^2)이다. 그리고 서로 떨어져 있는 요소를 교환하므로 안정적이지 않다. 2021. 11. 16. 버블 정렬 일반적으로 가장 기본적으로 생각할 수 있는 방법 인접한 두 요소의 대소 관계를 비교하여 교환을 반복! 앞(혹은 뒤)에서부터 차례대로 비교/교환이 이루어지기 때문에 안정정렬 맨 앞에서부터 현재 요소와 바로 다음 요소끼리 비교 현재 요소가 다음 요소보다 크다면 교환 다음 인덱스로 이동해 그 다음 요소와 비교/교환을 반복 배열의 요소 갯수가 n개라 한다면, 이웃한 요소끼리 비교/교환 작업을 처음부터 끝까지 한 번 진행하면, 가장 큰 요소가 맨 마지막 인덱스로 이동한다. 이 과정을 패스라고 한다.(n-1회 비교) 그리고선 남은 n-1개 요소로 비교/교환을 앞에서부터 끝까지 한 번 진행하면, 다음으로 큰 요소가 맨 마지막 직전 인덱스로 이동한다. (n-2회 비교) 이런 식으로 계속 진행하면, 이러한 작업이 총 n.. 2021. 11. 16. (Java) 백준 1920 : 수 찾기 문제 : https://www.acmicpc.net/problem/1920 N개의 정수를 요소로 하는 배열을 M번 탐색하는 문제 순차탐색 : 시간복잡도 O(N * M) = 100억. 시간제한 1초당 1억 연산 횟수 정도로 보기 때문에 시간 제한에 걸린다. 이진탐색: 시간복잡도 O(M * logN) import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] intArr1 = new int[n]; for(int i=0; i 2021. 11. 12. 자바 배열 정렬 (Comparable / Comparator 차이) 둘 다 "객체를 특정 기준으로 비교할 수 있도록 한다." Comparable - Comparable 인터페이스를 쓰려면 compareTo(T o) 구현 - 자기 자신과 매개변수 (T클래스 자료형 o) 객체를 비교 - lang패키지에 있어 import 필요 x Comparator - Comparator 인터페이스를 쓰려면 compare(T o1, T o2) 구현 - 두 매개변수 객체를 비교 - util패키지에 있어 import 필요 - Comparator 인터페이스를 구현하는 클래스는 비교하는 두 객체와 아무 관련이 없고, compare()만 overriding해서 비교할 때만 사용하려고 하는 것이다. 그래서 Comparator을 구현하는 익명 객체를 생성하여 주로 사용한다. - Comparator을 구현.. 2021. 11. 12. 이전 1 ··· 5 6 7 8 다음