Im heedy

06-6 퀵 정렬 퀵 정렬 알아보기 퀵 정렬(quick sort): 가장 빠른 정렬 알고리즘 위 그림은 퀵 정렬 알고리즘을 사용하여 학생 그룹을 키 순서로 정렬하는 과정을 나타냈습니다. 먼저 키가 168cm인 학생 A를 선택하여 이 학생을 기준으로 168cm 미만인 그룹과 168cm 이상인 그룹으로 나눕니다. 이때 그룹을 나누는 기준(학생 A의 키)을 피벗(pivot)이라고 합니다. [피벗은 다른 말로 중심축이라고 합니다. 피벗은 임의로 선택할 수 있고, 선택된 피벗은 2개로 나눈 그룹 어디에 넣어도 상관없습니다.] 다시 각 그룹에서 피벗을 선택하여 나누기를 반복하며 모든 그룹이 1명씩 남으면 정렬이 완료됩니다. 배열을 두 그룹으로 나누기 먼저 피벗을 x, 왼쪽 끝 원소의 인덱스를 pl(왼쪽 커서), 오..

06-5 셸 정렬 단순 삽입 정렬의 특징 장점: 이미 정렬을 마쳤거나 정렬이 거의 끝나가는 상태에서는 속도가 아주 빠릅니다. 단점: 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아집니다. 셸 정렬 알아보기 셸 정렬(shell sort): 단순 삽입 정렬의 장점은 살리고 단점은 보완하여 더 빠르게 정렬하는 알고리즘 셸 정렬은 단순 삽입 정렬의 장점을 살리고 단점을 보완하기 위해 사용합니다. 정렬 횟수는 늘어나지만 전체적으로 원소의 이동 횟수가 줄어들어 효율적입니다. 실습 6-8 셸 정렬 알고리즘 구현하기 # 셸 정렬 알고리즘 구현하기 from typing import MutableSequence def shell_sort(a: MutableSequence) -> None: """셸 정렬""" n = l..

06-4 단순 삽입 정렬 단순 삽입 정렬 알아보기 단순 삽입 정렬(straight insertion sort): 주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘 단순 선택 정렬과 비슷해 보이지만 값이 가장 작은 원소를 선택하지 않는다는 점이 다릅니다. 정렬된 부분과 아직 정렬되지 않은 부분에서 다시 배열을 구성할 경우에는 다음 작업을 n - 1번 반복하면 정렬이 완료됩니다. 아직 정렬되지 않은 부분의 맨 앞 원소를 정렬된 부분의 알맞은 위치에 삽입합니다. 단순 삽입 정렬의 알고리즘 개요는 다음과 같습니다. for i in range(1, n): tmp ← a[i]를 넣습니다. tmp를 a[0], ···, a[i -1]의 알맞은 위치에 삽입합니다. 위 그림에서 반복 제어 변수 j에 i..

06-3 단순 선택 정렬 단순 선택 정렬 알아보기 단순 선택 정렬(straight selection sort): 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘 단순 선택 정렬에서 교환 과정은 다음과 같습니다. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택합니다. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환합니다. 이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 정체 정렬을 완료합니다. 이 알고리즘의 개요는 다음과 같습니다. for i in range(n - 1): min# a[i], ···, a[n-1]에서 키값이 가장 작은 원소의 인덱스 a[i]와 a[min]의 값을 교환합니다. 실습 6-6 단순 선택 ..

06-2 버블 정렬 버블 정렬(bubble sort): 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 합니다. 버블 정렬 알아보기 위 그림은 이웃한 원소를 비교하고, 필요하면 교환하는 전체 작업 과정입니다. 이때 원소 수가 n인 배열에서 n -1번 비교·교환을 하면 가장 작은 원소 1이 맨 앞으로 이동합니다. 이러한 일련의 비교·교환하는 과정을 패스(pass)라고 합니다. 버블 정렬 프로그램 실습 6-1 버블 정렬 알고리즘 구현하기 이 프로그램은 n개의 원소 수와 각각의 원솟값을 입력받습니다. i값을 0부터 n - 2까지 1씩 증가시키고, 패스를 n - 1번 수행합니다. # 버블 정렬 알고리즘 구현하기 from typing import Mutab..

06-1 정렬 알고리즘 정렬이란? 정렬(sorting): 이름, 학번, 학점 등의 키(key)를 항목값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘여놓는 작업을 말합니다. 오름차순(ascending order): 값이 작은 데이터를 앞쪽에 늘어놓는 것 내림차순(descending order): 값이 큰 데이터를 앞쪽에 늘어놓는 것 정렬 알고리즘의 안정성 안정적인 알고리즘: 값이 같은 원소의 순서가 정렬한 후에도 유지되는 것 안정적이지 않은 알고리즘: 정렬한 후에도 우너래의 순서가 유지된다는 보장을 할 수 없는 것 내부 정렬과 외부 정렬 내부 정렬(internal sorting): 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘 외부 정렬(external sort..

05-4 8퀸 문제 8퀸 문제 알아보기 8퀸 문제(8-Queen prooblem)는 재귀 알고리즘을 설명할 때 자주 나오는 예제입니다. 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 x 8 체스판에 배치하세요. 분기 작업으로 문제 해결하기 실습 5-7 각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기 # 각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기 pos = [0] * 8 # 각 열에서 퀸의 위치를 출력 def put() -> None: """각 열에 배치한 퀸의 위치를 출력""" for i in range(8): print(f'{pos[i]:2}',end='') print() def set(i: int) -> None: """i열에 퀸을 배치""" for j in range(8): po..

05-3 하노이의 탑 하노이의 탑 알아보기 하노이의 탑(towers of Hanoi): 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작하여 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮기는 문제 원반은 1개씩 옮길 수 있으며 큰 원반은 작은 원반 위에 쌓을 수 없다는 규칙을 지켜야 합니다. [하노이의 탑 알고리즘] [하노이의 탑 문제 풀이] 실습 5-6 하노이의 탑 구현하기 # 하노이의 탑 구현하기 def move(no: int, x: int, y: int) -> None: """원반 no개를 x기둥에서 y기둥으로 옮김""" if no > 1: move(no - 1, x, 6..

05-2 재귀 알고리즘 분석 재귀 알고리즘의 2가지 분석 방법 실습 5-3 순수한 재귀 함수 구현하기 # 순수한 재귀 함수 구현하기 # 순수한(genuinely) 재쉬 -> 재귀 호출을 여러 번 실행하는 함수 def recur(n: int) -> int: """순수한 재귀 함수 recur의 구현""" if n > 0: recur(n - 1) print(n) recur(n - 2) x = int(input('정숫값을 입력하세요.: ')) recur(x) 정숫값을 입력하세요.: 4 1 2 3 1 4 1 2 recur() 함수는 함수 안에서 재귀 호출을 2번 실행합니다. 이처럼 재귀 호출을 여러 번 실행하는 함수를 순수한(genuinely) 재귀라고 하는데 실제 동작은 복잡합니다. 실행 결과처럼 매개변수 n에..

05-1 재귀 알고리즘의 기본 재귀 알아보기 재귀(recursion): 어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 재귀의 예: 자연수의 정의 1은 자연수입니다. 어떤 자연수의 바로 다음 수도 자연수입니다. 팩토리얼 알아보기 팩토리얼(factorial): 양의 정수를 순서대로 곱한다는 의미로 순차 곱셈이라고도 합니다. 재귀를 사용하는 대표적인 예입니다. 양의 정수 n의 패토리얼(n!)은 다음과 같이 정의를 할 수 있습니다. 팩토리얼 n!의 정의(n은 양의 정수) 0! = 1 n > 0이면 n! = n x (n - 1)! 실습 5-1 양의 정수 n의 팩토리얼 구하기 # 양의 정수 n의 팩토리얼 구하기 def factorial(n: int) -> int: """양의 정수 ..