[14일차] 합병정렬(Merge sort) / 클래스와 객체(Class and Object)

합병정렬(Merge sort) / 클래스와 객체(Class and Object)에 대해서 정리한다.

※ 분할-정복 기법(Divide and Conquer)

- 처리하기 어려워보이는 아주 많은 데이터도 작은 단위로 쪼개면 처리가 가능하다.

- 정렬에서만 사용하는 방법이 아니라 대부분의 문제에서 효율적으로 적용이 가능하다.

- 합병정렬, 퀵정렬, 힙 정렬 등이 분할-정복 기법을 개념으로 동작한다.

---

※ 합병정렬(Merge sort)

- 데이터를 하나의 원소 단위로 각각 분할한 다음에 인접한 원소끼리 정렬을 하면서

합병해주는 방식이다.

- 분할-정복 기법을 사용하는 대표적인 알고리즘이다.

- 재귀적 용법이 이런 문제에서 얼마나 효율적으로 동작할수 있는지 확인할 수 있다.

- 아래 코드는 재귀적 용법을 이용해서 합병정렬을 작성했다.

* 다른 방법도 있지만 여기서는 합병을 할때 tmp라는 빈 리스트를 만들어 주어서  left와 right 값을 비교해서

작은쪽의 값을 tmp 변수에 넣어주고 원래 리스트에 있는 값은 

remove()로 지워주는 방식으로 합병정렬을 진행 하였다.

* 이런식으로 정렬하다보면 마지막에 left나 right 리스트에 제일 큰 값이 하나 남기 때문에

if 문을 이용해 마지막 값을 리스트 자료형인 tmp 변수에 추가 시켜준다.

* lists에 총길이를 size변수로 가져와서 해당 리스트의 원소들이 하나의 원소단위가 될때까지

재귀적 함수를 이용해서 나누어 주어야 한다.

* 합병정렬이 동작하는걸 눈으로 보기위해서 unorder라는 리스트를 만들어주고 

divide()함수에 lists값을 unorder 리스트를 넣어줬다 

( 실행결과를 보면 unorder 리스트를 병합정렬하는 과정을 따라가볼수 있다 )

merge_sort.py

---

※ 클래스와 객체(Class and Object)

1. 클래스(Class)

- Blue Print (청사진)

- 사용자 정의 데이터 타입

- 멤버 변수(속성)

예). 나이, 이름, 사는곳, ...

- 멤버 메서드(method)

( 함수나 프로시져가 클래스 내에 속해있으면 메서드라고 표현한다 )

2. 객체(Object)

- 클래스의 실체화 된 내용

- 객체는 곧 변수다.

( 변수가 가지고 있는 내용이 조금 많을 뿐...)

3. 인스턴스화

- 클래스를 객체로 만드는 과정

( 아무 내용없이 비어있는 Sample이라는 클래스를 만들었다 )

( 실행 결과를 보면 Sample() 클래스를 객체화 시킬때마다 끝에 주소값이 변하는걸 알수 있다 )

---

※ 개발 방법론 발전 과정

1. 절차지향 (함수단위, 프로시져)

2. 객체지향 (Object(사물))

3. 함수형 언어 (Value oriented)