알고리즘 [Algorithm] - 기초 정렬문제 풀어보기 (5) (C, Python)

import sys
a = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(a)]
data_int = list(map(int,data))
data_int.sort()
for j in range(a):
    print(data_int[j])

기초 정렬 문제 풀어보기

지금까지 선택정렬, 버블정렬, 삽입정렬, 퀵정렬을 배웠다. 이를 활용해서 백준 온라인 저지의 문제를 풀어보자!

 

 

1. 세 숫자 정렬 : https://www.acmicpc.net/problem/2752

2752번: 세수정렬

C

#include <stdio.h>
int main(void){

	int array[3], i, j, temp, min, idx;
	for (i = 0; i < 3; i++) {
		scanf("%d", &array[i]);
	}

	for (i = 0; i < 3; i++) {
		min = array[i];
		idx = i;
		for (j = i; j < 3; j++) {
			if (min > array[j]) {
				min = array[j];
				idx = j;
			}
		}
		temp = array[i];
		array[i] = min;
		array[idx] = temp;

	}

	for (i = 0; i < 3; i++) {
		printf("%d ", array[i]);
	}
}

 

Python

a = list(map(int,input().split()))
a.sort()
print(f"{a[0]} {a[1]} {a[2]}")

 

 

위의 제출은 C언어를 활용해 문제를 푼 것이고, 아래는 Python을 이용해 문제를 푼 것이다. C언어는 로우레벨 언어이고, Python은 하이레벨 언어두개의 수행시간이 많이 차이나는 것을 확인할 수 있다! 각자에게 필요한 언어를 적절히 사용하는게 좋을 것 같다 하하

 

 

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

2750번: 수 정렬하기

C

#include <stdio.h>

int main(void){
    	//실습문제 2
	int n, i, j, tmp,array[1001],idx,min;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &array[i]);
	}

	for (i = 0; i < n; i++) {
		min = 1001;
		for (j = i; j < n; j++) {
			if (min > array[j]) {
				min = array[j];
				idx = j;
			}
		}

		tmp = array[i];
		array[i] = array[idx];
		array[idx] = tmp;
	}

	for (i = 0; i < n; i++) {
		printf("%d\n", array[i]);
	}
}

출력할 때 줄바꿈을 잘하자!

 

 

 

 

Python

import sys
n = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(n)]
data_int = list(map(int,data))
data_int.sort()
print(data)
print(data_int)

for i in range(n):
    print(data_int[i])

나는 Python을 사용할 때 Visual Studio보다 Colab을 주로 사용하는데, Colab에서는 sys라이브러리를 활용한 입력이 되지 않는다. 그것도 모르고 계속 시도한 바보... 쯧

  아 그리고 Python을 활용할 경우 리스트의 원소들을 int형으로 형변환해줘야 문제가 풀린다. 주의하자.

 

이번에도 실행속도가 굉장히 많이 차이 나는것을 볼 수 있다 !

 

 

3. 수 정렬하기 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

이번에는 위 두문제와 다르게 데이터의 갯수가 100만개이다. 현재는 시간제한이 2초가 되었지만 과거에는 1초여서 아마 O(N^2)가 걸리는 선택정렬, 버블정렬 등으로는 문제가 안풀린다. 퀵정렬으로 풀어보고 안풀린다면 구글링을 통해 문제를 풀어보자.

 

Python

import sys
a = int(sys.stdin.readline())
data = [sys.stdin.readline().strip() for i in range(a)]
data_int = list(map(int,data))
data_int.sort()
for j in range(a):
    print(data_int[j])

 

 

 

 

---

이 글은 나동빈님의 실전 알고리즘 강좌 (Algorithm Programming Tutorial)를 참고해 작성하였습니다.

https://www.youtube.com/watch?v=qQ5iLNjpxSk&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz