아이테킨의 끄적끄적

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

시간복잡도 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)의 시간복잡도를 가지는 알고리즘이라고 한다. 일반적으로 직접 함수를 만들어서 사용하는 것보다..

수많은 정렬 알고리즘 중 대표적인 5가지 정렬 알고리즘에 대해서 정리해보려고 한다. 버블 정렬(bubble sorting) 선택 정렬(Selection sorting) 삽입 정렬(insertion sorting) 병합 정렬(Merge sorting) 퀵 정렬(Quick sorting) 셸 정렬(shell sorting) 힙 정렬(heap sorting) 우선 시간복잡도 기준으로 나눠보자 O(N²) 버블 정렬 선택 정렬 삽입 정렬 O(N log₂ N) 병합 정렬 퀵 정렬 셸 정렬 힙 정렬 아래에 있는 정렬들이 일단 시간복잡도가 더 빠르니 성능이 좋은 정렬 알고리즘이라 생각해도 될 것 같다. 그러나 언제나 그렇듯 모든 상황에서 아래의 알고리즘이 더 좋다고 단정지을 수는 없다. 1. 버블 정렬(Bubble s..