패러다임이란?
- 전형적인 예 또는 패턴을 뜻함
알고리즘 패러다임이란?
- 어떠한 문제에 대한 알고리즘 접근 패턴을 뜻한다. 한문제에 여러가지 방식의 풀이가 있듯이 마찬가지로 한문제에 두개 이상의 알고리즘 패러다임이 존재할 수도 있는 것이다.
Brute Force란?
- 무식한 힘이라는 뜻에서 느껴지듯이 머리가 나쁘면 손발이 고생과 어울리는 말이다. 하나부터 열가지 전부다 계산해서 값을 찾는 방식이라고 보면된다. 컴퓨터는 손발(단순 계산능력)이 빠르니 고생해도 될 듯 하나 Brute Force는 비효율 적이기 방식이기 때문에 가능하면 인풋이 적은 경우애만 사용할 만하다. 하지만 직관적인 방법이기에 Brute Force 방식을 먼저 고안하는 것이 효율적인 알고리즘을 찾기 위한 첫 단추라고 코드잇 강사분이 말하시니 Brute Force를 먼저 고안해보도록 하자
Brute Force 연습문제 3개 풀이
Divide and Conquer
-
구조
- divide, conquer, combine의 연속
합병 정렬(merge sort)
- divide, conquer 로 list의 요소가 하나가 될때까지 부분문제들을 만든다음 2 부분문제들의 왼쪽에 있는 값 즉 첫번째 인덱스에 위치한값들 끼리 비교해서 순서대로 combine을 해주는 방법이다.
퀵 정렬(Quick Sort)
- 끝에 있는 값을 기준으로 나머지 값들을 왼쪽 오른쪽으로 나눈다음 정렬 하는 방식?
Merge Sort와 Quick Sort 사이의 특이점
- 합병정렬을 구현할때 divide, conquer, combine 세 부분중 combine부분을 고안하는게 복잡했다면 퀵정렬은 반대로 divide 즉 첫번재 부분을 고안하는게 관건이다.
도전!