이코테

선택, 삽입, 퀵 정렬에 이어서 마지막으로 계수 정렬에 대해 공부해 보자. 계수 정렬(Count Sort) 계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작한다. 계수 정렬은 모든 데이터가 양의 정수일 때 데이터의 개수가 N개, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N+K)의 수행 시간을 보장한다. 하지만 한 가지 조건이 붙는데, 바로 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. 계수 정렬이 이러한 특징을 가지는 이유는 계수 정렬을 이용할 때 모든 범위를 담을 수 있는 크기의 배열..

퀵 정렬은 삽입 정렬과 선택 정렬에 비해 훨씬 빠른 정렬 알고리즘이고 많이 사용되는 알고리즘이다. 병합 정렬과 함께 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다. 퀵 정렬 (Quick Sort) 기본 컨셉은 아래와 같다. 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식을 반복한다. 원리만 이해해도 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할 수 있다. 퀵 정렬에서는 큰 숫자와 작은 숫자를 교환할 때의 기준을 정하는데 이를 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 ..

선택 정렬은 매번 가장 작은 것을 선택해서 정렬했다. 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 시간이 매우 오래 걸리기 때문에 다른 접근법이 필요할 듯하다. 삽입 정렬(Insertion Sort) 삽입 정렬은 데이터를 하나씩 확인하여 각 데이터를 적절한 위치에 삽입하는 식으로 정렬을 진행한다. 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 혹은 완전히 정렬되어있을 때는 매우 효율적이다. 반면에 선택 정렬은 데이터가 완전히 정렬되어있어도 시간 복잡도가 같다. 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는..

가장 기본적인 정렬 방법 중 하나인 선택 정렬에 대해서 알아보자. 선택 정렬 (Selection sort) 기본적인 컨셉은 전체 데이터에서 가장 작은 값을 맨 왼쪽에 넣고, 그다음엔 두 번째로 작은 값을 왼쪽에서 두 번째에 넣는 방식이다. 이런 식으로 반복해주면 점점 정렬이 될 것이고 마지막 데이터는 가만히 두어도 정렬된 상태일 것이다. 위의 그림에서는 총 7개의 데이터를 7-1번만큼 반복해서 정렬을 하였다. 데이터가 N개이면 반복 횟수는 N-1번일 것이다. ##메인 함수 부분## if __name__ == "__main__": array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index = i for j in range(i+1, len(arr..

파이썬으로 시험을 보기 전에 기본 문법은 확실히 정리하고 보자. round() IEEE754 표준에서는 실수형을 저장하기 위해 4바이트, 8바이트라는 고정된 크기의 메모리를 할당하기 때문에 현대 컴퓨터 시스템은 대체로 실수 정보를 표현하는 정확도에 한계를 가진다. 파이썬에서도 0.3 + 0.6을 출력해보면 0.89999999999999가 출력된다. round() 함수는 소수점 특정 자릿수에서 반올림을 해준다. 코테에서는 흔히 소수점 다섯 번째 자리에서 반올림한 결과가 같으면 정답으로 인정하는 식이다. round() 함수는 두 번째 인자로 (반올림하고자 하는 위치 - 1)을 넘겨줘야 한다. a = 0.3 + 0.6 print(round(a,4)) 리스트 자료형 리스트 관련 메서드 insert() 함수와 r..