N은 약수의 처음 주어진 숫자와 마지막 숫자를 곱해주면 나온다.



예를 들어 9가 N이면

3 이 약수로 있다.


그러면 3 * 3 = 9


20 이면

2 4 5 10

2 * 10 = 20 

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/1037
* BOJ 백준온라인져지 1037 약수 풀이
*/
using namespace std;
vector<int> divisor;
void quickSort(int l, int r){
int i = 0, j = r;
int pivot = divisor[(l + r) / 2];
do{
while(divisor[i] < pivot) i++;
while(divisor[j] > pivot) j--;
if(i <= j){
int temp = divisor[i];
divisor[i] = divisor[j];
divisor[j] = temp;
i++, j--;
}
}while(i <= j);
if(l < j) quickSort(l, j);
if(r > i) quickSort(i, r);
}
int main(){
int N;
scanf("%d", &N);
while(N--){
int temp;
scanf("%d", &temp);
divisor.push_back(temp);
}
quickSort(0, divisor.size()-1);
printf("%ld", (long) divisor[0] * (long) divisor[divisor.size()-1]);
}
view raw BOJ_1037.cpp hosted with ❤ by GitHub


20 은 2 * 2 * 5 로 소인수 분해가 된다.

2 와 10

저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 2490 윷놀이 풀이  (0) 2017.12.05
BOJ 백준온라인져지 10872 팩토리얼 풀이  (0) 2017.12.05
BOJ 백준온라인져지 2163 초콜릿 자르기 풀이  (0) 2017.12.05
BOJ 백준온라인져지 2293 동전 1 풀이  (0) 2017.12.04
BOJ 백준온라인져지 2573 빙산 풀이  (0) 2017.12.04

Quick Sort는

최악의 경우 n^2

평균 nlgn


퀵 정렬의 내부 루프는 컴퓨터 아키텍쳐에서 효율적으로 작동되도록 설계되어 있다.

(메모리 참조가 지역화되어 있기 때문에 CPU캐시의 히트율이 높다.)



핵심만 정리하자면


pivot의 왼쪽엔 pivot보다 작은값

pivot의 오른쪽엔 큰값


do

if arr[i] > pivot && arr[j] < pivot // i와 j는 알아서 증가한다고 가정

swap arr[i++], arr[j--]

while(i <= j)


if(left < j) quickSort(arr, left, j)

if(right > i) quickSort(arr, i, right)


저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1932 숫자삼각형 풀이  (0) 2017.12.02
BOJ 백준온라인져지 1085 직사각형에서 탈출 풀이  (0) 2017.12.01
BOJ 백준온라인져지 11651 좌표 정렬하기 2 풀이  (0) 2017.11.30
BOJ 백준온라인져지 1004 어린 왕자 풀이  (0) 2017.11.30
BOJ 백준온라인져지 1002 터렛 풀이  (0) 2017.11.30

예제 입력 

5
0 4
1 2
1 -1
2 2
3 3

예제 출력 

1 -1
1 2
2 2
3 3
0 4


y를 오름차순으로 정렬하는데, y가 같으면 x의 오름차순으로 정렬하는 문제.


quick sort를 사용하면 nlgn인데,


y, x를 둘다하게되면

시간초과여서

꼼수를 부렸다.

#include <cstdio>
#include <vector>
/**
* https://www.acmicpc.net/problem/11651
* BOJ 백준온라인져지 11651 좌표 정렬하기 2 풀이
*/
using namespace std;
void quickSort(vector<long> &arr, int left, int right) {
int i = left, j = right;
long pivot = arr[(left + right) / 2];
long temp;
do {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
} while (i <= j);
/* recursion */
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
int main(){
int T;
scanf("%d",&T);
vector<long> pointList;
while(T--){
long x1,y1;
scanf("%ld%ld",&x1,&y1);
pointList.push_back((y1+100000)*1000000+(x1+100000));
}
quickSort(pointList, 0, pointList.size()-1);
for(int i = 0, size = pointList.size(); i<size; i++){
long y = pointList[i] / 1000000 - 100000;
long x = pointList[i] % 1000000 - 100000;
printf("%ld %ld\n",x,y);
}
return 0;
}
view raw BOJ_11651.cpp hosted with ❤ by GitHub
저작자표시

'IT > 알고리즘' 카테고리의 다른 글

BOJ 백준온라인져지 1085 직사각형에서 탈출 풀이  (0) 2017.12.01
Quick Sort  (0) 2017.11.30
BOJ 백준온라인져지 1004 어린 왕자 풀이  (0) 2017.11.30
BOJ 백준온라인져지 1002 터렛 풀이  (0) 2017.11.30
BOJ 백준온라인져지 11866 조세퍼스 문제 0 풀이  (0) 2017.11.29

+ Recent posts

티스토리툴바