백준/정렬
-
선택 정렬백준/정렬 2022. 7. 2. 22:27
1. 선택 정렬 선택 정렬은 다음과 같이 진행된다. 1. 주어진 숫자에서 최솟값을 찾는다. 2. 최솟값을 맨 앞자리 값과 바꾼다. 3. 맨 앞 자리를 제외한 나머지 값 중 최솟값을 찾아서 반복한다. 시간복잡도 : O(N*N) 2. 그림으로 설명 다음과 같이 a배열이 있다고 하자. 즉, a[0] = 5 이다. 단계 1 1) min = 0 i = 0 부터 시작한다. 즉, 위의 숫자 배열에서 맨 처음값부터 시작한다. 그리고 이때 min 이라는 변수를 사용하는데, min = i 이다. 즉, 처음에 min = 0 이다. j = i+1 = 1부터 시작한다. 그래서 혹시 a[j] < a[min] 이라면, min = j 로 바꿔준다. 즉, a[1] < a[0] 이므로 min = 1 이 된다. 2) min = 1 min..
-
버블 정렬백준/정렬 2022. 6. 29. 18:28
1. 버블 정렬 버블 정렬은 다음과 같이 진행된다. (오름차순 기준) 1. 맨 앞 숫자(a) 부터 비교를 시작한다. 2. 바로 뒤의 숫자(b) 와 비교해서 뒤의 숫자가 더 작으면 자리를 바꿔준다. 즉, a b 순서였는데 b < a 이면 b a 로 자리를 바꿔준다. 3. 그 다음 숫자와 비교하면서 위와 같은 과정을 반복한다. 4. 맨 끝까지 비교가 끝나면 다시 맨 앞 숫자를 뒤의 숫자와 비교한다. 시간 복잡도 최선의 경우 : O(N) 평균 : O(N*N) 단점 : 다른 정렬 알고리즘에 비해 교환과정이 많아서 시간 소비가 크다. 2. 그림으로 설명 다음과 같은 상황이라고 하자. 단계 1 맨 앞에 있는 값은 1이다. 바로 뒤의 5와 비교한다. 5가 더 크므로 둘의 자리를 그대로 둔다. 그 다음 5와 3을 비교..
-
삽입 정렬백준/정렬 2022. 6. 27. 20:36
1. 삽입 정렬 삽입 정렬은 다음과 같이 진행된다. 1. 현재 타깃이 되는 숫자와 이보다 앞에 위치하는 숫자들을 비교 2. 타깃 숫자 서로 교환 3. 타깃 숫자 > 앞에 위치하는 숫자 => 다음 타깃으로 이동 4. 위와 같은 방법으로 반복 시간복잡도 최선의 경우 : O(N) => 거의 정렬된 경우는 매우 효율적 최악의 경우 : O(N*N) => 역순에 가까울 수록 매우 비효율적 2. 그림으로 설명 다음과 같은 상황이라고 하자. 단계 1 첫번째 타깃은 두 번째부터 시작된다. 이때 타깃 숫자인 2보다 앞에 위치한 1이 작다. 그러면 자리 변경없이 끝이 난다. 다음 타깃으로 이동한다. 단계 2 두번째 타깃은 세 번째에 위치한 5이다. 앞에 있는 2가 더 작으므로 역시 자리 변경 없..
-
1422 숫자의 신백준/정렬 2022. 4. 17. 19:53
1. 정렬 사용하는 방법은, ex) 3=K 5=N 1234 567 89 이렇게 있다고 하자. 그렇다면 1234 567 89 를 number 배열에 넣은 다음 정렬시킨다. 그 방법은 아래에서 자세히 살펴보자. 일단 1234 567 89는 모두 1번씩 사용해야 한다. 그렇다면 이 세가지 숫자들을 어떻게 이어붙어야 가장 큰 숫자를 만들 수 있을까? 1) 먼저 1234, 567 을 어떤 순서로 이어붙어야 될까? 1234567 두개의 객체를 정렬시킬 때 두 객체의 자리가 그대로 유지된다. 2) 리턴값이 양수 => 두 객체의 자리가 변경된다. 예를 들어서 배열 input[0] =2, input[1]=3 을 가지고 정렬해보자. (compare 메서드에서는 int 형은 정렬이 안되기 때문에, Integer 형태로 저장..
-
정렬 정리백준/정렬 2022. 4. 17. 01:02
1. 문자열 정렬 => 만약 숫자를 문자로 받아서 정렬해보면? 예를 들어서 20, 12222 를 문자열 String 으로 받아서 내림차순 정렬해보자 String a = Integer.toString(12222); String b = Integer.toString(20); String input [] = new String[2]; input[0] = a; input[1] = b; Arrays.sort(input, Collections.reverseOrder()); // 내림차순 정렬 System.out.println(input[0]); System.out.println(input[1]); 아래는 이클립스 실행 결과이다. 즉, 숫자를 문자열 String 으로 입력받아서 내림차순 정렬하면, 맨 앞 숫자가 큰 ..
-
백준 8979 올림픽백준/정렬 2021. 11. 11. 22:59
반례를 찾을 수 없어서. 일단 부분점수 45 점을 맞았지만, 코드를 올린다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.PriorityQueue; import java.util.StringTokenizer; class Medal implements Comparable { int country; int g; int s; int c; public Medal(int country, int g, int s, int c) { this.country = country; this.g= g; this.s =s; this.c=c; } @Override public in..
-
5635 생일백준/정렬 2021. 10. 27. 21:37
https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.StringTokenizer; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { Buffere..
-
2750 수 정렬하기백준/정렬 2021. 10. 18. 19:56
https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new Buffere..