반응형
DoZZang
Do IT
DoZZang
전체 방문자
오늘
어제
  • Programming
    • Git
    • Web
    • 기타
    • Python
      • CodeUp
    • Math
    • Algorithm
    • Baekjoon
    • C,C++
    • Life
      • 독서
      • Just
      • 영화

블로그 메뉴

  • 홈
  • 태그
  • 방명록

인기 글

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
DoZZang
Baekjoon

[C] 백준 2750번 : 수 정렬하기

[C] 백준 2750번 : 수 정렬하기
Baekjoon

[C] 백준 2750번 : 수 정렬하기

2023. 2. 2. 12:39
반응형

https://www.acmicpc.net/problem/2750

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int N = 0, temp = 0;
	int arr[1000] = { 0, };
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	for (int i = 0; i < N; i++) {	//시간복잡도가 O(n^2)인 버블정렬
		for (int j = i + 1; j < N; j++) {
			if (arr[i] > arr[j]) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
	}
	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}
	return 0;
}

N의 범위가 1000으로 크지 않았기에 시간복잡도가 O(n^2)인 버블정렬을 이용할 수 있었습니다.

버블정렬은 정렬 알고리즘 중 상대적으로 간단하지만 비효율적인 정렬입니다.

문제에 나와있는 예제를 도식화하였습니다. arr 배열의 초기상태입니다.

0번째 원소가 (0+1)1번째 원소부터 차례대로 비교를 해나가기 시작하는데

0번째 원소의 값보다 비교하는 값이 더 작다면 두 값을 교환해줍니다.

이때,temp 변수를 이용하여 값이 사라지지 않도록 해줍니다.

아직 첫 번째 루프가 끝나지 않았습니다. 교환한 값인 2보다 작은 값이 있는지 2번 인덱스부터 비교합니다.

마지막 4번 인덱스의 값이 2보다 작으므로 위와 마찬가지로 교환해줍니다.

 

배열의 마지막 원소까지 비교를 마쳤으므로 첫 번째 루프를 마칩니다.

첫 번째 루프를 끝내게 되었을 때 배열의 첫번째 원소는 배열의 값 중 가장 작은 값이 위치합니다.

이를 반복해줍니다.

두 번째 루프입니다. 배열의 두 번째원소와 (2+1)세번째 원소부터 비교를 시작해나갑니다.

배열의 마지막 원소의 값이 두 번째 원소의 값보다 작기 때문에 교환해줍니다.

이후 배열의 네 번째 원소부터 비교를 시작하지만 2보다 작은 값이 없으므로

두 번째 루프는 이렇게 끝이납니다.

잘 보시면 두 번째 루프만에 배열이 오름차순으로 정렬된 것을 알 수 있습니다.

따라서 세 번째 루프부터는 보여드리지 않겠습니다. 비교는 하되 교환은 하지 않으니까요.

 

위 경우는 운이 좋은 경우입니다. 이렇게 운이 좋게 오름차순으로 정렬이 끝났다고 해서

반복문이 멈추는 것은 아닙니다. 항상 마지막 루프까지 성실하게 돕니다.

따라서 버블정렬은 최악,평군,최상의 경우 모두 시간복잡도가 O(n^2)이 됩니다.

 

정렬 알고리즘에 대해서는 따로 분류해서 다루겠습니다.

반응형
저작자표시 (새창열림)

'Baekjoon' 카테고리의 다른 글

[C++]백준 2309번: 일곱 난쟁이  (1) 2024.02.05
[C] 백준 10829번 : 이진수 변환  (0) 2023.08.10
[C] 백준 2563번 : 색종이  (0) 2023.02.01
[C] 백준 2090번 : 골드바흐의 추측  (2) 2023.01.31
[C]백준 2566번 : 최댓값  (0) 2023.01.29
    'Baekjoon' 카테고리의 다른 글
    • [C++]백준 2309번: 일곱 난쟁이
    • [C] 백준 10829번 : 이진수 변환
    • [C] 백준 2563번 : 색종이
    • [C] 백준 2090번 : 골드바흐의 추측
    DoZZang
    DoZZang
    과정은 힘들지만 성장은 즐겁습니다.

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.