제로베이스 데이터 파트타임 스쿨 학습 일지 [25.05.01]

[강의 요약]

[Part 03. 자료구조&알고리즘 with Python_ Ch 03. 알고리즘] 강의 수강

05_순위부터 12_선택 정렬(실습)까지 강의 수강하였음

🐢 100일 챌린지 🔥 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰                                       ] 46/100일 (46%)

근로자의 날(?)이어서 평소보다 많이 강의 수강을 했다.

오늘은 한곡 반복하면서 글 작성함

 

 

 

[05_순위]

▶ 순위란?

서로의 점수를 비교하여 서열을 정하는 것을 말한다.

아래의 사진처럼 다른 값들과 비교해서 자신의 위치(등수)를 매기는 것이 바로 순위다.

 

 

▶ 코드

import random

# 50~100 사이에서 중복 없이 20개의 점수 무작위 추출
scores = random.sample(range(50, 101), 20)

# 순위를 저장할 리스트를 0으로 초기화
ranks = [0 for i in range(20)]

# 각 점수를 다른 점수와 비교하여 순위 계산
for idx, sco1 in enumerate(scores):
    for sco2 in scores:
        if sco1 < sco2:
            ranks[idx] += 1

# 결과 출력
print(scores)
print(ranks)

# 점수와 순위 출력
for i, s in enumerate(scores):
    print(f'score: {s} \t rank: {ranks[i] + 1}')

최종 출력 시에는 순위 +1로 보정해서 1등부터 시작하게 해야 한다.

모든 쌍 비교가 필요하므로 시간복잡도는 O(n²)이다.

[출력 결과]

결과는 실행 시마다 랜덤이다.

[67, 100, 58, 91, 70, 94, 65, 88, 98, 71, 61, 72, 63, 62, 66, 73, 78, 75, 64, 60]
[16, 0, 18, 4, 14, 2, 17, 6, 1, 13, 15, 12, 10, 11, 9, 8, 5, 7, 10, 15]

score: 67 	 rank: 17  
score: 100 	 rank: 1  
score: 58 	 rank: 19  
score: 91 	 rank: 5  
score: 70 	 rank: 15  
...

 

 

 

[06_순위(실습)]

▶ 실습 문제

 

 

▶ 코드 : rankMod.py (모듈 파일)

class RankDeviation:

    def __init__(self, mss, ess):
        self.midStuScos = mss
        self.endStuScos = ess
        self.midRanks = [0 for _ in range(len(mss))]
        self.endRanks = [0 for _ in range(len(mss))]
        self.rankDeviation = [0 for _ in range(len(mss))]

    def setRank(self, ss, rs):
        for idx, sco1 in enumerate(ss):
            for sco2 in ss:
                if sco1 < sco2:
                    rs[idx] += 1

    def setMidRank(self):
        self.setRank(self.midStuScos, self.midRanks)

    def getMidRank(self):
        return self.midRanks

    def setEndRank(self):
        self.setRank(self.endStuScos, self.endRanks)

    def getEndRank(self):
        return self.endRanks

    def printRankDeviation(self):
        for idx, mRank in enumerate(self.midRanks):
            deviation = mRank - self.endRanks[idx]
            if deviation > 0:
                deviation = '↑' + str(abs(deviation))
            elif deviation < 0:
                deviation = '↓' + str(abs(deviation))
            else:
                deviation = '=' + str(abs(deviation))

            print(f'mid_rank: {mRank} \t end_rank: {self.endRanks[idx]} \t Deviation: {deviation}')

 

 

▶ 코드 : rankEx.py (실행 파일)

import rankMod as rm
import random

midStuScos = random.sample(range(50, 101), 20)
endStuScos = random.sample(range(50, 101), 20)

rd = rm.RankDeviation(midStuScos, endStuScos)

rd.setMidRank()
print(f'midStuScos: {midStuScos}')
print(f'mid_rank: {rd.getMidRank()}')

rd.setEndRank()
print(f'endStuScos: {endStuScos}')
print(f'end_rank: {rd.getEndRank()}')

rd.printRankDeviation()

[출력 결과]

랜덤 실행 결과임

midStuScos: [76, 59, 92, 61, 67, 65, 75, 90, 74, 69, 85, 82, 63, 66, 79, 83, 95, 64, 58, 71]
mid_rank: [6, 18, 1, 16, 10, 12, 7, 2, 8, 9, 4, 5, 14, 11, 3, 4, 0, 13, 19, 9]
endStuScos: [67, 100, 58, 91, 70, 94, 65, 88, 98, 71, 61, 72, 63, 62, 66, 73, 78, 75, 64, 60]
end_rank: [12, 0, 19, 4, 10, 2, 13, 6, 1, 9, 17, 8, 14, 16, 11, 7, 5, 8, 15, 18]
mid_rank: 6 	 end_rank: 12 	 Deviation: ↓6
mid_rank: 18 	 end_rank: 0 	 Deviation: ↑18
mid_rank: 1 	 end_rank: 19 	 Deviation: ↓18
...

 

[07_버블 정렬]

▶ 버블 정렬이란?

이웃한 값을 비교하여 큰 값을 끝으로 밀어내는 정렬을 말한다.

 

리스트의 처음부터 끝가지 인접한 두 값을 비교해서

더 큰 값을 오른쪽(끝)으로 이동시키는 정렬 방법이다.

이 과정을 리스트 길이만큼 반복하면, 큰 값들이 점점 뒤로 모여

마치 거품이 위로 올라오는 것처럼 정렬이 완성되기에 '버블 정렬'이라 부른다.

 

▶ 코드 : 내부 동작을 출력하며 정렬

nums = [10, 2, 7, 21, 0]

length = len(nums) - 1
for i in range(length):
    for j in range(length - i):
        if nums[j] > nums[j + 1]:
            # 값 교환 (swap)
            temp = nums[j]
            nums[j] = nums[j + 1]
            nums[j + 1] = temp
        print(nums)  # 내부 단계 출력
    print()

print(f'sorted nums: {nums}')

[출력 결과]

[2, 10, 7, 0, 21]
[2, 7, 10, 0, 21]
[2, 7, 0, 10, 21]
[2, 7, 0, 10, 21]

[2, 7, 0, 10, 21]
[2, 0, 7, 10, 21]
[2, 0, 7, 10, 21]

...
sorted nums: [0, 2, 7, 10, 21]

 

 

▶ 코드 : 함수화 및 원본 유지

import copy

def bubbleSort(ns):
    cns = copy.copy(ns)
    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j + 1]:
                cns[j], cns[j + 1] = cns[j + 1], cns[j]
    return cns

nums = [10, 2, 7, 21, 0]
sortedNums = bubbleSort(nums)

print(f'nums: {nums}')
print(f'sortedNums: {sortedNums}')

[출력 결과]

nums: [10, 2, 7, 21, 0]
sortedNums: [0, 2, 7, 10, 21]

 

[08_버블 정렬(실습)]

▶ 실습 문제

 

 

▶ 코드 : sortMod.py (모듈 파일)

import copy

def bubbleSort(ns, deepCopy=True):
    if deepCopy:
        cns = copy.copy(ns)  # 원본 보호
    else:
        cns = ns  # 얕은 복사 (원본이 바뀜)

    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j + 1]:
                cns[j], cns[j + 1] = cns[j + 1], cns[j]

    return cns

 

 

▶ 코드 : bubbleEx.py (실행 파일)

import sortMod as sm
import random as rd

students = []

for i in range(20):
    students.append(rd.randint(170, 185))

print(f'students: {students}')
print(f'students length: {len(students)}')

# 깊은 복사
sortedStudents = sm.bubbleSort(students)
print(f'students: {students}')
print(f'sortedStudents: {sortedStudents}')

deepCopy=False 옵션으로 얕은 복사도 가능함. 기본값은 True로 깊은 복사

[출력 결과]

students: [175, 183, 172, 170, 185, 179, 174, 171, 176, 180, 178, 173, 181, 182, 170, 177, 175, 174, 171, 172]
students length: 20
students: [175, 183, 172, 170, 185, 179, 174, 171, 176, 180, 178, 173, 181, 182, 170, 177, 175, 174, 171, 172]
sortedStudents: [170, 170, 171, 171, 172, 172, 173, 174, 174, 175, 175, 176, 177, 178, 179, 180, 181, 182, 183, 185]

 

[09_삽입 정렬]

▶ 삽입 정렬이란?

앞쪽은 이미 정렬되어 있다고 보고, 새로운 값을 끼워 넣는 방식을 말한다.

 

맨 처음 하나의 숫자는 정렬되어 있다고 가정하고

그다음 숫자부터 시작해서, 앞의 정렬된 부분에 들어갈 위치를 찾아 삽입한다.

이 과정을 리스트 끝까지 반복하면서 정렬을 완성한다.

 

 

▶ 코드 : sortMod.py (삽입 정렬 모듈)

def sortNumber(ns, asc=True):

    if asc:
        for i1 in range(1, len(ns)):
            i2 = i1 - 1
            cNum = ns[i1]

            while i2 >= 0 and ns[i2] > cNum:
                ns[i2 + 1] = ns[i2]
                i2 -= 1

            ns[i2 + 1] = cNum

    else:
        for i1 in range(1, len(ns)):
            i2 = i1 - 1
            cNum = ns[i1]

            while i2 >= 0 and ns[i2] < cNum:
                ns[i2 + 1] = ns[i2]
                i2 -= 1

            ns[i2 + 1] = cNum

    return ns

while 조건 순서 주의해야 함. i2 >= 0 먼저 검사해야 index error 방지

작은 데이터에 적합하고 안정 정렬이라 일부 상황에서 유리함

시간복잡도는 평균 O(n²)이지만, 거의 정렬된 경우에는 빠름

 

 

▶ 코드 : insertSort.py (실행 파일)

import sortMod as sm

nums = [5, 10, 2, 1, 0]

# sortNumber() 함수는 기본 asc=True (오름차순)
result = sm.sortNumber(nums, asc=False)  # asc=True 로 바꾸면 오름차순 정렬
print(f'result: {result}')

[출력 결과 (오름차순 기준)]

nums = [5, 10, 2, 1, 0]
→ result: [0, 1, 2, 5, 10]

[출력 결과 (내림차순 기준)]

nums = [5, 10, 2, 1, 0]
→ result: [10, 5, 2, 1, 0]

 

[10_삽입 정렬(실습)]

▶ 실습 문제

 

 

▶ 코드 : sortMod.py (클래스 정의 파일)

class SortNumbers:

    def __init__(self, ns, asc=True):
        self.nums = ns
        self.isAsc = asc

    def isAscending(self, flag):
        self.isAsc = flag

    def setSort(self):
        for i1 in range(1, len(self.nums)):
            i2 = i1 - 1
            cNum = self.nums[i1]

            if self.isAsc:
                while i2 >= 0 and self.nums[i2] > cNum:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1
            else:
                while i2 >= 0 and self.nums[i2] < cNum:
                    self.nums[i2 + 1] = self.nums[i2]
                    i2 -= 1

            self.nums[i2 + 1] = cNum

    def getSortedNumbers(self):
        return self.nums

    def getMinNumber(self):
        return self.nums[0] if self.isAsc else self.nums[-1]

    def getMaxNumber(self):
        return self.nums[-1] if self.isAsc else self.nums[0]

 

 

▶ 코드 : insertSortEx.py (실행 파일)

import random
import sortMod as sm

nums = random.sample(range(1, 1000), 100)
print(f'not sortedNumber: {nums}')

# 객체 생성
sn = sm.SortNumbers(nums)

# 오름차순 정렬
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by ASC: {sortedNumber}')

# 내림차순 정렬
sn.isAscending(False)
sn.setSort()
sortedNumber = sn.getSortedNumbers()
print(f'sortedNumber by DESC: {sortedNumber}')

# 최소값 / 최대값
print(f'MinNumber : {sn.getMinNumber()}')
print(f'MaxNumber : {sn.getMaxNumber()}')

[출력 결과]

not sortedNumber: [931, 598, 831, ..., 45]
sortedNumber by ASC: [4, 12, 17, ..., 994]
sortedNumber by DESC: [994, 989, ..., 4]
MinNumber : 4
MaxNumber : 994

 

 

 

[11_선택 정렬]

▶ 선택 정렬이란?

가장 작은 값을 선택해서 앞으로 보내는 정렬 방법을 말한다.

 

리스트 전체 중에서 가장 작은 값을 찾아서 맨 앞과 교환

그다음 인덱스부터 반복하여, 또 가장 작은 값을 찾아 앞으로 보냄

리스트의 끝까지 이 과정을 반복함

 

 

▶ 코드

nums = [4, 2, 5, 1, 3]

for i in range(len(nums)-1):
    minIdx = i  # 현재 기준 인덱스를 최소값 인덱스로 설정

    for j in range(i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j  # 더 작은 값 발견 시 minIdx 갱신

    # 현재 위치 i와 가장 작은 값 위치 minIdx를 교환
    tempNum = nums[i]
    nums[i] = nums[minIdx]
    nums[minIdx] = tempNum

    # 파이썬 방식으로는 아래처럼 교환 가능
    # nums[i], nums[minIdx] = nums[minIdx], nums[i]

print(f'nums: {nums}')

구조가 단순하고 직관적이지만, 비교 횟수가 많고 비효율적임(시간복잡도 O(n²))

제자리 정렬이며 안정 정렬은 아님

[출력 결과]

nums: [1, 2, 3, 4, 5]

 

[12_선택 정렬(실습)]

▶ 실습 문제

 

 

▶ 코드 : sortMod.py (선택 정렬 함수)

def sortNumber(ns, asc=True):
    cnt = 0  # 비교 횟수 카운트

    for i in range(len(ns) - 1):
        targetIdx = i

        for j in range(i + 1, len(ns)):
            if asc:
                if ns[targetIdx] > ns[j]:
                    targetIdx = j
                    cnt += 1
            else:
                if ns[targetIdx] < ns[j]:
                    targetIdx = j
                    cnt += 1

        ns[i], ns[targetIdx] = ns[targetIdx], ns[i]

    print(f'cnt: {cnt}')  # 비교 횟수 출력
    return ns

asc는 ascending(오름차순)의 약자

sortNumber() 함수의 매개변수 중 asc = True 또는 asc = False로 설정해서 정렬 방향을 선택할 수 있음

True 하면 오름차순 정렬

False 하면 내림차순 정렬

 

파이썬에서 리스트는 가변 객체임

함수에 리스트를 전달하면 원본 리스트 자체가 수정될 수 있음

해결 방법으로 copy.deepcopy()를 사용해서 리스트의 완전히 독립적인 복사본을 만들 수 있음

만든 복사본에 정렬 작업을 하면 원본 리스트는 안전하게 유지됨

 

 

▶ 코드 : selectionSortEx.py (실행 파일)

import random
import sortMod as sm
import copy

scores = random.sample(range(50, 101), 20)
print(f'scores: {scores}')
print(f'scores length: {len(scores)}')

# 오름차순 정렬 (깊은 복사하여 원본 유지)
result = sm.sortNumber(copy.deepcopy(scores))
print(f'result(ASC): {result}')

# 내림차순 정렬 (깊은 복사하여 원본 유지)
result = sm.sortNumber(copy.deepcopy(scores), asc=False)
print(f'result(DESC): {result}')

[출력 결과]

scores: [65, 83, 61, 75, 99, 58, 70, 78, 96, 66, 63, 81, 71, 100, 88, 86, 84, 91, 93, 52]
scores length: 20
cnt: 55
result(ASC): [52, 58, 61, 63, 65, 66, 70, 71, 75, 78, 81, 83, 84, 86, 88, 91, 93, 96, 99, 100]
cnt: 55
result(DESC): [100, 99, 96, 93, 91, 88, 86, 84, 83, 81, 78, 75, 71, 70, 66, 65, 63, 61, 58, 52]

 

 

 

[나의 생각 정리]

단순한 비교 로직이 반복문을 만나 어떻게 알고리즘이 되는지 알 수 있었다.

정렬 알고리즘을 객체지향적으로 구현했는데, 이러면 유지보수성과 재사용성이 좋은 것 같다.

단순히 코드만 구현할 줄 아는 게 아니라 원리도 설명할 수 있어야 면접에서 살아남을 수 있다.

혼잣말로 설명하면서 정리하는 시간을 계속 가지면 좋을 듯하다.

 

 

[적용점]

면접이나 시험에서 코딩할 때 사용

코테 문제 푸는 데 사용

 

 

 

“이 글은 제로베이스 데이터 스쿨 주 3일반 강의 자료 일부를 발췌하여 작성되었습니다.”