2022 제주코딩베이스캠프 DAY 7

반복문과 재귀함수

# merge sort, quick sort, 메모이제이션 기법, 다이나믹 프로그래밍 => 재귀함수의 확장

merge sort

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 합병 정렬은 다음의 단계들로 이루어진다.
  • 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

 

• 2개의 정렬된 리스트를 합병하는 과정
  1. 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
  2. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
  3. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
  4. 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.

• 합병 정렬(merge sort) 알고리즘의 특징
  • 단점
    • 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다 => 제자리 정렬(in-place sorting)이 아니다.
    • 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
  • 장점
    • 안정적인 정렬방법
      • 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
    • 레코드를 연결리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
    • 따라서 크기가 큰 레코드를 정렬할 떄 연결 리스트를 사용하면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬방법보다 효율적이다.

quick sort

• 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
• 퀵 정렬은 다음의 단계들로 이루어진다.
  • 분할(Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
  • 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
  • 순환 호출이 한 번 진행될 때마다 최소한 하나의 원소(피벗)은 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

• 퀵 정렬(quick sort) 알고리즘의 예제

메모이제이션(Memoization) 기법

 

동일한 연산을 반복해야 할 때 이전에 연산한 값을 메모리에 미리 저장해 둠으로써 계산의 반복수행을 제거하여 프로그램 실행 속도를 향상시키는 기술

함수

함수를 사용하면서 global 전역변수를 다루게 되는데, closure까지 확장이 가능하다.

closure

Python의 Closure에 대해 알아보자

정규표현식

정규표현식

클래스

super

• 자식 클래스에서 부모클래스의 내용을 사용하고 싶을 경우 사용함.

오버라이딩, 오버로딩

• 오버로딩 : 메소드의 이름이 같고, 매개변수의 개수나 타입이 달라야한다.
• 오버라이딩 : 부모 클래스로부터 상속받은 메소드를 자식 클래스에서 재정의하는 것

---

전공 때 저 기억 넘어에 있던 개념들을 한꺼번에 복습하게되는 계기였다.