파이썬 – 페이지 8

(모두의 알고리즘) 최대 수익 알고리즘

문제 : 어떤 주식에 대해 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한 번 사고팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요. 주가 테이블 문제 분석과 모델링 주식 거래로 수익을 내는 가장 좋은 방법은 ‘가장 쌀 때 사서 가장 비쌀 때 파는 것’ 얼핏 생각하면… Continue Reading (모두의 알고리즘) 최대 수익 알고리즘

(모두의 알고리즘) 가짜 동전 찾기 알고리즘

문제 : 겉보기에는 똑같은 동전이 n개 있습니다. 이 중에서 한 개는 싸고 가벼운 재료로 만들어진 ‘가짜 동전’입니다. 좌우 무게를 비교할 수 있는 양팔 저울을 이용해서 다른 동전보다 가벼운 가짜 동전을 찾아내는 알고리즘을 만들어 보세요. 문제 분석과 모델링 동전 n개 중에는 무게가 적게 나가는 가짜 동전이 한 개 섞여 있음 무게를 숫자로… Continue Reading (모두의 알고리즘) 가짜 동전 찾기 알고리즘

(모두의 알고리즘) 미로 찾기 알고리즘

미로 찾기 : 출발점에서 도착점까지 가기 위한 최단 경로를 찾는 알고리즘 문제 분석과 모델링 이 문제를 컴퓨터에게 풀어 보라고 하려면 어떻게 해야 할까? 사람에게는 쉽지만 컴퓨터에게 이 문제를 이해하고 풀게 하긴 어려움 이때 필요한 것이 바로 ‘모델링(모형화)’ 모델링이란 주어진 현실의 문제를 정형화하거나 단순화하여 수학이나 컴퓨터 프로그램으로 쉽게 설명할 수 있도록 다시… Continue Reading (모두의 알고리즘) 미로 찾기 알고리즘

(모두의 알고리즘) 친구의 친구 찾기

그래프 꼭짓점(동그라미로 표현) 여러 개와 각 꼭짓점 사이의 연결 관계를 선으로 표현한 것을 그래프라고 함 1부터 6까지 이름이 붙여진 꼭짓점(vertex)이 여섯 개 있고, 그 꼭짓점 사이를 연결하는 선(edge)이 일곱 개 있음 다음 관계를 그래프로 그리면 Summer와 John은 서로 친구입니다. Summer와 Justin은 서로 친구입니다. Summer와 Mike는 서로 친구입니다. Justin과 May는 서로… Continue Reading (모두의 알고리즘) 친구의 친구 찾기

(모두의 알고리즘) 동명이인 찾기

딕셔너리 정의 : 정보를 찾는 기준이 되는 키(key)와 그 키에 연결된 값 (value)의 대응 관계를 저장하는 자료 구조 예1 : 여러 사람이 있을 때 각 사람의 이름(키)과 나이(값)를 대응시켜 딕셔너리로 쉽게 표현할 수 있음

d = {"Justin": 13, "John": 10, "Mike": 9}
>>> d["Justin"]
13
>>> d["John"]
10
>>> d["Summer"]
Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
KeyError: 'Summer'
>>> d["Summer"] = 1

1

2

3

4

5

6

7

8

9

10

d = {"Justin": 13, "John": 10, "Mike": 9}

>>> d["Justin"]

13

>>> d["John"]

10

>>> d["Summer"]

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

KeyError: 'Summer'

>>> d["Summer"] = 1

예2 : 학생의 학번과 이름으로 대응된 학생명부

s_info = {
        1: "김민준",
        2: "이유진",
        3: "박승규"
}

1

2

3

4

5

s_info = {

1: "김민준",

2: "이유진",

3: "박승규"

}

응용 1: 학생 번호 2번에 해당하는 학생… Continue Reading (모두의 알고리즘) 동명이인 찾기

(모두의 알고리즘) 회문 찾기(큐와 스택)

회문(回文; palindrome) 순서대로 읽어도 거꾸로 읽어도 그 내용이 같은 낱말이나 문장 큐 설명 큐(queue)는 ‘줄 서기’에 비유할 수 있음 택시를 타기 위해서 줄을 서는 과정을 떠올려 보자 새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고, 택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시를 탐 가장… Continue Reading (모두의 알고리즘) 회문 찾기(큐와 스택)

12. (모두의 알고리즘)이진 탐색(Binary Search)

이진 탐색(Binary Search)이란 이진 탐색(binary search)은 정렬된 데이터 집합을 이분화하면서 탐색하는 방법 참조 URL 네이버 지식백과1 네이버 지식백과2 이진 탐색 알고리즘

def binary_search(a, x):
    start = 0
    end = len(a) - 1

    while start <= end:
        mid = (start + end) // 2
        if x == a[mid]:
            return mid
        elif x > a[mid]:
            start = mid + 1
        else:
            end = mid -1

    return -1


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search(d, 36))
print(binary_search(d, 50))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

def binary_search(a, x):

start = 0

end = len(a) - 1

while start <= end:

mid = (start + end) // 2

if x == a[mid]:

return mid

elif x > a[mid]:

start = mid + 1

else:

end = mid -1

return -1

d = [1, 4, 9, 16, 25, 36, 49, 64, 81]

print(binary_search(d, 36))

print(binary_search(d, 50))

연습문제. 재귀호출을 이용한 이진 탐색

def binary_search_recur(a, x, start, end):
    ...


d = [1, 4, 9, 16, 25, 36, 49, 64, 81]
print(binary_search_recur(d, 36, 0, len(d) - 1))
print(binary_search_recur(d, 50, 0, len(d) - 1))

1

2

3

4

5

6

7

def binary_search_recur(a, x, start, end):

...

d = [1, 4, 9, 16, 25, 36, 49, 64, 81]

print(binary_search_recur(d, 36, 0, len(d) - 1))

print(binary_search_recur(d, 50, 0, len(d) - 1))

..

11. (모두의 알고리즘)퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)이란 퀵 정렬(quick sort)은 기준키를 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 작은 값을 갖는 데이터와 큰 값을 갖는 데이터로 분리해가며 정렬하는 방법 참조 URL 네이버 지식백과1 네이버 지식백과2 쉽게 설명한 퀵 정렬

def qui_sort(a):
    n = len(a)

    if n <= 1:
        return a
    pivot = a[-1]
    g1 = list()
    g2 = list()

    for i in range(0, n - 1):
        if a[i] < pivot:
            g1.append(a[i])
        else:
            g2.append(a[i])

    return qui_sort(g1) + [pivot] + qui_sort(g2)


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(qui_sort(d))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

def qui_sort(a):

n = len(a)

if n <= 1:

return a

pivot = a[-1]

g1 = list()

g2 = list()

for i in range(0, n - 1):

if a[i] < pivot:

g1.append(a[i])

else:

g2.append(a[i])

return qui_sort(g1) + [pivot] + qui_sort(g2)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

print(qui_sort(d))

퀵 정렬 알고리즘

def quick_sort(a, start, end):
    if end - start <= 0:
        return

    pivot = a[end]
    i = start
    for j in range(start, end):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1

    a[i], a[end] = a[end], a[i]

    quick_sort(a, start, i - 1)
    quick_sort(a, i + 1, end)


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort(d, 0, len(d) - 1)
print(d)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

def quick_sort(a, start, end):

if end - start <= 0:

return

pivot = a[end]

i = start

for j in range(start, end):

if a[j] <= pivot:

a[i], a[j] = a[j], a[i]

i += 1

a[i], a[end] = a[end], a[i]

quick_sort(a, start, i - 1)

quick_sort(a, i + 1, end)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

quick_sort(d, 0, len(d) - 1)

print(d)

퀵 정렬(과거 알고리즘)

def quick_sort_old(a, start, end):
    if start < end:
        p = start
        l = start + 1
        r = end;
        while l <= r:
            while l <= end and a[l] <= a[p] :
                l = l + 1
            while r >= start + 1 and a[r] >= a[p]:
                r = r - 1
            if l < r:
                a[l], a[r] = a[r], a[l]

            a[p], a[r] = a[r], a[p]
            quick_sort_old(a, start, r-1)
            quick_sort_old(a, r + 1, end)


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
quick_sort_old(d, 0, len(d) - 1)
print(d)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

def quick_sort_old(a, start, end):

if start < end:

p = start

l = start + 1

r = end;

while l <= r:

while l <= end and a[l] <= a[p] :

l = l + 1

while r >= start + 1 and a[r] >= a[p]:

r = r - 1

if l < r:

a[l], a[r] = a[r], a[l]

a[p], a[r] = a[r], a[p]

quick_sort_old(a, start, r-1)

quick_sort_old(a, r + 1, end)

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

quick_sort_old(d, 0, len(d) - 1)

print(d)

… Continue Reading 11. (모두의 알고리즘)퀵 정렬(Quick Sort)

10. (모두의 알고리즘)병합 정렬(Merge Sort)

병합 정렬(Merge Sort)이란 주어진 데이터들을 몇 부분으로 분할한 다음 각각을 재귀적으로 정렬하고, 두 부분을 합쳐서 하나로 만드는 방법 복잡도는 O(n log n)으로 비교적 좋은 편이나 내부 정렬로는 별로 사용하지 않고 주로 외부 정렬을 위해 사용 쉽게 설명한 병합 정렬

def mer_sort(a):
    n = len(a)

    if n <= 1:
        return a

    mid = n // 2
    g1 = mer_sort(a[:mid])
    g2 = mer_sort(a[mid:])

    result = list()
    while g1 and g2:
        if g1[0] < g2[0]:
            result.append(g1.pop(0))
        else:
            result.append(g2.pop(0))

    while g1:
        result.append(g1.pop(0))
    while g2:
        result.append(g2.pop(0))

    return result


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
print(mer_sort(d))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

def mer_sort(a):

n = len(a)

if n <= 1:

return a

mid = n // 2

g1 = mer_sort(a[:mid])

g2 = mer_sort(a[mid:])

result = list()

while g1 and g2:

if g1[0] < g2[0]:

result.append(g1.pop(0))

else:

result.append(g2.pop(0))

while g1:

result.append(g1.pop(0))

while g2:

result.append(g2.pop(0))

return result

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

print(mer_sort(d))

병합 정렬 알고리즘

def merge_sort(a):
    n = len(a)

    if n <= 1:
        return

    mid = n // 2
    g1 = a[:mid]
    g2 = a[mid:]
    merge_sort(g1)
    merge_sort(g2)

    i1 = 0
    i2 = 0
    ia = 0

    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] < g2[i2]:
            a[ia] = g1[i1]
            i1 += 1
            ia += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
            ia += 1

    while i1 < len(g1):
        a[ia] = g1[i1]
        i1 += 1
        ia += 1
    while i2 < len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort(d)
print(d)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

def merge_sort(a):

n = len(a)

if n <= 1:

return

mid = n // 2

g1 = a[:mid]

g2 = a[mid:]

merge_sort(g1)

merge_sort(g2)

i1 = 0

i2 = 0

ia = 0

while i1 < len(g1) and i2 < len(g2):

if g1[i1] < g2[i2]:

a[ia] = g1[i1]

i1 += 1

ia += 1

else:

a[ia] = g2[i2]

i2 += 1

ia += 1

while i1 < len(g1):

a[ia] = g1[i1]

i1 += 1

ia += 1

while i2 < len(g2):

a[ia] = g2[i2]

i2 += 1

ia += 1

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

merge_sort(d)

print(d)

연습문제1. 큰수에서 작은수 순서로 나열하는 병합 정렬 알고리즘

def merge_sort_rev(a):
    ....


d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]
merge_sort_rev(d)
print(d)

1

2

3

4

5

6

7

def merge_sort_rev(a):

....

d = [6, 8, 3, 9, 10, 1, 2, 4, 7, 5]

merge_sort_rev(d)

print(d)

..

09. (모두의 알고리즘)삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)이란 삽입 정렬(insertion sort)은 아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식 참조 URL 네이버 지식백과1 네이버 지식백과2 쉽게 설명한 삽입 정렬

def find_ins_idx(b, v):
    for i in range(0, len(b)):
        if v < b[i]:
            return i

    return len(b)


def ins_sort(a):
    result = list()
    while a:
        value = a.pop(0)
        ins_idx = find_ins_idx(result, value)
        result.insert(ins_idx, value)

    return result


d = [2, 4, 5, 1, 3]
print(ins_sort(d))

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

def find_ins_idx(b, v):

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

if v < b[i]:

return i

return len(b)

def ins_sort(a):

result = list()

while a:

value = a.pop(0)

ins_idx = find_ins_idx(result, value)

result.insert(ins_idx, value)

return result

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

print(ins_sort(d))

삽입 정렬 알고리즘

def insertion_sort(a):
    n = len(a)
    for i in range(1, n):
        value = a[i]
        j = i - 1
        while j >= 0 and value < a[j]:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = value


d = [2, 4, 5, 1, 3]
insertion_sort(d)
print(d)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

def insertion_sort(a):

n = len(a)

for i in range(1, n):

value = a[i]

j = i - 1

while j >= 0 and value < a[j]:

a[j + 1] = a[j]

j -= 1

a[j + 1] = value

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

insertion_sort(d)

print(d)

연습문제2. 큰수에서 작은수 순서로 나열하는 삽입 정렬 알고리즘

def insertion_sort_rev(a):
    ...


v = [2, 4, 5, 1, 3]
insertion_sort_rev(v)
print(v)

1

2

3

4

5

6

7

def insertion_sort_rev(a):

...

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

insertion_sort_rev(v)

print(v)

..