package com.lth.algorithm.programmers; import java.util.Arrays; import java.util.Comparator; public class Sort { public static void main(String[] args) { Sort sort = new Sort(); System.out.println(sort.solution(new int[]{300,30030030, 12, 4, 647467454, 2222, 2, 0, 260})); } // 길이가 같을 경우 그냥 비교한다. // 길이가 다를경우 맨 가장 앞부터 하나씩 비교 // 끝까지 비교했는데 같은값이 나올경우 짧은 문자열의 길이만큼 긴 문자열을 자른 후 비교 // 위의 과정을 계속 반복 // 만약 ..
정렬
정렬을 할때에는 여러 알고리즘을 적용할 수 있습니다. 알고리즘의 성능은 일반적으로 데이터의 크기에 따라 결정됩니다. 따라서 데이터 크기에 따라 가장 효과적인 정렬 방법을 예시 코드와 함께 정리해 보겠습니다 작은 크기의 데이터 (수십 개 이하) 버블 정렬, 삽입 정렬이나 선택 정렬과 같은 간단한 알고리즘들이 효과적일 수 있습니다. 버블 정렬 public class BubbleSort { public static void main(String[] args) { int[] array = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(array); System.out.println("Sorted array: " + Arrays.toString(array)); } static void ..
단어 정렬 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 256 MB 92851 38585 28821 40.388% 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 예제 입력 1 13 but i wont hesitate no more no more it cannot wait..
Dicide-and-Conquer qaradigm을 사용 즉 풀기 어려운 정렬을 계산하기 쉽게 나누어 진행하는것 partition을 이용 Pivot을 정해서 작은것은 왼쪽 큰것은 오른쪽으로 위치시킨다. 재귀호출을 통해 계속 반복한는것 퀵 정렬의 수행시간은 Pivot을 어떨게 설정하냐에 따라 달라진다. Merge sort 는 nlogn이지만 공간은 사용해야 한다는 단점이 있다. HeapSort는 max-heap구조를 만들어야 한다는 어려움이 있다. Quicksort는 nlogn이지만 최악의 경우 시간이 많이 늘어난다.
정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명할 수 있다. 문제정의, 알고리즘 설명, 정확성 증명, 성능 분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3......... an) - 출력 (output) 입력된 숫자 위 배열이 오름차순 조건을 만족하도록 재 배열하는 것 합병 정렬(Merge Sort) - 합병을 이용한 정렬 알고리즘 - 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병 - 각 배열의 가장 왼쪽에 있는 값을 비교해보면 가장 작은 수를 알 수 있다. 정렬을 하기에는 너무 큰 배열을 쪼개어 정렬한 후 합병한다. 이를 위해 합병 정렬을 필요한 것이다. A divide-and-conquer approach 크기가 커서 풀기 어려운 하나의..
정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 선택정렬 알고리즘 선택정렬(Selection sort) - 선택하여 정렬하는 알고리즘 - 최소값 선택 정렬 (Min-Selection sort) 가장 작은 값을 선택(오름차순) - 최대값 선택 정렬 (Max-Selection sort) 가장 큰 값을 선택(내림차순) - 정확성 증명 수학적 귀납법을 이용 i번쨰 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명 - 성능분석 최선 최악의 경우 수행..
