7. 기초 정렬 알고리즘 문제 풀이

백준 사이트

https://www.acmicpc.net/

Baekjoon Online Judge

 

- 처음이면 이 두 카테고리 중 풀기!

문제 > 단계별로 풀어보기

문제 > 알고리즘 분류

 

- 1초에 1억번 연산 가능하다고 생각하면 된다.

 

- 웬만한 알고리즘 문제를 풀 때 배열은 +1의 크기로 해놓는 것이 좋다.

만약에 N이 1000이라면 하단처럼 배열의 크기는 1001로 해놓는다.

 

- 소스코드 비공개, 언어는 c++ 11로 설정.

 

 

- 백준 내 프로필 : https://solved.ac/profile/1010hy

 

---

1. 단순정렬 : https://www.acmicpc.net/problem/2750

이 문제에서는 1000 x 1000 = 1000000이기 때문에 1억보다 작은 숫자이므로 계산 시간의 속도 상관없이 어느 정렬이든 사용할 수 있다.

풀이 : https://github.com/1010hy/Algorithm_Baekjoon/tree/main/%EB%B0%B1%EC%A4%80/Bronze/2750.%E2%80%85%EC%88%98%E2%80%85%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0

 

 

2. 세 수 정렬 : https://www.acmicpc.net/problem/2752

풀이 : https://github.com/1010hy/Algorithm_Baekjoon/tree/main/%EB%B0%B1%EC%A4%80/Bronze/2752.%E2%80%85%EC%84%B8%EC%88%98%EC%A0%95%EB%A0%AC 

 

 

3. 100만 개 정렬 : https://www.acmicpc.net/problem/2751

 

100만x100만은 1억이 넘기 때문에 반드시 시간복잡도가 O(N*logN)인 정렬로 풀어야 한다.

퀵정렬의 평균 시간복잡도는 O(N*logN)이지만, 최악의 경우 O(N*N)이 되기 때문에 퀵정렬을 사용하여 풀었을 때 시간초과가 되었다..