programmer life guidance 101

www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 12334 3075 2047 28.486% 문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다..

Quick Sort 정렬할 배열이 주어진다. 마지막 수를 기준(pivot)으로 삼는다. 기준(15)보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다(정렬 완료) - Algorithm 마찬가지로 quicksort도 recursion이므로 매개변수를 명시화한다. quickSort(A[], p, r) { base case; // p >= r일 때, 정렬할 데이터가 0개 또는 1개이므로 할 일 없음 if(p= x j

> 분할정복법 Divide and Conquer merge sort와 quick sort는 분할 정복 알고리즘을 사용한다 기본적으로 recursion을 사용하여 문제를 해결하는 기법이다. 아래의 세가지 단계를 거쳐서 문제를 해결한다. 분할 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 크기는 작은 사이즈의 문제지만, 문제 자체는 전체 문제와 동일한 문제들 정복 각각의 작은 문제를 순환적으로 해결 합병 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구합 Merge Sort divide : 데이터가 저장된 배열을 절반으로 나눔 recursively sort : 각각을 순환적으로 정렬 merge : 정렬된 두 개의 배열을 합쳐 전체를 정렬 주어진 배열을 계속해서 반으로 나누다 보면 결..

> Locality의 관점에서 Quick sort가 Merge sort보다 빠른이유 Quick sort와 Merge sort는 nlogn의 시간복잡도를 가지는 대표적인 정렬 방법이다. 일반적으로 Quick sort가 Merge sort보다 크다. 그 이유는 Locality와 관련이 있다. Locality의 개념을 알아보고 왜 Quick sort가 더 빠른지 알아보도록 하자. Locality 지역성(Locality)은 CPU가 짧은 시간 범위 내에 일정 구간의 메모리 영역을 반복적으로 엑세스하는 경향을 말한다. 메모리 내의 정보를 균일하게 엑세스 하는게 아닌, 짧은 시간내에 특정 부분을 집중적으로 참조하는 특성이다. void f() { //간단한 작업을 수행 } void g() { int arr[1000]..