sort (6) 썸네일형 리스트형 정렬(Sorting)이란? 정렬(sort) 알고리즘이란 주어진 데이터가 있을 때 특정 규칙을 준수하도록 나열하는 문제이다. 특정 규칙을 준수하도록 나열한다는 의미는 특정 문제를 풀기위해 원하는(희망하는) 순서대로 다시 나열 한다는 것이다. 예를들어 주어진 데이터 A = { 4, 2, 1, 3 } 정수형으로 되어 있다고 가정해보자. 우리가 원하는 것은 A의 원소를 숫자가 커지는대로 또는 숫자가 작아지는대로 나열하고 싶다고 한다면 숫자가 커지는대로 정렬을 하면 A = { 1, 2, 3, 4} 로 나열되고 숫자가 작아지는대로 정렬을 하면 A = { 4, 3, 2, 1}로 나열되는 것이다. 정렬에서는 숫자가 증가하는 순을 오름차순정렬(Ascending Order Sorting) 이라고 하고 숫자가 작아지는 순서대로 정렬하는 것을 내림차순.. 퀵정렬(Quick Sort) 퀵정렬은 매우 효율적인 정렬 알고리즘이며 데이터 배열을 특정 규칙에 의해 분할 하면서 정렬을 하는 분할정복(Divide & Conquer) 에 기반한다. 분할단계에서는 배열은 다음과 같은 조건이 만족되도록 2개의 부분으로 나누는데 그 중 하나는 지정된 값보다 작은 값들로 다른 하나는 지정된 값보다 큰 값들로 이루어지도록 분할한다. 여기서 지정된 값을 보통 피벗(pivot)이라고 불린다. 즉, 분할되기전 배열에서 임의의 기준값이 될 피벗을 하나 선택한다. 피벗을 배열중에 어떤 놈을 선택할지는 나중에 설명하겠다. 지금은 그냥 배열에 아무값이나 선택한다고 생각하면 된다. 지금은 일단 배열의 맨 끝에 있는 놈을 피벗으로 선택한다. 다음 그림에서 ①번은 아직 정렬되지 않은 배열데이터를 나타내고 ②번은 맨 끝에 있.. 백준 1764 문제 - 듣보잡 문제출처 : https://www.acmicpc.net/problem/1764 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 테스트케이스 입력 출력 3 4 ohhenrie charlie baesangwook obama baesangwook .. 합병정렬(Merge Sort) 지난 강좌에서는 버블정렬(Bubble Sort), 선택정렬(Selection Sort), 삽입정렬(Insertion Sort)와 같이 비교적 간단하고 이해하기 쉬우나 큰 데이터 셋에는 효율적이라고 할 수 없는 기본적인 정렬 알고리즘에 대해서 알아 봤었다. 이번 시간에는 분할정복 알고리즘을 통해 정렬이 이루어지는 합병정렬(Merge Sort)에 대해서 설명하겠다. 분할정복 알고리즘 개념이 필요하니 분할정복(Divide & Conquer) 알고리즘 을 반드시 읽어 봐야 한다. 합병정렬을 하기위해 예를들어 아래와 같은 데이터가 있다고 하자. 합병정렬은 먼저 데이터 크기가 1개가 될때 까지 반복하여 같은 반으로 나누는 분할 단계를 거친다. 여기서는 8 개 항목의 배열을 크기가 4인 배열로 분할한다. 크기가 4개.. 삽입정렬(Insertion Sort) 삽입 정렬( insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘인데 버블정렬(Bubble Sort)와 선택정렬(Selection Sort)와 마찬가지로 단순하고 이해하기 쉽지만 성능상으로는 느린 정렬 알고리즘 중 하나이다. 어떤 식으로 동작하는지 살펴보자. 위와 같이 정렬되지 않은 데이터들이 있고 오름차순(ascending)으로 정렬하는 것을 가정하고 설명하겠다. 삽입정렬은 처음 2개의 원소들을 비교한다. 14와 33 2개의 원소를 비교하면 이미 오른차순으로 정렬되어 있고 정렬 서브리스트(sorted sub-list) 14를 가지게 된다. 이제 앞으로 이동하여 33과 27을 비교한다. 33.. 버블(거품)정렬(Bubble Sort) 버블정렬은 데이터의 모든 원소를 하나씩 무식하게 비교해가면서 정렬하는 기법(부르트포스(Brute Force) 의 한 종류) 으로 정렬시 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블(거품)정렬이라고 부른다. 알고리즘을 살펴보기 전에 VisuAlgo 에서 어떤 방식으로 정렬되는지 시뮬레이션 해보자. 버블정렬은 모든 원소를 하나씩 비교해서 원하는 정렬 규칙에 맞게 두 원소를 서로 swap 하는 과정을 거친다. 쉽게 설명하기위해 정렬되지 않은 배열 numbers 가 아래처럼 있다고 할때 오름차순으로 버블정렬 하때 순서는 아래와 같다. (아래 이미지들의 출처는 튜토리얼 포인트 입니다.) 버블소트는 처음 2개의 원소(numbers[0], numbers[1])를 비교한다. 비교해서 만약 첫.. 이전 1 다음
