Problems and Technique

• Problems
  • ex. Sorting
  • ex. Selection (minimum, maximum, k-th smallest element)
• Techniques - Strategy
  • Divide and Conquer : merge-sorting(반으로 자름), Quick-sort(pivot을 정해서 작으면 왼쪽, 크면 오른쪽)
  • Backtracking: maze problem (미로 찾기, 1,2,3을 기억하고 현재 위치를 stack에 저장, exit이 나오면 찾은 것, 벽이 나오면 stack의 맨위를 따라감. → 8 queens라는 유명한 문제가 있음.)
  • Greedy
  • Dynamic Programming: 미니멈, 프린스 알고리즘

Data Structure

• 문제를 풀 때 중요한 역할을 함.
• ex. Search Problem
  • Linked List: (굳이 잘 사용하지 않음) → n개의 데이터를 11로 만들어서. 한 군데에서 차근차근.
    • sequential search와 binary search가 있음.
  • Binary Search Trees
    • O(log(n))를 기대하고 만들었지만 worst case는 O(n)만큼 걸림
  • Hash tables
    • 키가 들어가면 hash table로 들어가서 찾는다. hash에서 걸리는 시간만 constant 시간이 된다.
    • collision이라고 해서 한 쪽으로 몰릴 수 있음.
    • 적은 리소스로 많은 데이터를 효율적으로 관리할 때 유용함.
  • Linear Array
    • sorting 이 되어있으면, binary search
    • sorting 이 안되어있으면, sequential search

⇒ input에 대하여 어떤 ds를 사용할 것인지 판단하는 것이 중요함.

Algorithm

• input을 변환시키는 잘 정의된 산술적인 절차이다. 어떤 값이나 값의 집합을 원하는 결과값으로 바꾸는 과정이다.
• input을 output으로 바꾸는 데 well-defined된 것이다.
  • Example1. Sorting Algorithm
    • 예) 1~100까지의 숫자가 있다고 할 때, 이를 다 뒤집어 놓고 흩뿌리면 숫자가 안보이기 때문에 아무거나 잡고 이를 기준으로 정렬을 한다. → insertion sort2
      • input: n개의 숫자들의 배열
      • output: 재정렬된 input들, 예를 들면 작은 순으로.
    • 문제의 예시; 특정한 배열인 <31, 41, 59, 26, 41>이 있다고 할 때
      • output은 sequence <26, 31, 41, 41, 58, 59>가 된다.

An Example: Insertion Sort

InsertionSort(A, n)
	for i = 2 to n {
		key = A[i]
		j = i - 1;
		while (j > 0) and (A[j] > key) {
			A[j+1] = A[j]
			j = j - 1
		}
		A[j+1] = key
}

• i = 1인 경우 무조건 sorting이다 (첫 번째이기 때문)

Expressing algorithms

• 명확하고 간결한 알고리즘으로 표현해야 한다.
• 대부분 영어로 표현함.
• pseudocode를 사용한다 → part code, part English
  • 이는 프로그래밍 언어와 유사하다.