안녕하세요 기린입니다 :)
이번 시간에는 앞서 배웠던 정렬 알고리즘을 활용해 실제로 문제를 풀어보는 시간을 가져보겠습니다.
먼저 알고리즘 문제 풀이 사이트는 종류가 다양한데 저는 최백준님 사이트를 추천드립니다 !
백준 온라인 저지: https://www.acmicpc.net/
백준 온라인 저지에 들어가셔서 일단 회원가입 후 로그인 해보실게요 !
알고리즘을 이제 막 시작하신 분이라면 문제 카테고리에서 > 알고리즘 분류 > 단계별로 풀어보기 를 먼저 스터디 해보시는걸 추천드려요 !
저희는 단계별 풀어보기를 해보도록 하겠습니다 : ]
첫 번째 문제는 '수 정렬하기' 입니다. https://www.acmicpc.net/submit/2750
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
문제에 다른 조건 없이 단순하게 정렬을 하면 되는데요 문제풀이의 시간 제한 조건이 1초인걸 보실 수 있습니다.온라인 체점 시스템의 경우 1초에 1억번 정도 연산을 할 수 있다고 생각하고 문제를 푸시면 될 것 같은데요위 문제의 경우 1,000 * 1,000 = 1,000,000 번 정도 연산을 하기때문에 앞서 배운 정렬 알고리즘으로 코드를 작성해도큰 문제가 없다고 생각하시면 될 것 같습니다. 그럼 아래 코드를 보시겠습니다 !
#include <stdio.h>
int array[1001];
int main(void) {
int number, i, j, min, index, temp;
// N개의 수 입력
scanf("%d", &number);
// N개 만큼 입력받음
for(i = 0; i < number; i++) {
scanf("%d", &array[i]);
}
// 정렬
for(i = 0; i < number; i++) {
min = 1001;
for (j = i; j < number; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
// 출력
for (i = 0; i < number; i++) {
printf("%d\n", array[i]);
}
return 0;
}앞서 배운 알고리즘을 그대로 적용했죠 ? 이 소스 코드의 시간 복잡도는 O(N^2) 입니다. 실제로 실행시켜서 문제에 나와있는 입력값을 복사하여 입력해보고 출력이 제대로 나오는지 확인해보세요. 그리고 제출을 해보고 체점 결과를 확인해봅시다 !
앞으로 계속 이런식으로 문제를 풀어보도록 하겠습니다 :)
두 번째 문제는 '세수 정렬' 입니다. https://www.acmicpc.net/problem/2752
동규는 세수를 하다가 정렬이 하고싶어졌다.
숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다.
숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오.
입력: 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다.
세수를 하다가... 정렬이 하고싶어 지다니,,
세 개의 숫자만 정렬을 하면 되겠죠? 바로 소스코드를 봅시다.
#include <stdio.h>
int array[3];
int main(void) {
int i, j, min, index, temp;
// N개 만큼 입력받음
for(i = 0; i < 3; i++) {
scanf("%d", &array[i]);
}
// 정렬
for(i = 0; i < 3; i++) {
min = 1000001;
for (j = i; j < 3; j++) {
if (min > array[j]) {
min = array[j];
index = j;
}
}
temp = array[i];
array[i] = array[index];
array[index] = temp;
}
// 출력
for (i = 0; i < 3; i++) {
printf("%d ", array[i]);
}
return 0;
}
첫 번째 문제와 같이 3개의 수를 한번씩 비교해가면서 정렬하고있죠 :)
세 번째 문제는 '1,000,000 개 수 정렬' 입니다 https://www.acmicpc.net/problem/2751
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한줄에 하나씩 출력한다.
위 문제는 데이터의 갯수가 100만개 이므로 시간 복잡도 O(N * logN)인 퀵 정렬을 사용해 볼게요 !
#include <stdio.h>
int number, data[1000000];
void quickSort(int* data, int start, int end) {
// 원소가 1개인 경우에는 함수 종료
if (start >= end) {
return;
}
// key는 첫 번째 원소
int key = start;
int i = start + 1, j = end, temp;
// 엇갈릴 때까지 반복
while (i <= j) {
// 키 값보다 큰 값을 만날 때까지
while (data[i] <= data[key]) {
i++;
}
// 키 값보다 작은 값을 만날 때까지
while (data[j] >= data[key] && j > start) {
j--;
}
// 현재 엇갈린 상태면 키 값과 교체
if (i > j) {
temp = data[j];
data[j] = data[key];
data[key] = temp;
}
// 엇갈리지 않았다면 i와 j를 교체
else {
temp = data[j];
data[j] = data[i];
data[i] = temp;
}
}
quickSort(data, start, j - 1);
quickSort(data, j + 1, end);
}
int main(void) {
// N 입력받기
scanf("%d", &number);
// N개 만큼 입력받기
for (int i = 0; i < number; i++) {
scanf("%d", &data[i]);
}
// 정렬
quickSort(data, 0, number - 1);
// 출력
for (int i = 0; i < number; i++) {
printf("%d\n", data[i]);
}
return 0;
}
퀵 정렬을 이용해서 100만개의 데이터를 정렬해봤습니다 :) 그치만 위 소스코드를 넣어 제출하시면 시간 초과로 나오실겁니다 !!
사실 기본적으로 O(N * logN)을 요구하는 문제는 기본적인 퀵 정렬 소스코드를 넣었을 때 틀리다고 처리가 됩니다. 왜냐하면 앞서 말했듯 최악의 경우 O(N ^ 2)가 나올 수 있기 때문이죠 :]
그래서 일반적으로 C++ 알고리즘 STL(Standard Template Library) 라이브러리를 사용하는데요 STL 라이브러리에서 제공하는 sort() 함수는 퀵 정렬을 기반으로 처리하되 별도의 처리를 거쳐 최악의 경우에도 시간 복잡도 O(N * logN)를 보장한답니다. 나중에 배울 병합 정렬이나 힙 정렬을 사용한다면 더 좋구요 아래는 stl 라이브러리를 사용한 소스 코드이니 참고하시기 바랍니다
이 소스코드로 제출하면 정답처리가 됩니다
#include <stdio.h>
#include <algorithm>
int number, data[1000000];
int main(void) {
// N 입력받기
scanf("%d", &number);
// N개 만큼 입력받기
for (int i = 0; i < number; i++) {
scanf("%d", &data[i]);
}
// 정렬
std::sort(data, data + number);
// 출력
for (int i = 0; i < number; i++) {
printf("%d\n", data[i]);
}
return 0;
}
다음시간에는 병합정렬에 대해 알아보겠습니다 :]
자 그럼 즐거운 코딩하세요 !
문의: ralla0405@gmail.com
