프로그래밍 (5) 썸네일형 리스트형 [Design Pattern] 00. 디자인 패턴이란? 1. "디자인 패턴"이란? "디자인 패턴"이라는 개념은 사실 소프트웨어에서 처음 생겨난 것이 아닙니다. 바로, 건축의 영역에서 등장한 개념이었죠. 엥? 건축이랑 소프트웨어랑 무슨 관계가 있길래 영향을 받은 거죠? 건축과 소프트웨어, 단순히 단어만 들으면 무슨 상관이 있는지 이해가 안 가실 수도 있습니다. 하지만, 곰곰이 생각해보면 건축과 소프트웨어 개발은 닮은 점이 무척 많습니다. 고객의 요구사항을 파악하고, 이를 토대로 설계하고, 설계한 대로 프로젝트를 진행한다. 아니, 거의 같다고 해도 무방할 것 같습니다. 하지만, 여기서 큰 차이점이라고 함은 소프트웨어는 언제든 기능을 수정, 추가할 수 있는 반면에 건물은 짓고 나면 건드리기가 참 힘든 정도겠네요. 디자인 패턴은 "어떠한 설계 문제 상황에는 ~패턴이.. 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort) -하나의 요소를 고른 후(Pivot) 기준값보다 작은 요소는 앞에 위치 시키고, 큰 요소는 뒤에 위치시키는 정렬- 다른 말이 필요없다. 무려 퀵 정렬이다. 이름(Quick)에서도 알 수 있듯여러 정렬 알고리즘 중에서 가장 빠르다.평균 시간 복잡도는 O(n) 최악 시간복잡도는 O(n^2)이다. "그렇다면 퀵만 쓰면 되는 것을, 왜 여러 정렬을 쓰는거죠?" 물론, 퀵이 빠르다만, 프로그래밍이라는 것은 Case By Case.상황에 맞춰서 적절한 알고리즘을 사용해야 하는 것이다. 퀵 정렬은 재귀적 구조이므로, 재귀의 이해가 문제없다면금방 이해를 할 수 있으리라 생각한다. 대강 알고리즘의 원리는 이렇다.1. 기준값(Pivot)을 정한다.(Pivot을 정하는 기준은 자기 마음이다)2.. 삽입정렬 (Insertion Sort) 삽입 정렬(Insertion Sort) -이미 정렬 돼있는 배열에 추가 요소를 적절한 위치(?)에 삽입(Insertion) 하여 정렬하는 방식- 평균 시간복잡도, 최악 시간복잡도 모두 O(n^2)인 느린 알고리즘..다만 구현이 용이하며 인플레이스(in-place) 알고리즘이라 한다. 여기서 "적절한 위치"라는 말은,오름차순이냐 내림차순이냐에 따라 비교하는 조건이 달라질 것인데,그 조건에 맞게 비교하고 교환을 하라는 뜻이다. 또한 "이미 정렬 돼있는 배열"이라는 말은 첫 Loop때 배열의 첫 번째 요소와 두 번째 요소는 무조건 정렬을 시키고이후 Loop 부터는 그 정렬된 배열과 비교하며 교환을 하는 방식이라서 그렇다. -Sample Source- 선택정렬 (Selection Sort) 선택 정렬(Selection Sort) -배열의 요소 중 최댓값 or 최솟값을 골라서(Selection),배열의 가장 끝의 요소와 교환 하는 정렬 - 총 n개의 데이터가 있다면, 교환 횟수는 많아야 n-1번 비교 횟수는 n(n-1) / 2번, 시간 복잡도는 O(n^2)이다.비교 횟수가 버블 정렬과 같다는 특징이 있다. -Sample Source- 버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) -서로 이웃한 데이터들을 비교하며 가장 큰 데이터를 맨 뒤로 보내며 정렬하는 방식- 최악의 경우 시간복잡도는 O(n^2),최선의 경우 시간복잡도는 O(n),평균 시간복잡도는 O(n^2)이다. (시간 복잡도의 개념을 알고 싶다면 위키보다는 이 블로그를 추천한다.) 평균이 O(n^2)인 느린 알고리즘이지만, 병렬 처리에 적합하며 코드가 간단하다. 왜 느리냐 하면은, 모든 요소에 대해 비교하고, 해당 되는 요소에 교환을 하기 때문. 데이터들을 교환 시킬 때 거품이 수면 위로 올라오는 것 같다 하여버블 정렬이라고 한다.(실제로 버블정렬 애니메이션을 보면 그렇게 보이는 것 같다) -Sample Source- 이전 1 다음
