본문 바로가기
반응형

알고리즘31

[Java][프로그래머스][Level 2] 가장 큰 수 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 생각 기본적인 정렬로는 안된다. 따라서 Compara.. 2019. 6. 23.
[Java][알고리즘][정렬] Quick Sort / 퀵 정렬 퀵 정렬 가장 많이 쓰이는 정렬 알고리즘이다. 최악의 경우는 O(N^2) 이지만 실제로 수행해보면 합병 정렬보다 더 좋은 성능을 낸다. pivot을 기준으로 pivot보다 작은 원소들은 pivot의 왼쪽, 큰 원소들은 오른쪽에 위치 시켜 분할 한 후, 새롭게 pivot을 만들어 재귀적으로 정렬하는 알고리즘이다. 위 예시를 보면서 이해해보도록 하자. 일반적으로는 맨 왼쪽 원소를 pivot으로 정한다. pivot을 중간값으로 잘 정하는게 퀵 정렬에서의 성능을 좌우한다. 이를 위해 3개의 원소를 정해서 중간값을 pivot으로 하는 Median of Three나 9개의 원소를 뽑아 3개씩 나눠 각 중간값을 구하고 다시 그 3개 중에서 중간값을 정해 pivot으로 정하기도 하지만.. 맨 왼쪽으로 그냥 하도록 하자.. 2019. 6. 19.
[Java][알고리즘][정렬] Merge Sort / 합병 정렬 합병 정렬 분할 정복 방식을 이용한 정렬이다. 드디어 성능이 좋아진다! O(NlogN)을 보장해준다. 각 배열을 계속 분할하여 정렬을 시키고 다시 합치면서 다시 정렬을 해준다. Merge에서는 위와 같은 과정이 생긴다. 단점으로는 보조 배열을 만들어야 해서 정렬하고자 하는 배열과 같은 크기의 보조 배열을 만들어줘야 한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 public class Merge { public static boolean isless(Comparable a, Comparabl.. 2019. 6. 18.
[Java][알고리즘][정렬] Insertion Sort / 삽입 정렬 삽입 정렬 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 '삽입' 하는 것이다. 어느 정도 정렬이 되있는 상태의 배열에서는 좋은 성능을 낼 수 있다. 하지만 만약 역으로 정렬된 경우라면 선택, 버블 정렬과 같은 성능이 나온다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 public class Insertion { public static boolean isless(Comparable a, Comparable b) { return a.compareTo(b) 2019. 6. 17.
반응형

티스토리툴바