chanmyung

힙 정렬(HeapSort) 힙이란? http://devheat.tistory.com/12 참고 설명 힙의 최상위 노드에는 가장 큰 값이 존재한다는 특성을 이용해 정렬하는 알고리즘 최대 힙 혹은 최소 힙의 노드 삭제를 연속으로 수행해 값이 가장 큰 노드부터 내림차순 혹은 오름차순으로 꺼낼 수 있다. 구현 구현은 이전 포스팅 http://devheat.tistory.com/12 에서 만든 delete 메소드를 연달아 호출하면 된다. 최상위 노드를 꺼내고, 최하위 노드를 최상위에 위치시켜 다시 하향 heapify를 수행하는 것이 핵심 소스코드 번외 이전 포스트와 마찬가지로 Generic Heap에도 정렬 기능을 추가할 수 있다. 구현 힙 사용 예제 (Comparable을 구현한 String 클래스를 사용)

선택 정렬(Selection Sort) 설명 오름 차순 기준 가장 작은 수의 인덱스를 찾아 현재 위치 인덱스의 값과 Swap한다. 한 사이클당 교환이 1회 이루어지므로 버블 정렬 보단 효율적이다. 동작 동작 예시 정수형 배열이 [5, 3, 2, 4, 1] 5개의 원소를 가질 때 오름차순 정렬 선형 탐색으로 가장 작은 값의 인덱스를 찾음 (인덱스 0 이상에서) 결과: 4 배열의 0번지의 값과 Swap [1, 3, 2, 4, 5] 선형 탐색으로 가장 작은 값의 인덱스를 찾음 (인덱스 1 이상에서) 결과: 2 배열의 1번지의 값과 Swap [1, 2, 3, 4, 5] 선형 탐색으로 가장 작은 값의 인덱스를 찾음 (인덱스 2 이상에서) 결과: 2 배열의 2번지의 값과 Swap [1, 2, 3, 4, 5] // ..

백준 온라인 저지 2108번 통계학 문제 문제 설명 수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자. 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최대값과 최소값의 차이 N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절대값은 4,000을 넘지 않는다. 출력 첫째 줄에는 산술평균을..

백준 1181번 단어 정렬 문제 내용 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 해결 방법 Java8에 추가된 stream을 활용하면 간단하게 해결할 수 있다. 소스코드(38640 KB916 MS) 타인의 소스코드 (syntaxtree님, 39796 KB132 MS) 읽히는건 내 소..

백준 온라인 저지 1427번 소트 인사이드 문제 문제 내용 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 해결방법 문자열을 입력받아 .split("")로 각 글자별로 쪼갬 Arrays.sort(​T[] a, Comparator