조이의 개발 성장 다이어리

✅ 조합 vs 순열 차이 - 순열 : AB, BA가 다름 (순서가 중요하기 때문에) - 조합 : AB, BA가 똑같음 (순서가 중요하지 않음) 예를들어 자물쇠 번호를 123으로 해야만 풀리고 321로는 풀리지 않듯이, 순서가 중요한 것이 순열이며 샐러드에 닭가슴살을 넣은 다음 드레싱을 넣든, 드레싱을 넣은 다음 닭가슴살을 넣든 결과는 똑같기 때문에 순서는 중요하지 않는 것이 조합이다. 조합 - 순서와 상관없이, 중복 없이 n개중에 r개를 선택한 경우들을 나열 - 예를들어 [1, 2, 3]에서 서로 다른 2개의 원소를 뽑아 나열하는 경우, 중복을 고려해야하기 때문에 (1, 2), (1, 3), (2, 3)의 경우의 수가 존재한다. - 조합 공식 : func combi(_ nums: [Int], _ targ..

퀵 정렬이란? 퀵 정렬(quicksort)은 평균적으로 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬 또한 분할-정복법에 근거한다. 2개의 부분 리스트로 분할한 후 각각의 부분 리스트를 다시 퀵 정렬한다. 그러나 리스트를 비균등하게 분할한다. 먼저, 리스트의 한 요소를 피봇(pivot)으로 선택한다. (여기서는 마지막 요소를 선택한 경우와 첫 번째 요소를 선택한 경우를 다룬다.) 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮겨지고, 피봇보다 큰 요소는 모두 피봇의 오른쪽으로 옮겨진다. 이 상태에서 피봇을 제외한 왼쪽 리스트와 오른쪽 리스트를 각각 정렬하면 전체 리스트가 정렬된다. 맨 마지막 요소를 pivot으로 하는 경우 - 첫번째 알고리즘 i는 left-1부터, j는 left부터 시작하여 이동한..

삽입정렬이란? 배열의 두번째 원소부터 시작해서 오름차순 혹은 내림차순으로 정렬했을 때 알맞은 자리를 찾고, 오름차순일 경우에 삽입하고자 하는 수보다 큰 수들을 뒤로 밀어낸다. 그리고 알맞은 자리에 넣고자 하는 수를 삽입하고, 이 과정을 수가 모두 정렬될 때까지 반복하는 방법이 삽입 정렬이다.(내림차순일 경우 작은 수들을 뒤로 밀어냄) void insertion_sort(int list[], int n) { int i, j, k; int temp; for (i = 1; i ..

버블 정렬이란? 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이 과정이 한번 완료되면 가장 큰 값이 배열의 오른쪽 끝으로 이동한다. 버블 정렬(bubble sort)은 이러한 비교-교환 과정을 배열 전체가 정렬될 때까지 계속하는 방법이다. void bubble_sort(int list[], int n) { int i, j; for (i = 0; i list[j + 1]) { //list[j]가 list[j+1]보다 크면, 즉 오름차순으로 정렬되어있지 ..

이진탐색이란? 배열의 중앙에 있는 값을 알아내어 찾고자 하는 항목이 중앙의 왼쪽에 있는지 오른쪽에 있는지를 알아내어 탐색의 범위를 반으로 줄이는 방법 단, 배열이 반드시 정렬이 되어있어야하기 때문에 고정된 데이터에 적합하다. 위의 예시는 34를 찾는 경우이다. 1. 34는 중앙값인 27보다 크므로 오른쪽 부분에서 탐색한다. 2. 다시 오른쪽 부분의 중앙값인 38과 비교한다. 38보다 작으므로 왼쪽 부분에서 탐색한다. 3. 다시 왼쪽 부분의 중앙값인 30과 비교한다. 30보다 크므로 오른쪽 부분에서 탐색한다. 4. 다시 오른쪽 부분의 중앙값인 34과 비교한다. 찾고자 하는 값이 중앙값과 일치한다. 즉, 중앙값과 비교하면서 찾고자하는 항목이 중앙값보다 작으면 왼쪽에서 다시 중앙값과 비교하고, 크면 오른쪽에서..

순환(recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 ex 1) 팩토리얼 int factorial(int n) { if (n

최악의 경우(worst case) ★ 알고리즘의 수행 시간이 가장 오래 걸리는 경우 => 시간 복잡도의 척도 최선의 경우(best case) 알고리즘의 수행 시간이 가장 적게 걸리는 경우 평균적인 경우(average case) 알고리즘의 모든 입력을 고려하고 각 입력이 발생하는 확률을 고려한 평균적인 수행 시간 EX) 순차 탐색(sequential search)의 경우 ※ 순차탐색 : 찾고자 하는 항목을 배열의 첫 번째부터 마지막까지 비교하면서 찾아내는 탐색방법 최선의 경우 : 찾고자 하는 숫자가 배열의 맨 처음에 있는 경우 : 비교 횟수가 1번이므로 O(1) 5 9 10 17 21 29 33 37 38 43 최악의 경우 : 찾고자 하는 숫자가 배열의 맨 끝에 있는 경우 : 비교 횟수가 n번이므로 O(n..

효율적인 알고리즘을 짜려면? 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터의 자원(ex:메모리)을 덜 사용하도록 짜야한다. -> 즉, 알고리즘을 짤때 수행시간과 기억공간을 분석하여 시간 효율성과 공간 효율성을 고려해야함 공간 복잡도(space complexity) 알고리즘이 사용하는 기억 공간 분석 시간 복잡도(time complexity) ★ 알고리즘의 수행 시간 분석 => 알고리즘의 효율성을 이야기할때 주로 시간 복잡도를 고려 절대적인 수행 시간을 나타내는 것이 아닌 알고리즘을 이루는 연산이 몇 번 수행되는지를 숫자로 표시함 시간 복잡도 함수 : 연산의 수행 횟수는 보통 입력의 개수에 따라 달라지기 때문에 n에 대한 함수로 나타냄. 이 함수를 시간복잡도 함수라고 하며 T(n)으로..