[Problem Solving Paradigms]

#주된 접근 방법 

• complete search
• divide and conquer
• greedy
• DP...

 

ex)

Input : Size m(<= 1000) 인 array A

 

• A에서 제일 큰 element와 작은 element 찾기 :
  • complete search 
    • O(n) time
• A에서 k번째로 작은 element 찾기
  • Divide and conquer
    • O(n log n) or O(n) excepted time
• A의 두 element x,y에 대해 |x-y|의 최대값 구하기 
  • Greedy 
    • O(n) time
• A의 longest increasing subsequence구하기
  • DP - O(n**2) or Greedy - O(n log k)

k는 LIS의 길이

 

해당 상황마다 저 알고리즘을 왜 써야하는지 1도 모르겠지만 이제 알아가 보자! ㅎ

이런 사진이라도 넣어야지 기분이가 좋아지지 않을까?