[2024 동계모각코] 5주차 결과

"Do it! 알고리즘 코딩테스트 with Python" 책에서

04-1 버블 정렬 부분을 풀어볼 것입니다.

---

04-1 버블 정렬

 

정렬 알고리즘의 종류와 정의에 대해 먼저 알아봅시다.

 

버블(bubble) : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

선택(section) : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

삽입(insertion) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

퀵(quick) : pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식

병합(merge) : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

기수(radix) : 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

 

버블 정렬의 핵심 이론

• 버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법입니다.
• 간단하게 구현할 수 있지만, 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편입니다.
• 루프를 돌면서 인접한 데이터 간의 swap 연산으로 정렬합니다.

버블 정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정한다.

2. 인접한 데이터 값을 비교한다.

3. swap조건에 부합하면 swap 연산을 수행한다.

4. 루프 범위가 끝날 때까지 2~3을 반복한다.

5. 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다.

6. 비교 대상이 없을 때까지 1~5를 반복한다.

---

문제 15 수 정렬하기 1

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

 

---

01단계 문제 분석하기

N의 최대 범위가 1,000으로 매우 작기 때문에 O(n^2) 시간 복잡도 알고리즘으로 풀 수 있습니다.

버블 정렬의 시간 복잡도가 O(n^2)이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에서 문제를 해결할 수 있습니다.

 

---

02단계 손으로 풀어보기

 

---

03단계 슈도코드 작성하기

N(정렬할 수 개수)
A(수 저장 리스트 선언 및 입력 데이터 저장)

for i를 0~N-1만큼 반복:
	for j를 0~N-1-i만큼 반복:
    	현재 A 리스트의 값보다 1칸 오른쪽 리스트의 값이 더 작으면 두 수 바꾸기
        
A 리스트 출력

---

04단계 코드 구현하기

# 수 정렬하기 1

n=int(input()) # 정렬할 수 개수는 n
A=[0]*n # A(수 저장 리스트 선언 및 입력 데이터 저장)

for i in range(n):
    A[i]=int(input()) # A[i]에 입력 데이터 저장

for i in range(0,n-1):
    for j in range(0,n-1-i):
        if A[j]>A[j+1]:
            A[j],A[j+1]=A[j+1],A[j] # A[j]와 A[j+1]의 값을 바꾸기
            
for i in range(n):
    print(A[i])

---

문제 16 버블 정렬 프로그램 1

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

 

 

---

01단계 문제 분석하기

버블 정렬의 swap이 한 번도 일어나지 않은 루프가 언제인지 알아내는 문제입니다!

버블 정렬의 이중 for문에서 안쪽 for문 전체를 돌 때 swap 이 일어나지 않았다 는 것은 이미 모든 데이터가 정렬됐다는 것을 의미합니다.

이때는 프로세스를 바로 종료해도 시간 복잡도를 줄일 수 있습니다.

 

하지만 이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간을 초과할 수 있습니다.

안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어가 필요합니다!

 

안쪽 for 문이 몇 번 수행됐는지 구하는 다른 아이디어:

안쪽 루프는 1에서 n-i까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있다.

 

---

02단계 손으로 풀어보기

1. 파이썬에서 기본적으로 제공하는 sort()함수로 배열을 정렬합니다. sort()함수의 시간 복잡도는 O(nlogn)입니다.

2. 각 데이터마다 정렬 전 index값에서 정렬 후 index값을 빼고 최댓값을 찾습니다. 그리고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더합니다.

 

---

03단계 슈도 코드 작성하기

N(데이터 개수), A(데이터 리스트, 단 클래스를 데이터로 담는 리스트)

for N만큼 반복:
	A 리스트 저장
    
A 리스트 정렬

for N만큼 반복:
	A[i]의 정렬 전 index - 정렬 후 index 계산의 최댓값을 찾아 저장
    
최댓값 + 1을 정답으로 출력

 

---

04단계 코드 구현하기

# 버블 정렬 프로그램1

import sys
input=sys.stdin.readline

N=int(input()) # 배열의 크기
A=[] # 정렬해야 하는 배열

for i in range(N):
    A.append((int(input()),i))
    # 정렬 기준을 고려하여 데이터, index 순서로 저장

Max = 0
sorted_A=sorted(A)

for i in range(N):
    if Max<sorted_A[i][1]-i:
        # 정렬 전 index - 정렬 후 index 계산의 최댓값 저장
        Max=sorted_A[i][1]-i
    
print(Max+1)