난이도 ●○○ l 풀이 시간 15분 l 시간 제한 1초 l 메모리 제한 128MB l 기출 T 기업 코딩테스트 문제 하나의 수열에는 다양한 수가 존재한다. 이러한 수는 크기에 상관없이 나열되어 있다. 이 수를 큰수부터 작은 수의 순서로 정렬해야 한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오. 입력조건 첫쨰 줄에 수열에 속해있는 수의 개수 N이 주어진다. ( 1

정렬 라이브러리 알고리즘은 오랫동안 연구된 분야이며, 특히 정렬 알고리즘은 매우 많이 연구된 주체이다. 그렇기 떄문에 정렬 알고리즘은 이 밖에도 매우 다양한 종류가 있다. 물론, 현대의 정렬 알고리즘은 정립되어 있기 때문에 앞으로는 큰 개선이 이루어질 것으로 예상하기는 어렵다. 따라서 정렬 알고리즘 문제는 어느정도 정해진 답이 있는, 즉 외워서 잘 풀어낼 수 있는 문제라고 할 수 있다. 지금까지 다양한 정렬 알고리즘에 대해서 알아보았다. 우리가 알고리즘 문제를 풀 때는 앞서 다루었던 에제처럼 정렬 알고리즘을 직접 작성하게 되는 경우도 있지만 미리 만들어진 라이브러리를 이용하는 것이 효과적인 경우가 더 많다. 파이썬은 기본 정렬 라이브러리인 Sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동..

퀵 정렬 퀵 정렬은 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 이 책에서 다루지는 않지만 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 '병합 졍렬' 알고리즘이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 그렇다면 퀵 정렬은 도대체 어떻게 동작하길래 이름부터가 '빠른 정렬 알고리즘' 인지 알아보자. '기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?' 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이해하기까지 시간이 걸리겠지만 원리를 이해하면 병합 정렬, 힙 정렬 등 다른 고급 정렬 기법에 비해 쉽게 소스코드를 작성할수 있다. 퀵 정..

삽입정렬 선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 그렇다면 다른 접근 방법에 대해서 생각해보자. '데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?' 삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 물론 삽입 정렬은 선택 정렬에 비해 구현 나니이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 잘 알려져 있다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면 삽입 정렬은 그렇지 않다. 삽입 정렬은 특정한 데이터를 적절한 위치에 '삽입' 한다는 의미에서 삽입 정..

선택 정렬 컴퓨터가 데이터를 정렬할 때 어떻게 할지 한번 생각해보자. 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 잇는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번쨰 데이터와 바꾸는 과정을 반복하면 어떨까? 이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort) 알고리즘 이라고 한다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다. 이해를 돕기 위해 에제를 통해 자세한 동작 원리를 확인하겠다. 정렬 알고리즘에서는 흔히 데이터의 개수를 N 이라고 표현한다. 다음 예제에서는 N=10인 경우를 가정한다. 또한 다음의 그림에서 회색 카드는 ..

정렬 알고리즘 개요 정렬(Sorting)이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 이 언급하려 한다. 더불어 파이선에서 제공하는 기본 정렬 라이브러리를 적용하여 좀 더 효과적인 정렬 수행 방법도 다루여 한다. 보통 정렬부터 공부하면 '알고리즘의 효율성'을 쉽게 이해할 수 있어 알고리즘 개론서 초반에 정렬 알고리즘을..