Little bIT awesome

Comparison Sort N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N!임 따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도임) 이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것 정렬하는 숫자가 특정 범위 안에 있을 때 사용함 Process public static void countingSort(int[] arr, int n) { // {5, 4, 3, 2, 1} int[] buffer = new int[n]; int m = g..

기수 정렬 (Radix Sort) Comparison Sort N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N! 따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N!를 만족하는 h를 가져야 하고, 이 식을 h > O(nlogn)을 가져야 한다. (h == 트리의 높이, 즉 Comparison Sort의 시간 복잡도) 데이터를 구성하는 기본 요소 (Radix)를 이용하여 정렬을 진행하는 방식 자릿 수의 값 별로 정렬을 하기 때문에 나올 수 있는 값의 최대 사이즈는 9 정의 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 ※ 분할 정복 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각..

힙 정렬 (Heap Sort) 정의 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로 한 정렬 방식 불안정 정렬에 속한다. ※ 완전 이진트리  마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 가장 왼쪽에 있다. 퀵 정렬과 합병 정렬의 성능이 좋기 때문에 힙 정렬의 사용 빈도가 높지는 않다. 힙 자료구조의 활용 시에 알아두면 좋음 힙 정렬이 유용할 때 가장 크거나 가장 작은 값을 구할 때 : 최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능 최대 k만큼 떨어진 요소들을 정리할 때 : 삽입 정렬보다 더욱 개선된 결과를 얻을 수 있다. Process 1. 최대 힙을 구성 2. 현재 힙 루트는 가장 큰 값이 존재함..

병합 정렬 (Merge Sort) 정의 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 ※ 분할 정복 (divide and conquer) 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략  빠른 정렬로 분류되며, 퀵 정렬과 함께 많이 언급되는 정렬 방식이다. 안정 정렬에 속한다. 퀵 정렬과의 차이점 퀵 정렬 : 우선 피벗을 통해 정렬 (partition) → 영역을 쪼갬(quickSort) 병합 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge) Process static void mergeSort(int[] array, int left, int right) { if (left < right) { int mid =..

거품정렬 (Bubble Sort) 정의 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 거품 정렬이라고 이름 지어짐 Process 1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째와 세 번째 원소를 ... 이런 식으로 (마지막 - 1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다. 2. 1회전을 수행하고 나면가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제회된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 자바 코드 void bubbleSo..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Collections; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String n = br.readLine(); String[] arr = n.split(""); Integer[] arrInt = new Integer[arr.length]..

import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); StringTokenizer st; for (int i = 0; i < n; i++) { st = new StringTokenizer(..

BufferedReader & BufferedWriter BufferedReader : Scanner 와 유사 BufferedWriter : System.out.println();과 유사 기존에 사용하던 Scanner, System.out.println();보다 속도 측면에서 훨씬 빠르기 때문에 많은 데이터를 처리할 때 유리하다. : 입력된 데이터가 바로 전달되지 않고 버퍼를 거쳐 전달되므로 데이터 처리 효율성을 높임 BufferedReader import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; BufferedReader br = new BufferedReader(new InputStream..

다음에 올 숫자 다른 사람의 풀이도 분석해보자 a, b, c에 대입해서 풀었네 깔끔하다 다항식 더하기 예외에 대해서 처리해주는 것이 얼마나 중요한지를 깨닫게 해준 문제. 만약 계수가 1이라면? 계수가 생략되어서 따로 처리를 해주어야 한다. 출력할 때 숫자가 0이라면 0을 따로 출력하지 않도록 따로 처리해주어야 한다. 예외를 처리하지 않아서 몇몇 케이스에서만 오류가 떠서 왜인지 생각하느라 애먹었던 문제였다. 최빈값 구하기 공간적으로 비효율적인 코드같긴하다. 다른사람의 코드를 보자 enumerate()함수는 index와 원소에 동시에 접근한다. (index, 원소) 형태의 튜플을 반환한다. for문을 돌린 후에도 i가 0이라면, 즉, set(array)에 원소가 하나밖에 없다면 그 원소가 최빈값이다. 따라서..

치킨 쿠폰 몫과 나머지를 둘 다 사용하는 경우 divmod를 사용하면 편하다. divmod는 몫과 나머지를 튜플 형태로 반환해준다. print(divmod(3, 2)) # (1, 1) 유한소수 판별하기 파이썬의 최대공약수 최소공배수 함수를 활용해보자 import math한 다음에 최대공약수: math.gcd() 최소공배수: math.lcm() 저주의 숫자 다른 사람의 풀이를 보니까 100까지라 노가다를 한 사람도 있었고 while문으로 조건에 만족하지 않을 때까지 1씩 더한 사람도 있었다. 후자의 풀이를 시도했다가 꼬여서 위의 풀이로 풀었음. 그리고 배운점은 ㄹㅇ 코테를 풀 때 안풀리면 노가다를 해서라도 풀어보자..!라는 것 특이한 정렬 꽤나 복잡하게 풀었는데 파이썬에는 sort함수가 매우 잘 되어있고,..