• 검색 결과가 없습니다.

Y. Daniel Liang 길준민 · 정재화

N/A
N/A
Protected

Academic year: 2022

Share "Y. Daniel Liang 길준민 · 정재화"

Copied!
58
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(1)

ISBN 978-89-7050-850-4 978-0-13-274718-9

Y. Daniel Liang 길준민 · 정재화

(2)

Chapter 10

리스트

(3)

10.1 들어가기

10.2 리스트 기초

10.3 사례연구: 로또 번호 생성기

10.4 사례연구: 카드팩

10.5 카드팩 GUI

10.6 리스트 복사하기

10.7 함수에 리스트 전달하기

10.8 함수에서 리스트 반환하기

10.9 사례 연구: 문자 빈도수 세기

10.10 리스트 검색하기

10.11 리스트 정렬하기

10.12 사례 연구: 공 튕기기

• 100개의 숫자를 읽어 이들의 평균을 계산하고 이 숫자 중에 평균 이상인 숫자가 얼마나 되는지를 출력한다고 해보자. 어떻게 해결할 것인가?

CONTENTS

학습하기에 앞서

Ch10 리스트

(4)

• 리스트가 프로그래밍에서 왜 유용한지 설명할 수 있다(§10.2).

• 리스트의 생성 방법을 학습한다(§10.2.1).

• 시퀀스(sequence)에 대한 공통 연산을 활용할 수 있다(§10.2.2).

• 리스트에 대해 len, min, max, sum, random.suffle 함수를 사용할 수 있다(§10.2.3).

• 인덱스 변수를 사용하여 리스트 원소에 접근할 수 있다(§10.2.4).

• 슬라이싱 연산자 [start : end]를 사용하여 리스트의 부분 리스트를 얻을 수 있다(§10.2.5).

• 리스트에서 +(연결, concatenation), *(반복, repetition), in/not in 연산자를 사용할 수 있 다(§10.2.6).

• for 루프를 사용하여 리스트의 원소들을 순회할 수 있다(§10.2.7).

• 비교 연산자를 사용하여 두 리스트의 내용을 비교할 수 있다(§10.2.8).

• 리스트 컴프리헨션을 사용하여 리스트를 생성할 수 있다(§10.2.9).

• 리스트의 append, count, extend, index, insert, pop, remove, reverse, sort 메소드를 호출할 수 있다(§10.2.10).

• str의 split 메소드를 사용하여 문자열을 분할하여 리스트로 구성할 수 있다(§10.2.11절).

• 콘솔에서 읽은 데이터로 리스트를 만들 수 있다(§10.2.12).

• 애플리케이션 개발에서 리스트를 활용할 수 있다(§10.3-10.5).

• 리스트의 내용을 다른 리스트로 복사할 수 있다(§10.6).

• 리스트 인자와 반환 리스트를 포함한 함수를 개발하고 호출할 수 있다(§10.7-10.9).

• 선형 검색(§10.10.1)과 이진 검색(§10.10.2)을 사용하여 원소를 검색할 수 있다.

• 선택 정렬을 사용하여 리스트의 원소들을 정렬할 수 있다(§10.11.1).

• 삽입 정렬을 사용하여 리스트의 원소들을 정렬할 수 있다(§10.11.2).

학습목표

(5)

• list 클래스의 생성자를 이용하여 리스트를 생성

• 간결한 문법을 사용하여 다음과 같이 리스트를 생성할 수 있다.

리스트 생성하기

list1 = list() # 빈 리스트를 생성한다.

list2 = list([2, 3, 4]) # 원소 2, 3, 4를 가진 리스트를 생성한다.

list3 = list(["red", "green", "blue"]) # 문자열을 가진 리스트를 생성한다.

list4 = list(range(3, 6)) # 원소 3, 4, 5를 가진 리스트를 생성한다.

list5 = list( "abcd") # 문자 a, b, c, d를 가진 리스트를 생성한다.

list1 = [] # list() 와 동일하다.

list2 = [2, 3, 4] # list([2, 3, 4]) 와 동일하다.

list3 = ["red", "green"] # list(["red", "green"]) 와 동일하다.

(6)

리스트 메소드

Add an item x to the end of the list.

Insert an item x at a given index. Note that the first element in the list has index 0.

Remove the first occurrence of the item x from the list.

Return the index of the item x in the list.

Return the number of times item x appears in the list.

Sort the items in the list.

Reverse the items in the list.

Append all the items in L to the list.

Remove the item at the given position and return it. The square bracket denotes that parameter is optional. If no index is specified, list.pop() removes and returns the last item in the list.

  TV

append(x: object): None

insert(index: int, x: object): None remove(x: object): None

index(x: object): int count(x: object): int sort(): None

reverse(): None

extend(l: list): None

pop([i]): object

(7)

리스트를 위한 함수

>>> list1 = [2, 3, 4, 1, 32]

>>> len(list1) 5

>>> max(list1) 32

>>> min(list1) 1

>>> sum(list1) 42

>>> import random

>>> random.shuffle(list1) # list1 내의 원소들을 뒤섞는다.

>>> list1

(8)

5.6 4.5 3.3 13.2

4.0 34.33

34.0 45.45 99.993

11123

인덱스 연산자 []

myList = [5.6, 4.5, 3.3, 13.2, 4.0, 34.33, 34.0, 45.45, 99.993, 11123]

myList[0]

myList[1]

myList[2]

myList[3]

myList[4]

myList[5]

myList[6]

myList[7]

myList[8]

myList[9]

myList

리스트 참조 변수 참조

인덱스 5인

리스트 원소

(9)

+, *, in/not 연산자

>>> list1 = [2, 3]

>>> list2 = [1, 9]

>>> list3 = list1 + list2

>>> list3 [2, 3, 1, 9]

>>> list3 = 3 * list1

>>> list3

[2, 3, 2, 3, 2, 3]

>>> list4 = list3[2 : 4]

>>> list4

(10)

+, *, in/not 연산자

Python Shell

>>> list1 = [2, 3, 5, 2, 33, 21]

>>> list1[-1]

21

>>> list1[-3]

2

Python Shell

>>> list1 = [2, 3, 5, 2, 33, 21]

>>> 2 in list1 True

>>> list1 = [2, 3, 5, 2, 33, 21]

>>> 2.5 in list1 False

(11)

한 끝 차이 오류

i = 0

while i <= len(lst):

print(lst[i])

i += 1

(12)

• 리스트 컴프리헨션(list comprehension)은 리스트의 순차 원소를 생성할 수 있는 간편한 방법을 제공한다.

• 꺽쇠괄호 안에 표현식을 먼저 작성하고 그 다음에 for 절을 넣고, 그 이후로 for 나 if 절을 넣거나 생략하는 형태로 리스트 컴프리헨션을 구성할 수 있다. 리스 트 컴프리헨션은 표현식의 결과에 따라 리스트를 만든다.

• 다음의 예를 살펴보자.

리스트 컴프리헨션

Python Shell

>>> list1 = [x for x range(0, 5)] # 0, 1, 2, 4의 리스트를 반환한다.

>>> list1 [0, 1, 2, 3, 4]

>>> list2 = [0.5 * x for x in list1]

>>> list2

[0.0, 0.5, 1.0, 1.5, 2.0]

>>> list3 = [x for x in list2 if x < 1.5]

>>> list3

(13)

리스트 비교하기

Python Shell

>>>list1 = ["green", "red", "blue"]

>>>list2 = ["red", "blue", "green"]

>>>list2 == list1 False

>>>list2 != list1 True

>>>list2 >= list1 False

>>>list2 > list1 False

>>>list2 < list1 True

>>>list2 <= list1 True

(14)

문자열을 리스트로 분할하기

items = "Welcome to the Korea".split() print(items)

['Welcome', 'to', 'the', 'Korea']

items = "34#13#78#45".split("#") print(items)

['34', '13', '78', '45']

(15)

• Pick-10 로또의 각 티켓은 1부터 99 사이의 서로 다른 번호를 10개씩 가지고 있다. 여러 장의 티켓을 구매했다고 가정하고, 이들 티켓에 1부터 99까지의 모든 번호가 있기를 바랄 것이다.

• 하나의 파일에서 모든 티켓의 번호를 읽고 1부터 99까지 모든 번호가 있는지 를 판별하는 프로그램을 작성해 보자.

• 파일에서 마지막 번호는 0이라고 가정하고 다음과 같은 번호들을 가지고 있다 고 해보자.

사례 연구: 로또 번호 생성기

LottoNumbers 실행

Lotto Numbers Sample Data

(16)

사례 연구: 로또 번호 생성기

False False False False

. . .

False False

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

True

False False False

. . .

False False

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

isCovered isCovered

False True

False False

. . .

False False

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

isCovered

False False True False

. . .

False False

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

isCovered

False False False False

. . .

False True

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

isCovered

(a) (b) (c) (d) (e)

(17)

• 이 문제는 52장의 카드로 구성된 카드팩에서 4장의 카드를 랜덤하게 뽑는 프 로그램을 작성하는 것이다.

• 모든 카드는 deck 리스트로 표현되며, 다음과 같이 0에서 51까지의 초깃값으 로 채워져 있다.

사례 연구: 카드팩

deck = [x for x in range(0, 52)]

(18)

사례 연구: 카드팩

0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51

13 스페이드(♠)

13 하트(♥)

13 다이아몬드( )

13 클로버(♣)

0 . . . 12 13 . . . 25 26 . . . 38 39 . . . 51

카드팩

[0]

. . . [12]

[13]

. . . [25]

[26]

. . . [38]

[39]

. . . [51]

랜덤 섞기

6 48

11 24 . . . . . . . . . . . . . . . .

카드팩

[0]

[1]

[2]

[3]

[4]

[5]

. . . [25]

[26]

. . . [38]

[39]

. . . [51]

카드 번호 6은

스페이드 (7 // 13 = 0) 7 (6 % 13 = 6) 입니다.

카드 번호 48은

클로버 (48 // 13 = 3) 10 (48 % 13 = 9)입니다.

카드 번호 11은

스페이드 (11 / /13 = 0) Q(11 % 13 = 11) 입니다.

카드 번호 24는 하트 (24 // 13 = 1)

Q(24 % 13 = 11) 입니다.

(19)

사례 연구: 카드팩

cardNumber / 13 =

0 스페이드

1 하트

2 다이아몬드

3 클로버

cardNumber % 13

=

0 A

1 2

. .

10 J

11 Q

12 K

(20)

카드팩 GUI

DeckOfCardsGUI 실행

(21)

• 프로그램에서 리스트 전체 또는 그 일부를 중복하여 복사할 필요가 종종 있다.

이러한 경우, 다음과 같이 할당 명령문(=)을 사용하여 시도할 수 있다.

리스트 복사하기

list2 = list1

list2 = list1 의 수행 전

list1

list2

list1의 내용

list1

list2

list2 = list1 의 수행 후

list2 내용

list1의 내용

list2 쓰레기 내용

(22)

함수에 리스트 전달하기

함수 호출

lst = [3, 1, 2, 6, 4, 2]

printList(lst)

함수 호출

printList([3, 1, 2, 6, 4, 2])

무명 리스트

def printList(lst):

for element in lst:

print(element)

(23)

• 파이썬은 값에의한 전달 방식을 사용하여 인자를 함수에 전달한다.

• 값에 의한 전달 방식을 사용하는 경우 숫자, 문자의 값을 전달하는 것과 리스 트를 전달하는 것에 큰 차이점이 있다.

• 변경불가능 객체

• 변경가능 객체

값에 의한 전달

(24)

• 숫자 또는 문자 인자의 경우, 파이썬에서 숫자와 문자는 변경불가능이기 때문 에, 원본 값은 함수의 내부에서 변경되지 않는다.

값에 의한 전달(변경불가능 객체)

(25)

• 인자가 리스트인 경우, 인자의 값은 리스트의 레퍼런스이기 때문에 레퍼런스 값이 전달된다.

• 의미적으로는 공유 값에 의한 전달이 가장 정확한 표현이다. 즉 함수 내부의 리스트는 실제가 전달되는 것과 마찬가지이다.

• 따라서 함수 내부에서 리스트의 값을 변경하면 함수 외부에서도 변경된 값을 볼 수 있다.

값에 의한 전달(변경가능 객체)

(26)

값에 의한 전달 예제

def main():

x = 1 # x는 int 변수이다.

y = [1, 2, 3] # y는 리스트이다.

m(x, y) # x, y 인자를 사용하여 m을 호출한다.

print("x는", x, "입니다.") print("y[0]은, y[0], "입니다.")

def m(number, numbers):

number = 1001 # number에 새로운 값을 할당한다.

numbers[0] = 5555 # numbers[0]에 새로운 값을 할당한다.

main() # main 함수를 호출한다.

(27)

고려사항

출력결과

def add(x, lst = []):

if not(x in lst):

lst.append(x) return lst

list1 = add(1) print(list1) list2 = add(2) print(list2)

list3 = add(3, [11, 12, 13, 14]) print(list3)

list4 = add(4) print(list4)

[1]

[1, 2]

[11, 12, 13, 14]

[1, 2, 4]

• 기본값은 단 한 번만 생성된다.

주의

(28)

• list 클래스에는 리스트의 원소들을 역순으로 만들어 주는 reverse() 메소드를 갖고 있음에 주목하자.

• list.reverse()

함수에서 리스트 반환하기

list1 = [1, 2, 3, 4, 5, 6]

list2 = reverse(list1)

def reverse(list):

result = []

 

for element in list:

result.insert(0, element)  

return result

list

result

(29)

• 100개의 소문자를 랜덤하게 생성하고 이들 문자를 chars라 하는 문자 리스트 에 할당한다.

• chars 리스트에 있는 각 문자의 개수를 센다.

사례 연구: 문자 빈도수 세기

Chars[0]

Chars[1]

Chars[98]

Chars[99]

Chars[0]

Chars[1]

Chars[24]

Chars[25]

(30)

• 검색(searching) 이란 리스트에서 특정 원소를 찾는 과정이다. 즉, 점수 리스 트에 원하는 점수가 있는지를 찾는 것이 하나의 예이다.

• 검색은 컴퓨터 프로그래밍에서 흔한 작업이며, 많은 알고리즘들이 검색을 위 해 개발되어 왔다. 이 절에서는 가장 일반적인 두 가지 검색 방법으로 선형 검 색(linear search)과 이진 검색(binary search)에 대해서 살펴본다.

리스트 검색하기

#리스트에서 key를 찾는 함수

def linearSearch(lst, key):

for i in range(0, len(lst)):

if key == lst[i]:

return i

return -1

lst

[0] [1] [2]

key i = 0, 1, …에 대해 lst[i]와 key를 비교한다.

(31)

• 선형 검색(linear search)은 키 원소 key와 리스트의 각 원소를 순차적으로 비교한다.

• 키와 일치하는 원소를 리스트에서 찾을 때까지 혹은 발견된 원소 없이 리스트 의 모든 원소를 전부 비교할 때까지 반복된다.

• 일치하는 원소를 찾으면, 선형 검색은 이 원소의 인덱스를 반환한다. 만일, 찾 지 못하면 –1을 반환한다.

선형 검색 방식

(32)

선형 검색 알고리즘

6 4 1 9 7 3 2 8

6 4 1 9 7 3 2 8

6 4 1 9 7 3 2 8

6 4 1 9 7 3 2 8

6 4 1 9 7 3 2 8

6 4 1 9 7 3 2 8

3

3

3

3

3

3

키 리스트

(33)

선형 검색 애니메이션

실행

(34)

• 이진 검색을 수행하기 위해서는 리스트의 원소들이 먼저 정렬되어 있어야 한 다. 리스트가 오름차순으로 정렬되어 있다고 가정해 보자. e.g., 2 4 7 10 11 45 50 59 60 66 69 70 79

• 이진 검색은 우선 리스트의 중간 원소와 키를 비교한다.

이진 검색

(35)

• 다음과 같이 3가지 경우를 고려해 볼 수 있다

• 키가 리스트의 중간 원소보다 작으면, 리스트의 첫 번째 절반(즉, 중앙에서 왼쪽 부분)만을 대 상으로 키 검색을 해야 한다

• 키가 리스트의 중간 원소와 같으면, 일치한 것이므로 검색을 마친다.

• 키가 리스트의 중간 원소보다 크다면, 리스트의 두 번째 절반(즉, 중앙에서 오른쪽 부분)만을 대상으로 키 검색을 해야 한다

이진 검색

(36)

이진 검색

1 2 3 4 6 7 8 9

1 2 3 4 6 7 8 9

1 2 3 4 6 7 8 9

8

8

8

키 리스트

(37)

이진 검색 애니메이션

실행

(38)

이진 검색

lst Key = 11

 

 

 

2 4 7 10 11 45 50 59 60 66 69 70 79

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

low mid high

lst 2 4 7 10 11 45

[0] [1] [2] [3] [4] [5]

low mid high

lst 10 11 45

[3] [4] [5]

low mid high

(39)

이진 검색

lst Key = 54

 

 

 

2 4 7 10 11 45 50 59 60 66 69 70 79

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

low mid high

lst 59 60 66 69 70 79

[7] [8] [9] [10] [11] [12]

low mid high

lst 59 60

[7] [8]

low mid high

low high

(40)

• 이진검색 메소드는 원소가 리스트에 있으면, 그 원소의 인덱스를 반환한다. 만 약 그렇지 않다면 다음을 반환한다.

• 삽입 위치: -low - 1

• 삽입 위치는 키가 리스트에 삽입되어야 할 위치를 나타낸다.

이진 검색

(41)

해결 방법

# 리스트에서 키를 찾기 위해 이진 검색을 사용한다.

def binarySearch(lst, key):

low = 0

high = len(lst) - 1

while high >= low:

mid = (low + high) // 2 if key < lst[mid]:

high = mid - 1 elif key == lst[mid]:

return mid else:

low = mid + 1

return –low - 1 # 현재 high < low이므로, 키는 발견되지 않음  

(42)

• 검색과 마찬가지로 정렬도 컴퓨터 프로그래밍에서 흔한 작업이다. 정렬을 위 한 다양한 알고리즘이 개발되어 왔다.

• 이 절에서는 간단하고 직관적인 두 가지 알고리즘으로 선택 정렬(selection sorting) 과 삽입 정렬(insert sorting)을 살펴본다.

리스트 정렬하기

(43)

• 선택 정렬은 리스트 내에서 가장 작은 원소를 찾고 그것을 첫 번째 원소와 교 환한다. 그런 다음, 남은 원소 중에 가장 작은 원소를 찾고 그것을 남은 원소들 중에 첫 번째 원소와 교환한다. 이러한 과정은 한 개의 원소가 남을 때까지 반 복한다.

• 아래의 그림은 선택 정렬을 사용할 때 리스트 {2, 9, 5, 4, 8, 1, 6}의 정렬 과 정을 보여준다.

2 9 5 4 8 1 6

선택 정렬

리스트에서 1(가장 작은)을 선택하고 2(첫 번째에 위치한)와 교환한다.

남은 리스트에서 2(가장 작은)를 9(첫 번 째)와 교환한다.

숫자 1은 현재 정확한 위치에 놓여있기 때 문에 더 이상 고려될 필요가 없다.

교환

1 9 5 4 8 2 6

교환

교환

(44)

선택 정렬

숫자 4는 현재 정확한 위치에 놓여있기 때 문에 더 이상 고려될 필요가 없다.

숫자 5는 현재 정확한 위치에 놓여있기 때 문에 더 이상 고려될 필요가 없다.

숫자 6은 현재 정확한 위치에 놓여있기 때 문에 더 이상 고려될 필요가 없다.

숫자 8은 현재 정확한 위치에 놓여있기 때 문에 더 이상 고려될 필요가 없다.

5는 가장 작고 올바른 위치에 놓 여 있다. 교환은 필요없다.

 

남은 리스트에서 6(가장 작은)을 8(첫 번째)과 교환한다.

남은 리스트에서 8(가장 작은)을 9(첫 번째)와 교환한다.

남은 리스트에 원소가 한 개밖에 없 으므로 정렬이 완료된다.

1 2 4 5 8 9 6

1 2 4 5 8 9 6

교환

1 2 4 5 6 9 8

교환

1 2 4 5 6 8 9

(45)

선택 정렬 애니메이션

실행

(46)

해결방법

for i in range(0, len(lst)):

lst[i : len(lst)] 내에서 가작 작은 원소를 선택한다.

필요하다면, 가작 작은 원소를 lst[i]와 교환한다.

# lst[i]는 정확한 위치에 놓이게 된다.

# 다음 반복은 lst[i+1: len(lst)]을 대상으로 적용한다.

lst[0] lst[1] lst[2] lst[3] Lst[10]

lst[0] lst[1] lst[2] lst[3] Lst[10]

lst[0] lst[1] lst[2] lst[3] Lst[10]

lst[0] lst[1] lst[2] lst[3] Lst[10]

lst[0] lst[1] lst[2] lst[3] Lst[10]

lst[0] lst[1] lst[2] lst[3] Lst[10]

(47)

currentMin = lst[i]

currentMinIndex = i

for j in range(i + 1, len(lst)):

if currentMin > lst[j]:

for i in range(0, len(lst)):

lst[i : len(lst)] 내에서 가장 작은 원소를 선택한다.

필요하다면, 가장 작은 원소를 lst[i]와 교환한다.

# lst[i]는 정확한 위치에 놓이게 된다.

# 다음 반복은 lst[i+1: len(lst)]을 대상으로 적용한다.

파이썬 코드로 확장

(48)

# lst[i..len(lst)-1]에서 가장 작은 원소를 찾는다.

currentMin = lst[i]

currentMinIndex = i

for j in range(i + 1, len(lst)):

if currentMin > lst[j]:

currentMin = lst[j]

currentMinIndex = j

# 필요하다면, lst[currentMinIndex]를 lst[i]와 교환한다.

if currentMinIndex != i:

lst[currentMinIndex] = lst[i]

lst[i] = currentMin

파이썬 코드로 확장

for i in range(0, len(lst)):

lst[i : len(lst)] 내에서 가장 작은 원소를 선택한다.

필요하다면, 가장 작은 원소를 lst[i]와 교환한다.

# lst[i]는 정확한 위치에 놓이게 된다.

# 다음 반복은 lst[i+1: len(lst)]을 대상으로 적용한다.

(49)

# 이 함수는 숫자를 정렬한다.

def selectionSort(lst):

for i in range(0, len(lst) - 1):

# lst[i..len(lst)]에서 가장 작은 원소를 찾는다.

currentMin = lst[i]

currentMinIndex = i

for j in range(i + 1, len(lst)):

if currentMin > lst[j]:

currentMin = lst[j]

currentMinIndex = j

# 필요한 경우, lst[i] 와 lst[currentMinIndex]를 교환한다.

if currentMinIndex != i:

lst[currentMinIndex] = lst[i]

lst[i] = currentMin

함수로 변환

selectionSort(yourList)를 호출한다.

(50)

• 삽입 정렬 알고리즘은 새로운 원소를 정렬된 부분 리스트에 삽입하는 과정을 전체 리스트가 정렬될 때까지 반복함으로써 리스트를 정렬한다.

삽입 정렬

myList = [2, 9, 5, 4, 8, 1, 6] # 정렬 전

단계 1: 초기에 정렬된 부분 리스트는 리스트의 첫 번째 원소를 갖고 있다. 9를 이 부분 리스트에 삽입한다.

단계 2: 정렬된 부분 리스트는 [2, 9]이다. 5를 이 부분 리 스트에 삽입한다.

단계 3: 정렬된 부분 리스트는 [2, 5, 9]이다. 4를 이 부분 리스트에 삽입한다.

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 5 9 4 8 1 6

(51)

삽입 정렬

단계 4: 정렬된 부분 리스트는 [2, 4, 5, 9]이다. 8을 이 부분 리스트에 삽입한다.

단계 5: 정렬된 부분 리스트는 [2, 4, 5, 8, 9]이다. 1을 이 부분 리스트에 삽입한다.

2 4 5 9 8 1 6

2 4 5 8 9 1 6

단계 6: 정렬된 부분 리스트는 [1, 2, 4, 5, 8, 9]이다. 1

을 이 부분 리스트에 삽입한다.

1 2 4 5 8 9 6

단계 7: 전체 리스트가 이제 정렬되었다.

2 5 9 4 8 1 6

(52)

삽입 정렬 애니메이션

실행

(53)

삽입 정렬

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 9 5 4 8 1 6

2 9 5 4 8 1 6

myList = [2, 9, 5, 4, 8, 1, 6] # 정렬 전

(54)

• 삽입 정렬 알고리즘은 새로운 원소를 정렬된 부분 리스트에 삽입하는 과정을 전체 리스트가 정렬될 때까지 반복함으로써 리스트를 정렬한다.

어떻게 삽입할 것인가?

[0] [1] [2] [3] [4] [5] [6]

list

list

list

단계 1: 4를 임시 변수인 currentElement에 저장한다.

currentElement: 4

2 5 9 4

단계 2: lst[2]를 lst[3]으로 이동시킨다.

단계 3: lst[1]을 lst[2]로 이동시킨다.

[0] [1] [2] [3] [4] [5] [6]

2 5 9

[0] [1] [2] [3] [4] [5] [6]

2 5 9

[0] [1] [2] [3] [4] [5] [6]

2 4 5 9

(55)

해결 방법

for i in range(1, len(lst)):

정렬된 부분 리스트 lst[0..i-1]에 lst[i]를 삽입하여 lst[0..i]를 정렬한다.

lst[0]

lst[0] lst[1]

lst[0] lst[1] lst[2]

lst[0] lst[1] lst[3]

lst[0] lst[1] lst[3] ...

(56)

해결 방법

확장

k = i - 1

while k >= 0 and lst[k] > currentElement:

lst[k + 1] = lst[k]

k -= 1

# 현재 원소를 lst[k + 1]에 삽입한다.

lst[k + 1] = currentElement

InsertSort

for i in range(1, len(lst)):

정렬된 부분 리스트 lst[0..i-1]에 lst[i]를 삽입하여 lst[0..i]를 정렬한다.

(57)

사례 연구: 공 튕기기

Ball x: int y: int dx: int dy: int

color: Color radius: int

공 중심에 대한 x, y 좌표 기본값은 (0, 0)

dx와 dy는 (x, y)에 대한 증가값

공의 색상 공의 반지름

BouncingBalls 실행

(58)

ISBN 978-89-7050-850-4 978-0-13-274718-9

감사합니다.

참조

관련 문서

• 다른 프로그램을 위해 설계된 클래스를 사용할 때, 데이터가 부정하게 수정되는 것 을 방지하고 클래스의 관리를 용이하게 만들기 위해 데이터 필드를 private로

• 파이썬은 연산자와 동일한 결과를 산출하는 함수로서 특수 메소드의 정의를 허용한다.이 메소드들은 파이썬이 인식할 수 있도록 특별한

• 하향식 접근 방식은 위에서부터 아래로 구조 차트에 있는 함수 하나씩을 차례대로 구 현해 가는 방식이다. 간단하지만 불완전한 함수인 스텁(stub)을 사용하여 함수를

case의 비교 값과 일치하는 것이 없으면 default 문 실행. default

이것이 방사능에 대해 알려진 많은 사실을 설명하는 데 러더퍼드와 소디가 제안한 모형이다 그들은. 방사능 원소를 세 가지의 주된 가족으로 분류할 수 있음을 입증했는데

반면 원시가 있는 사람은 평소 플러스 디옵터의 안경을 착용 하고 있으며 근거리 작업 시 플러스 디옵터가 더 필요하게 되어 노안 증 상을 더욱 빨리 느끼게 되는

- 대리인으로 하여금 효율적인 자원배분을 유도하기 위해서는 주인은 대리인에 게 수평적 등이윤곡선과 일치하는

-반달첨판이 단힌 위부터 방실판막이 열릴 때까지 모든 판막이 닫힌 상태에서 부피는 변화 없이 심실 이와에 의해 심실압이 감소하기 시 작하는 시기.