아이테킨의 끄적끄적

통계학에서 주로 사용되는 개념들을 직접 구현해보라고 만든 문제인 것 같다. 산술평균이나, 중앙값, 범위 구하는 문제는 max,min,sum,등등 파이썬 내장함수를 이용하면 어렵지 않게 구할 수 있는 문제다. 특별히 최빈값을 구할때 collections 모듈에서 Counter클래스 썻다. 코딩테스트에서는 다른 라이브러리를 불러오지 못하게 하는 경우도 있다고 들어서 이런 모듈을 불러와서 문제를 풀어도 될지에 대해서 불안하지만 Counter함수에 대해서 공부도 할겸 구글링하면서 풀어보았다. 여기에 counter에 대한 documentation이 있다. https://docs.python.org/ko/3/library/collections.html#collections.Counter collections — 컨..

계수정렬(counting sort)을 사용해서 풀어야하는 문제다. 계수정렬의 가장 큰 특징은 비교정렬이 아니다 라는 점이다. 비교정렬은 두수의 대소관계를 반복적으로 계산하면서 푸는 정렬방법인데 계수정렬은 이런 방법을 사용하는게 아니라 말 그대로 숫자들의 개수를 세면서 정렬한다. 그리고 계수정렬의 시간복잡도는 선형시간이다 O(n) 성능이 좋다는 다른 정렬방법(퀵정렬 - O(n^2), 병합정렬 - O(nlogn), 힙정렬 - O(nlogn))들 보다도 훨씬 빠르다. 그러나 단점은 제한이 많다는 것이다. 값들간의 차이 크기가 별로 없거나 값들이 정수로만 이루어져있을때 사용이 가능하다. 역시나 모든 문제에서 좋은 알고리즘은 없고 그때그때마다 상황에 맞는 알고리즘을 찾아서 사용해야 한다. 계수정렬의 스탭별 자세한..

시간복잡도 O(nlogn)을 가지는정렬을 사용해야 통과가 가능한 문제이다 1. 파이썬 내장함수 사용(sorted) 2. 퀵정렬 3. 퀵정렬(cache사용없이) 4. 병합정렬 5. 힙정렬 이 다섯가지 정렬방법으로 풀어보았다. (그리고 시간이 중요한만큼 sys.stdin.readlind으로 입력값을 받았다.) 1. 파이썬 기본 내장함수 sorted() import sys n = int(input()) li = [] for _ in range(n): li.append(int(sys.stdin.readline())) for i in sorted(li): print(i) 병합정렬을 기반으로 만들어진 함수이며 O(nlogn)의 시간복잡도를 가지는 알고리즘이라고 한다. 일반적으로 직접 함수를 만들어서 사용하는 것보다..