알고리즘 병합정렬 퀵정렬 등

 알고리즘이 어렵다는 말을 들어봤는데 정말 그렇더라. 설명을 듣고 이해하더라도 다시 술술 풀려면 꽤 오랜 시간을 노력해야 할 것 같다. 곧 파이썬 테스트가 있어서 진도를 나가기가 좀 부담스럽다. 복습하기에도 시간이 빠듯하다!

알고리즘 4

[알고리즘] 17 최빈값

1. 최빈값이란?
   (1) 빈도수가 가장 많은 데이터다.

[알고리즘] 18 최빈값(실습)

다시 풀어봐라!

알고리즘 5

[알고리즘] 19 근사값

1. 근사값이란?
   (1) 특정 값에 가장 가까운 값이다.
   (2) for문을 이용해서 리스트의 처음부터 끝까지 특정 값과 비교해본다.
   (3) 절대값을 구하는 abs( )을 사용해서 차이를 구한다.

[알고리즘] 22 평균(실습)

다시 풀어봐라!

[알고리즘] 23 재귀 알고리즘

1. 재귀 알고리즘이란?
   (1) 나 자신을 다시 호출하는 것을 재귀라 한다.
   (2) 팩토리얼 구할 때 써봤다.

알고리즘 6~7

[알고리즘] 24 재귀 알고리즘(실습)

1. 최대공약수 구하기
   (1) 예시
   def gcd(n1, n2):
   if n1 % n2 == 0:
   return n2
   else:
   return gcd(n2, n1 % n2)

[알고리즘] 26 하노이의 탑(실습)

1. 하노이의 탑
   (1) 재귀 알고리즘을 사용한다.
   (2) 코드를 외우자.

[알고리즘] 27 병합정렬

1. 병합정렬이란?
   (1) 자료구조를 분할하고 각각을 정렬한 후 다시 병합하여 정렬한다.

[알고리즘] 28 병합정렬(실습)

1. 문제풀이 과정
   (1) random 모듈을 이용해서 1부터 100까지의 난수를 10개 생성한다.
   (2) 병합정렬을 하는 함수 모듈을 만든다.
   (3) 난수가 2보다 작을 때 ns를 반환하게 한다.
   (4) 반씩 분할하기 위해 midIdx = len(ns) // 2을 해준다.
   (5) 분할할 때 왼쪽 숫자의 범위를 leftNums = mSort(ns[0:midIdx])로 정해준다.
   (6) 분할할 때 오른쪽 숫자의 범위를 rightNums = mSort(ns[midIdx:len(ns)])로 정해준다.
   (7) 병합을 위해 리스트를 하나 만든다.
   (8) 작은 것은 앞으로 큰 것은 뒤로 보내기 위해 왼쪽과 오른쪽 인덱스 변수를 하나씩 만든다.
   (9) while문을 이용해 왼쪽 인덱스와 오른쪽 인덱스의 반복 범위를 정해준다.
   (10) if문을 이용해 왼쪽 인덱스의 값이 오른쪽 인덱스의 값보다 작다면 병합을 위한 리스트에 왼쪽 인덱스의 값을 넣어준다.
   (11) 왼쪽 인덱스 값을 하나 추가해줬기 때문에 leftIdx += 1을 해준다.
   (12) 오른쪽 인덱스가 작은 경우는 else를 이용해서 정해준다.
   (13) 병합 리스트에 병합리스트와 오른쪽 그리고 왼쪽 인덱스의 값을 덧셈해준다.
   (14) 병합 리스트를 반환한다.
   (15) 난수를 생성시킨 창에서 병합정렬 모듈을 실행시킨다.
   (16) 출력해본다.
   (17) 오름차순과 내림차순 옵션을 위해 병합정렬 모듈에 asc = True를 넣어준다.
   (18) while문 안에 왼쪽과 오른쪽 인덱스의 순서를 정하는 부분에서 if asc:를 넣어준다.
   (19) 내림차순을 위해 else를 넣어주고 부등호를 바꿔준다.
   (20) leftNums = mSort(ns[0:midIdx])와 rightNums = mSort(ns[midIdx:len(ns)])에 asc = asc를 넣어 재귀될 때 True가 되는 걸 방지해서 내림차순이 되도록 한다.

[알고리즘] 29 퀵정렬

1. 퀵정렬이란?
   (1) 기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다.
   (2) 기준 값을 계속 정해서 비교해준다.

2. 문제풀이 과정
   (1) 퀵정렬을 하는 함수 모듈을 만든다.
   (2) if문을 이용해 len(ns)가 2보다 작을 때 ns를 반환하도록 해준다.
   (3) midIdx와 midVal를 정해준다.
   (4) smallNums = [ ], sameNums = [ ], bigNums = [ ]를 선언해준다.
   (5) for문과 if문을 이용해 n이 midVal보다 작을 때 smallNums에 넣어준다.
   (6) n이 midVal과 같을 때는 sameNums에 넣어준다.
   (7) else를 이용해 n이 midVal보다 큰 경우도 정해준다.
   (8) smallNums, sameNums, bigNums를 반환하여 재귀해준다.

[알고리즘] 30 퀵정렬(실습)

1. 문제풀이 과정
   (1) 랜덤 모듈을 이용해 난수를 만든다.
   (2) 퀵정렬 함수 모듈을 만든다.
   (3) len(ns)가 2보다 작을 때 ns를 반환한다.
   (4) midIdx = len(ns) // 2와 midVal = ns(midIdx)로 정해준다.
   (5) smallNums = [ ], sameNums = [ ], bigNums = [ ]를 만든다.
   (6) for문과 if문을 이용해 n이 midVal보다 작거나 같을 때, 클 때 위에서 만든 리스트에 각각 저장될 수 있도록 해준다.
   (7) 리스트들을 다시 반환하여 재귀해준다.
   (8) 오름차순과 내림차순 옵션을 위해 함수에 asc = True를 준다.
   (9) 리스트를 재귀한 부분에 if asc와 else를 이용해 옵션을 만든다.
   (10) 이때 bigNums와 smallNums의 위치를 바꿔주고 각각 asc=asc를 넣어준다.