switch

여러 가지 정렬 알고리즘의 차이점을 이해하고, 해당 상황에서 어떤 알고리즘이 어울릴지 살펴보자 예를 들어 Cat이라는 객체로 이루어진 아주 크기가 큰 배열이 있다고 하자 이 배열에 담긴 객체들을 나이순으로 정렬하라고 했을 때 어떤 알고리즘을 사용해야 할까? 여기서 알 수 있는 2가지는 1. 배열의 크기가 크므로 효율성이 매우 중요하다. 2. 나이순으로 정렬하는 것이므로 그 값의 범위가 좁다는 것을 알 수 있다. 다양한 정렬 알고리즘들을 살펴봤을 때 버킷 정렬 혹은 기수 정렬이 가장 적합하리라는 것을 눈치챌 수 있다. 각 버킷의 크기를 1년으로 설정하면 O(n)에 정렬할 수 있다. 자주 사용되는 정렬 알고리즘을 알아두면 문제풀이 능력을 크게 향상할 수 있다. 1. 버블 정렬 평균 및 최악 실행시간 : O(..

정렬을 이용한 문제풀이 무차별 알고리즘을 이용해서 O(n^2) 시간에 문제를 쉽게 풀어낼 수 있는 경우는 많지만 O(n^2)은 입력 크기가 클 때 사용하기에는 너무 느리다 O(n^2)이 걸리는 문제를 O(n)이나 O(n log n)시간으로 풀 수 있는 알고리즘의 설계에 대해 알아보자 예를 들어 배열의 모든 원소가 유일한지 검사한다고 해보자 아래의 무차별 알고리즘은 두 원소의 모든 조합을 O(n^2)에 살펴보는 것이다 bool ok = true; for (int i = 0; i < n; i++) { for (int j= i+1; j < n; j++) { if (array[i] == array[j]) ok = false; } } 배열을 정렬한다면 배열에 같은 원소가 있을 때 그 원소들이 정렬된 배열에서 나란..

시간복잡도는 알고리즘 로직을 코드로 구현할 때 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계이다. Big-O 표기법 시간복잡도를 표기하는 방법들이다. 1. Big-O (오) - 상한(최악의 경우) 2. Big-Ω (오메가) - 하한(최선의 경우) 3. Big-Θ (세타) - 평균(중간의 경우) O(1) constant complexity : 입력값이 증가하더라도 시간이 늘어나지 않는다. (입력 크기 상관없이 즉시 출력) O(n) linear complexity : 입력값이 증가함에 따라 시간 또한 같은 비율로 증가 (n앞에 있는 계수는 무시) O(log n) logarithmic complexity : 빅오 표기법 중 O(1) 다음으로 빠름 Binary Search같이 절반씩 줄어드는 경우 O(n^..