짤짤이 알고리즘 특강

원래 어려운거라서 어려운거고..

알고리즘을 설계하는 방법에 대해 논함

• 알고리즘은 한 마디로 레시피
  • 목적하는 결과물을 만들기 위해 존재
  • 수행해야 하는 절차, 과정을 단계 별로 정확하게 기술 한 것
  • 우린 여기서 컴퓨터를 사용한 알고리즘에 대해 주로 논함
• Problems and Algorithms
  • 문제가 있어야 방법을 이야기 하지
    • 명확한 Problem의 서술이 필요하다.
    • 수학적으로 탐구 가능한 대상 :
      • Problem : 가능한 입력들의 집합과 각 입력에 대한 출력의 쌍
      • Algorithm : 그런 Problem에 대해 올바른 출력을 하게 되는 기본 연산들의 sequence
      • 사실 함수!!
        • prob : 함수의 정의
        • algor : 함수 값 계산을 하는 과정
• 알고리즘을 기술하기
  • 충분한 알고리즘에 대한 기술과 설명은
    • 자연어 기술, Pseudocode, Program Code 라는 수단
    • 짤 수는 있겠다, 근데 설명은 못하겠다………….?
    • 코드를 쓸 만큼 아이디어가 구체화 되지 않은 상태를 자주 접할 것이다.
      • 코드는 꽤 까다로운 언어이기 때문이지!!!!!!!!!!
• 알고리즘을 분석하기
  • Correctness Proof : 정확도
    • 주로 수학적 귀납법을 활용한다. (Induction is our friend)
  • Running Time Analysis : 시간복잡도 분석

Example : Multiplication.

• Multiplication Problem, 곱셈 문제
  • Input, 자연수 2개 x, y
  • Output , 자연수 1개
• 우리가 초등학교 때 배운게 있다 : Long Multiplication
• 또 다른 형태도 있다.. : Lattice Multiplication
• 근데 이게 끝일까?
• 하나의 문제에 대해 여러가지 Algorithm을 생각 할 수 있다.

Another Example : Sorting Problem

• 정렬, 아시다시피 정직하면 조낸 느리지..
• Bubble, Insertion, … Sorting O(nˆ2)
• Merge Sort, Quick Sort : 재귀에 대한 내용을 요구한다 :
  • Divide and conquer 기법으로 설계된 정렬 알고리즘이다.

오늘의 목표는 재귀를 이해하기라는데

Recursion : 모두 재귀로 재귀한다 !!!!!!!!!!!!!!

알고리즘 설계 기법

• Divide and conquer
• Backtracking
• Dynamic Programming
• Greedy Algorithms
• 기저에 깔려있는 배경지식이 재귀이다. 그러니까 재귀를 모르면 뭘 하지를 못할 것이다.

트리 및 그래프 순회 알고리즘

• In-order | Pre-order | Post-oreder Travseral
• DFS, BFS

반복문과 재귀의 관계

• 서로 변환이 가능함

Recursive definition in mathmatics

자연수의 정의 :

• 1은 자연수이다.
• n이 자연수이면, n보다 1 큰 수도 자연 수이다.

Data structures

• Linked List
  • Null은 List이다.
  • A가 List이면, A 앞에 노드를 연결한 전체도 List이다.
• Binary Tree
  • 공집합은 Binary Tree이다.
  • T1과 T2가 Binary Tree라면..?

Reduction (Induction 아님)

• 알고리즘 설계에서 가장 자주 사용하는 거의 유일한 기술
• Reducing one problem X to another problem Y
  • X를 풀기 위한 알고리즘을 기술 할 때
  • Y의 알고리즘을 이용, 호출한다. → Black box, subroutine.
  • X를 풀면서 Y를 호출하는 그 행위를 Reduction 이라 생각하면 빠릅니다.
  • 이차방정식에 대한 근을 계산하고 싶다라고 하자.
    • 근의 공식에 맞게 계산하면 되겠지만, 내장 함수를 생각해본다.

주의!

• Y의 동작 방식은 알 필요가 없다.
• 그 알고리즘이 Y를 해결한다고 가정한다. Black box 처럼 생각하기

Reduction Examples

• 배열에서 최솟값 찾기
  • 방법 1
    1. A를 정렬한다. return A[0]
  • 방법 2
    1. Selection(A, k)
       1. A를 정렬하고, return A[k-1]
• Selection 문제를 정렬 문제로 reduce 하여 해결한다.
  • Selection 수행을 위해 Sorting 알고리즘을 subroutine으로 활용한다.
  • 이 문제를 위한 할 일이 줄어들었다. REDUCE!!!!

Reduction

• 사실 내가 이미 쓰고 있는 기술
  • 복잡한 문제를 해결하기 위해 단계 나누기
  • 내가 작성하는 함수에서 다른 함수를 호출 하는 것
    • 내가 만든 다른거, STL, 남이 만든거, 기본 연산자. 등등. .. .. . . ..
• 알고리즘을 설계할 때 (함수를 작성할 때)
  • 사용하는 basic building block들이 어떻게 동작하는지 몰라도 된다.
  • 내 알고리즘이 다른 알고리즘에서 building block으로써 사용 될 수 있을지 몰라도 된다.
  • 알더라도 모른척 하랜다.

느낌이 새하얘지는 경우가 있다.

Reduction으로 사용하게 되는 것이 무얼 해결 해줄 수 있느냐? 해결하고자 하는 문제가 어떤 문제이냐? 를 아는게 시작이다.

Recursion

• 특별한 종류의 Reduction
  • 주어진 문제의 instance가 충분히 작아서 바로 풀 수 있으면 바로 풀어.
  • 그렇지 않으면, 같은 문제의 더 작은 instance로 Reduction 한다.
  • 즉 Recursion은 같은 문제로 Reduction 하는 것
    • 단, 입력 사이즈가 줄어들어야 한다.
    • Recursion = Subproblem으로 Reduction이다.
• Recursion의 근본적 이해를 하려면 들어가서 이해하는 것은 아니다.
• Hanoi Tower
  • n개의 Disc와 3개의 Peg
  • n - 1개를 옮기는 것은
    • 원래 instance보다 작은 Hanoi tower 문제의 instance → subproblem
    • n번째를 옮길 수 있으면 n-1을 옮길 수 있다.

그 말이 그 말 저 말이 저 말인 것 같은 느낌, 그놈의 귀납법..

Recursion : in general

• Recursion은 reduction의 일종
  • base case
    • 주어진 문제의 instance가 충분히 작아서 바로 풀 수 있으면, 바로 수행한다.
  • recursion step
    • 그렇지 않으면, 같은 문제의 더 작은 instance로 Reduction 한다.
• Simplify & Delegate
  • Simplify : 더 작은 instance (subproblem)를 만들고
  • Delegate : 던져버리고 잊어버려 (recursion의 magic; Recursion Fairy가 해주겠지..)
• 왜됨 이게
  • by Induction, 수학적 귀납법

 

(내 생각에) 핀트는 이 부분이다.

Merge Sort

• 주어진 배열을 대략 절반으로, 둘로 나눈다
• 두 subArray를 각각 “정렬”한다 (by recursion)
• 정렬된 두 subArray를 합쳐서(merge) 하나의 정렬된 배열로 만든다
• T(n) = 2T(n/2) + O(n)
  • T(n) = O(n logn)

Quick Sort

• 평균적 분석은 O(n log n)
• 최악의 경우, r이 1이거나 n으로 잡혀버린경우..
• T(n) = T(n - 1) + O(n) = O(nˆ2)

Recursion

SImplify and delegate

자신으로 reduce

Correctness : induction으로 증명

time complexity analysis : 점화식 구하기

핀트는
Reduction의 존재를 자주 상기 하도록 한다.