파이썬 – 페이지 9

08. (모두의 알고리즘)선택 정렬(Selection Sort)

선택 정렬이란 선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식 참조 URL 네이버 지식백과1 네이버 지식백과2 쉽게 설명한 선택 정렬

def find_min_idx(b):
    n = len(b)
    min_idx = 0
    for i in range(1, n):
        if b[min_idx] > b[i]:
            min_idx = i

    return min_idx


def sel_sort(a):
    result = list()
    while a:
        min_idx = find_min_idx(a)
        value = a.pop(min_idx)
        result.append(value)

    return result


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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

def find_min_idx(b):

n = len(b)

min_idx = 0

for i in range(1, n):

if b[min_idx] > b[i]:

min_idx = i

return min_idx

def sel_sort(a):

result = list()

while a:

min_idx = find_min_idx(a)

value = a.pop(min_idx)

result.append(value)

return result

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

print(sel_sort(v))

선택 정렬 알고리즘

def selection_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_idx = i
        for j in range(i + 1, n):
            if a[min_idx] > a[j]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]


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

1

2

3

4

5

6

7

8

9

10

11

12

13

def selection_sort(a):

n = len(a)

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

min_idx = i

for j in range(i + 1, n):

if a[min_idx] > a[j]:

min_idx = j

a[i], a[min_idx] = a[min_idx], a[i]

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

selection_sort(v)

print(v)

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

def selection_sort_rev(a):
    ...


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

1

2

3

4

5

6

7

def selection_sort_rev(a):

...

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

selection_sort_rev(v)

print(v)

..

07. (모두의 알고리즘)순차 탐색(Sequential Search)

순차 탐색으로 특정 값의 위치 찾기

def search_list(a, x):
    n = len(a)
    for i in range(0, n):
        if x == a[i]:
            return i

    return -1


v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list(v, 18))
print(search_list(v, 33))
print(search_list(v, 900))

1

2

3

4

5

6

7

8

9

10

11

12

13

def search_list(a, x):

n = len(a)

for i in range(0, n):

if x == a[i]:

return i

return -1

v = [17, 92, 18, 33, 58, 7, 33, 42]

print(search_list(v, 18))

print(search_list(v, 33))

print(search_list(v, 900))

연습문제 1. 찾는 값이 여러 개 있으면 각 해당 위치를, 없으면 빈 리스트 []를 돌려주도록 수정

def search_list_ex1(a, x):
    ...
    ...


v = [17, 92, 18, 33, 58, 7, 33, 42]
print(search_list_ex1(v, 18))
print(search_list_ex1(v, 33))
print(search_list_ex1(v, 900))

1

2

3

4

5

6

7

8

9

def search_list_ex1(a, x):

...

v = [17, 92, 18, 33, 58, 7, 33, 42]

print(search_list_ex1(v, 18))

print(search_list_ex1(v, 33))

print(search_list_ex1(v, 900))

연습문제3. 학생번호 리스트, 학생이름 리스트 2개가 주어지고 학생 번호로 찾으면 학생이름을, 학생번호가 없으면 ?를 돌려주는 프로그램,

def search_list_ex3(a, b, x):
    ...
    ...


stu_no = [39, 14, 67, 105]
stu_name = ["Justin", "John", "Mike", "Summer"]
print(search_list_ex3(stu_no, stu_name, 67))
print(search_list_ex3(stu_no, stu_name, 99))

1

2

3

4

5

6

7

8

9

def search_list_ex3(a, b, x):

...

stu_no = [39, 14, 67, 105]

stu_name = ["Justin", "John", "Mike", "Summer"]

print(search_list_ex3(stu_no, stu_name, 67))

print(search_list_ex3(stu_no, stu_name, 99))

..

06. (모두의 알고리즘)하노이의 탑 옮기기

하노이의 탑 규칙 크기가 다른 원반 n개를 출발점 기둥에서 도착점 기둥으로 전부 옮김 원반은 한 번에 한 개씩만 옮길 수 있음 원반을 옮길 때는 한 기둥의 맨 위 원반을 뽑아 다른 기둥의 맨 위로만 옮길 수 있음 원반을 옮기는 과정에서 큰 원반을 작은 원반 위로 올릴 수 없음 하노이의 탑… Continue Reading 06. (모두의 알고리즘)하노이의 탑 옮기기

05. (모두의 알고리즘)최대공약수 구하기

최대공약수 알고리즘 두 수 중 더 작은값을 i에 저장 i가 두 수의 공통된 약수인지 확인 공통된 약수이면 이 값을 결과값으로 돌려주고 종료 그렇지 않으면 i=1-1후 2번으로 돌아가 반복 최대공약수 구하기

def gcd(a, b):
    i = min(a, b)
    while True:
        if a % i == 0 and b % i == 0:
            return i
        i = i - 1


print(gcd(1, 5))
print(gcd(3, 6))
print(gcd(60, 24))
print(gcd(81, 27))

1

2

3

4

5

6

7

8

9

10

11

12

def gcd(a, b):

i = min(a, b)

while True:

if a % i == 0 and b % i == 0:

return i

i = i - 1

print(gcd(1, 5))

print(gcd(3, 6))

print(gcd(60, 24))

print(gcd(81, 27))

유클리드 최대공약수 특징 a와 b의 최대공약수는 b와 a%b의 최대공약수와 같다 어떤 수와 0의 최대공약수는 자기 자신 유클리드를 이용하여 최대공약수… Continue Reading 05. (모두의 알고리즘)최대공약수 구하기

04. (모두의 알고리즘)팩토리얼 구하기

팩토리얼 구하기

def fact1(n):
    f = 1
    for i in range(1, n + 1):
        f = f * i
    return f


print(fact1(1))
print(fact1(5))
print(fact1(10))

1

2

3

4

5

6

7

8

9

10

def fact1(n):

f = 1

for i in range(1, n + 1):

f = f * i

return f

print(fact1(1))

print(fact1(5))

print(fact1(10))

재귀 호출

def hello():
    print("hello")
    hello()


hello()

1

2

3

4

5

6

def hello():

print("hello")

hello()

위 코드의 문제는? 재귀 호출을 이용한 팩토리얼 구하기

def fact2(n):
    ...
    ...


print(fact2(1))
print(fact2(5))
print(fact2(10))

1

2

3

4

5

6

7

8

def fact2(n):

...

print(fact2(1))

print(fact2(5))

print(fact2(10))

연습문제 연습문제 4-1

def sum_recur(n):
    ...

1 2	def sum_recur(n): ...

연습문제 4-2

def max_recur1(a, n):
    ...


또는

def max_recur2(a):
    ...

1

2

3

4

5

6

7

8

def max_recur1(a, n):

...

또는

def max_recur2(a):

...

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

동명이인 찾기

def find_same_name(a):
    n = len(a)
    result = set()

    for i in range(0, n-1):
        for j in range(i+1, n):
            if a[i] == a[j]:
                result.add(a[i])
    return result


name = ["Tom", "Jerry", "Mike", "Tom"]
print(find_same_name(name))

1

2

3

4

5

6

7

8

9

10

11

12

13

def find_same_name(a):

n = len(a)

result = set()

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

for j in range(i+1, n):

if a[i] == a[j]:

result.add(a[i])

return result

name = ["Tom", "Jerry", "Mike", "Tom"]

print(find_same_name(name))

result를 set이 아닌 list로 만들면 어떤 문제가 발생하는가? 위 코드를 아래와 같이 result를 set이 아닌 list로 만드시오.

def find_same_name_list(a):
    ....
    ....
print(find_same_name_list(name))

1

2

3

4

def find_same_name_list(a):

....

print(find_same_name_list(name))

연습문제 3-1

def make_couple(a):
    ....
    ....


v = ["Tom", "Jerry", "Mike"]
print(make_couple(v))

1

2

3

4

5

6

7

def make_couple(a):

....

v = ["Tom", "Jerry", "Mike"]

print(make_couple(v))

연습문제 3-2 집합(set) 함수 사용 예제

m = {17, 92, 18, 33, 58, 27, 32, 42}
n = {17, 92, 36, 53}
# Set 함수들
m.add(55)
print(m, "55추가(add)")
m.add(55)
print(m, "추가 반복(add)")
print(m.pop(), "맨 앞의 값 추출(pop)")
print(m, "pop를 사용하면 맨 앞의 값 제거됨")
m.discard(27)
print(m, "27을 삭제(discard)")
m.remove(42)
print(m, "32을 삭제(remove)")
p = m.union(n)
print(m, n, p, "합집합(union)")
q = m.intersection(n)
print(m, n, q, "교집합(intersection)")
r = m.difference(n)
print(m, n, r, "차집합(difference)")
s = m.copy()
print(m, s, "복사(copy)")
print(17 in m, "포함 여부(in)" )
print(m.issubset(n), "m<n 부분집합 여부(issubset)")
print(m.issubset(p), "m<p 부분집합 여부(issubset)")
print(m.issuperset(n), "m>n 부분집합 여부(issubset)")
print(m.issuperset(p), "m<p 부분집합 여부(issubset)")
print(m.isdisjoint(n), "m과 n의 교집합이 없는지 여부(isdisjoint)")
print(r.isdisjoint(n), "r과 n의 교집합이 없는지 여부(isdisjoint)")
m.clear()
print(m, "모두 제거(clear)")

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

m = {17, 92, 18, 33, 58, 27, 32, 42}

n = {17, 92, 36, 53}

# Set 함수들

m.add(55)

print(m, "55추가(add)")

m.add(55)

print(m, "추가 반복(add)")

print(m.pop(), "맨 앞의 값 추출(pop)")

print(m, "pop를 사용하면 맨 앞의 값 제거됨")

m.discard(27)

print(m, "27을 삭제(discard)")

m.remove(42)

print(m, "32을 삭제(remove)")

p = m.union(n)

print(m, n, p, "합집합(union)")

q = m.intersection(n)

print(m, n, q, "교집합(intersection)")

r = m.difference(n)

print(m, n, r, "차집합(difference)")

s = m.copy()

print(m, s, "복사(copy)")

print(17 in m, "포함 여부(in)" )

print(m.issubset(n), "m<n 부분집합 여부(issubset)")

print(m.issubset(p), "m<p 부분집합 여부(issubset)")

print(m.issuperset(n), "m>n 부분집합 여부(issubset)")

print(m.issuperset(p), "m<p 부분집합 여부(issubset)")

print(m.isdisjoint(n), "m과 n의 교집합이 없는지 여부(isdisjoint)")

print(r.isdisjoint(n), "r과 n의 교집합이 없는지 여부(isdisjoint)")

m.clear()

print(m, "모두 제거(clear)")

02. (모두의 알고리즘)최대값 찾기

최대값 찾기

v = [17,92,18,33,58,7,32,42]
n = len(v)
max_v = v[0]

for i in range(1,n):
    if v[i] > max_v:
        max_v = v[i]

print(max_v)

1

2

3

4

5

6

7

8

9

v = [17,92,18,33,58,7,32,42]

n = len(v)

max_v = v[0]

for i in range(1,n):

if v[i] > max_v:

max_v = v[i]

print(max_v)

응용1 : 위 최대값 구하기를 def를 이용하여 함수로 만들기 응용2 : n개의 숫자 중 가장 큰값이 있는 곳의 위치 알려주기 응용3 : n개의 숫자 중 가장 작은값 찾기 응용4 : n개의 숫자 중 가장 작은값이 있는 곳의 위치 알려주기 리스트 사용 예제 1

mylist = ["one", "two", "three", "four"]

#리스트 함수 사용법 : mylist. 을 쓰고 잠시 기다리면 함수 목록이 나타남

print(mylist[0])
print(mylist[2])
print(mylist[-1])
print(mylist[-3])

mylist.append("five")
print(mylist)

mylist.insert(2, "zero")
print(mylist)

print(mylist.pop(2))
print(mylist)

if "two" in mylist:
    print("있습니다")
else:
    print("없습니다")

print("리스트 항목의 수는", len(mylist))

mylist.reverse()
print(mylist)

mylist.clear()
print(mylist)
print("리스트 항목의 수는", len(mylist))

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

mylist = ["one", "two", "three", "four"]

#리스트 함수 사용법 : mylist. 을 쓰고 잠시 기다리면 함수 목록이 나타남

print(mylist[0])

print(mylist[2])

print(mylist[-1])

print(mylist[-3])

mylist.append("five")

print(mylist)

mylist.insert(2, "zero")

print(mylist)

print(mylist.pop(2))

print(mylist)

if "two" in mylist:

print("있습니다")

else:

print("없습니다")

print("리스트 항목의 수는", len(mylist))

mylist.reverse()

print(mylist)

mylist.clear()

print(mylist)

print("리스트 항목의 수는", len(mylist))

리스트 사용 예제 2

v = [17, 92, 18, 33, 58, 7, 32, 42]

print(v[0], v[2], v[-1], v[-3], "인덱스")
print(17 in v, "포함 여부(in)" )
v.append(33)
print(v, "맨뒤에 추가(append)")
print(v.count(33), "33의 개수", )
v.insert(2, 11)
print(v, "3번째에 11 삽입(insert)")
print(v.pop(4),  "5번째 값" )
print(v, "5번째 값을 빼냄(pop)")
v.remove(33)
print(v, "33을 삭제(remove)")
v.reverse()
print(v, "역순으로 배치(reverse)")
v.sort()
print(v, "정렬(sort)")
w = v.copy()
print(w, v, "v를 w에 복사(copy)")
v.clear()
print(v, "모두 삭제(clear):")

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

v = [17, 92, 18, 33, 58, 7, 32, 42]

print(v[0], v[2], v[-1], v[-3], "인덱스")

print(17 in v, "포함 여부(in)" )

v.append(33)

print(v, "맨뒤에 추가(append)")

print(v.count(33), "33의 개수", )

v.insert(2, 11)

print(v, "3번째에 11 삽입(insert)")

print(v.pop(4), "5번째 값" )

print(v, "5번째 값을 빼냄(pop)")

v.remove(33)

print(v, "33을 삭제(remove)")

v.reverse()

print(v, "역순으로 배치(reverse)")

v.sort()

print(v, "정렬(sort)")

w = v.copy()

print(w, v, "v를 w에 복사(copy)")

v.clear()

print(v, "모두 삭제(clear):")

01. (모두의 알고리즘)1부터 n까지의 합 구하기

1~n까지 연속한 숫자의 합 구하기

def sum1(n):
    s = 0
    for i in range(1,n+1):
        s = s + i

    return s

def sum2(n):
    s = n * (n + 1) // 2
    return s

print(sum1(100))
print(sum2(100))

1

2

3

4

5

6

7

8

9

10

11

12

13

def sum1(n):

s = 0

for i in range(1,n+1):

s = s + i

return s

def sum2(n):

s = n * (n + 1) // 2

return s

print(sum1(100))

print(sum2(100))

응용1 : 1부터 n까지 짝수의 합 응용2 : 1부터 n까지 홀수의 합 응용3 : 1부터 n까지 3의 배수의 합 응용4 : 1부터 n까지 3의 배수가 아닌 수의 합 계산 복잡도 시간 복잡도(time complexity) : O(1), O(n), O(n^2) 공간 복잡도(space complexity)

파이썬 기본 문법

파이썬 참조 목록 파이썬 Library : https://docs.python.org/3.7/library/index.html 파이썬 Library(한글) : https://docs.python.org/ko/3/ 파이썬 도장깨기 : https://dojang.io/course/view.php?id=7 파이썬에 대한 정리가 잘 되어 있음 Baekjoon Online Judge : https://www.acmicpc.net/ 파이썬, C, Java 등 문제은행 입력과 출력

name = input("이름이 뭔가요? ")  #홍길동을 입력한다면
print("입력된 이름은", name , "입니다") #입력된 이름은 홍길동 입니다
print("성은", name[0], "입니다")  # 홍
print("성은", name[-3], "입니다") # 홍

1

2

3

4

name = input("이름이 뭔가요? ") #홍길동을 입력한다면

print("입력된 이름은", name , "입니다") #입력된 이름은 홍길동 입니다

print("성은", name[0], "입니다") # 홍

print("성은", name[-3], "입니다") # 홍

name = input(“이름이 뭔가요? ) print(“값1”, “값2”, ….) print(변수1, 변수2, …) print(변수1, “값2”,…) 특수문자 : \n, \t, \\, \” 포멧… Continue Reading 파이썬 기본 문법

파이썬 설치하기

아나콘다(Anaconda) 패키지 설치하기(2022년 1월 수정) URL : https://www.anaconda.com/distribution/ Products -> Individual Edition -> Download 선택하면 자동으로 다운로드 됨 설치 Install for : 주어진대로(All Users 선택시 설치 폴더가 다르고, 경우에 따라 관리자 권한 CMD 요구) Choose Install Location : 주어진대로 Advanced Installation Options : 둘 다 체크 시작 -> Anaconda -> Jupyter… Continue Reading 파이썬 설치하기