#include <iostream>
using namespace std;
#define number 8
int sorted[8]; // 정렬된 배열. 반드시 전역 변수로 선언.
void merge(int a[], int m, int middle, int n){
// m: 정렬할 배열의 시작 지점
// middle: 정렬할 배열의 중간 지점
// n: 정렬할 배열의 끝 지점
int i = m;
int j = middle+1;
int k = m;
// 작은 순서대로 배열에 삽입
while(i<=middle && j <= n){
// i가 j보다 더 작으면 새로운 배열에 저장
if(a[i] <= a[j]){
sorted[k] = a[i];
i++;
}
// 그렇지 않으면 j 값 저장
else{
sorted[k] = a[j];
j++;
}
k++; // 한 번 저장하면 k 증가
}
// 남은 데이터 삽입
// i가 먼저 끝났다면 j 모두 새로운 배열에 저장
if(i > middle){
for(int t = j; t <= n; t++){
sorted[k] = a[t];
k++;
}
}
// j가 먼저 끝났으면 i 모두 새로운 배열에 저장
else{
for(int t = i;t<=middle;t++){
sorted[k] = a[t];
k++;
}
}
// 정렬된 배열을 실제 배열에 삽입
for(int t = m; t <= n; t++){
a[t] = sorted[t];
}
}
void merge_sort(int a[], int m, int n){
// 크기가 1보다 큰 경우 return
if(m < n){
int middle = (m+n) / 2;
merge_sort(a, m, middle); // middle을 기준으로 왼쪽 병합정렬
merge_sort(a, middle+1, n); // middle을 기준으로 오른쪽 병합정렬
merge(a, m, middle, n); // 정렬 후 합치기
}
}
int main(void){
int arr[number] = {7, 6, 5, 8, 3, 5, 9, 1};
merge_sort(arr, 0, number-1);
for(int i=0;i<number;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
출력
1 3 5 5 6 7 8 9
시간 복잡도
병합정렬은 정확히 반씩 나눈다는 점에서 최악의 경우에도 NlogN을 보장한다.
☞ 퀵 정렬이 가지는 한계(Pivot 값에 따라 편향되게 분할할 가능성이 있다는 점에서 최악의 경우 O(N^2)의 시간 복잡도를 가짐)를 보완할 수 있음.
#include <iostream>
using namespace std;
int number = 10;
int Data[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
void quickSort_up(int *data, int start, int end){
// start: 정렬을 수행하는 부분집합의 첫 번째 원소
// end: 정렬을 수행하는 부분집합의 마지막 원소
// 원소가 1개인 경우
if(start >= end){
return;
}
int key = start; // pivot
int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
int tmp;
// 엇갈리는 경우 while 탈출
while(i <= j){
// i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
while(data[i] <= data[key]){
i++;
}
// j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
// index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
while(data[j] >= data[key] && j > start){
j--;
}
// 엇갈린 경우 pivot값과 현재 data 변경
if(i > j){
tmp = data[j];
data[j] = data[key];
data[key] = tmp;
}
// 엇갈리지 않은 경우 i와 j index의 data 변경
else{
tmp = data[j];
data[j] = data[i];
data[i] = tmp;
}
}
// 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
quickSort_up(data, start, j-1); // 왼쪽 data
quickSort_up(data, j+1, end); // 오른쪽 data
}
void quickSort_down(int *data, int start, int end){
// start: 정렬을 수행하는 부분집합의 첫 번째 원소
// end: 정렬을 수행하는 부분집합의 마지막 원소
// 원소가 1개인 경우
if(start >= end){
return;
}
int key = start; // pivot
int i = start + 1; // pivot 값에서 오른쪽으로 이동하면서 pivot값 보다 큰 값을 찾기 위해 존재하는 index
int j = end; // 정렬을 수행하는 부분집합의 마지막 원소에서부터 왼쪽으로 이동하면서 pivot 값보다 작은 값을 찾기 위해 존재하는 index
int tmp;
// 엇갈리는 경우 while 탈출
while(i <= j){
// i번째 원소가 pivot 값 보다 작으면 i 오른쪽으로 이동(pivot 값보다 큰 값을 만날 때 까지 오른쪽으로 이동)
while(data[i] >= data[key]){
i++;
}
// j번째 원소가 pivot 값 보다 크면 j 왼쪽으로 이동(pivot 값보다 작은 값을 만날 때 까지 왼쪽으로 이동)
// index가 엇갈렸을 때 작은 값과 pivot 값을 변경해주기 때문에 j는 배열을 벗어나지 못하도록 해주어야 함
while(data[j] <= data[key] && j > start){
j--;
}
// 엇갈린 경우 pivot값과 현재 data 변경
if(i > j){
tmp = data[j];
data[j] = data[key];
data[key] = tmp;
}
// 엇갈리지 않은 경우 i와 j index의 data 변경
else{
tmp = data[j];
data[j] = data[i];
data[i] = tmp;
}
}
// 엇갈리는 경우 pivot 값이 정렬되었으므로, pivot 값을 재설정해주어야 함
quickSort_down(data, start, j-1); // 왼쪽 data
quickSort_down(data, j+1, end); // 오른쪽 data
}
int main(void){
quickSort_up(Data, 0, number-1); // 오름차순
for(int i=0;i<10;i++){
cout << Data[i] << " ";
}
cout << endl;
quickSort_down(Data, 0, number-1); // 내림차순
for(int i=0;i<10;i++){
cout << Data[i] << " ";
}
return 0;
}
출력
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
만약 아래 배열을 정렬한다면?
선택 정렬의 시간 복잡도: N^2 = 100
퀵 정렬의 시간 복잡도:
1 2 3 4 5 => 5 * 5 = 25
6 7 8 9 10 => 5 * 5 = 25
-> 25 + 25 = 50
∴ O(NlogN)의 시간복잡도를 갖는 알고리즘을 이용하면 100만개 정도의 데이터는 어렵지 않게 정렬이 가능하다.
시간복잡도
평균 : N*logN
최악의 경우: N^2
만약 이미 오름차순 정렬되어있는 배열을 퀵정렬을 이용해 오름차순 정렬한다면?
=> 분할 정복의 이점을 사용하지 못하고 있으므로, 이런 경우에는 insertion sort를 사용하는 게 효율적이다.
#include <iostream>
using namespace std;
int main(void){
int i, j, tmp;
int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i=0;i<10;i++){
for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
if(arr[j] > arr[j+1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for(i=0;i<10;i++){
cout << arr[i] << " ";
}
return 0;
}
출력
1 2 3 4 5 6 7 8 9 10
시간 복잡도
10 + 9 + 8 + ... + 1
= 10 * (10 - 1) / 2
= N * (N - 1) / 2
= O(N^2)
실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다. : Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다. 반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
예제 입출력
우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.
처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.
num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.
#include <iostream>
#include <string>
using namespace std;
int cal_len(long long n){
string num = to_string(n);
return num.length();
}
long long ispossible(int n){
// n의 길이 계산
int len = cal_len(n);
string num;
// n의 길이만큼 1로만 구성된 문자열 만들기
for(int i=0;i<len;i++){
num += '1'; // O(n)으로 동작
}
while(true){
// num이 n의 배수인지 확인
if(num%n==0) return num.length();
// num 한 자리 추가
num += '1';
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 런타임 에러(out_of_range)로 실패 ㅠ
num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.
그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.
결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.
Algorithm
Brute Force 1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음 2. num이 n으로 나누어 떨어지는지 확인 2-1. 나누어떨어지면 num의 길이 return 2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산) → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !
Code
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num의 크기 줄여주기
num%=n;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
