1. 병합정렬이란 https://visualgo.net/en/sorting 병합 정렬 또한 대표적인 분할 정복 방법을 채택한 알고리즘 일단 반으로 쪼갠 뒤 나중에 합치는 알고리즘으로 퀵 정렬과 달리 정확히 반씩 쪼개서 값을 정렬 → O(N * logN) 보장 퀵 정렬은 값에 따라서 편향되게 분할할 가능성이 있음 항상 반으로 쪼개기 때문에 퀵정렬과 달리 피벗값이 없음 리스트를 더 이상 나눌 수 없을 때까지 반으로 나눔(분할) 오름차순으로 정렬하면서 병합 이미지 출처 : https://commons.wikimedia.org/wiki/File:Merge_sort_algorithm_diagram.svg import java.util.ArrayList; import java.util.Arrays; import j..
1. 재귀함수란 자기 자신을 호출하는 메서드로 특정 조건이 없다면 무한 반복함 특정 조건에 해당하면 더 이상 호출하지 않도록 해야 함 고급 정렬 알고리즘에서는 재귀용법을 많이 사용함 재귀함수는 전형적인 스택 예) Factorial 구현 public class Factorial{ public int factorialFunc(int n){ if(n > 1){ return n * this.factorialFunc(n - 1); } else{ return 1; } } } 2. 재귀함수의 형태 2가지 function(입력) { if(입력 > 일정값){ // 입력값이 특정 값보다 크명 return function(입력 - 1); // 재귀 함수 호출 }else{ return 특정 값; // 재귀함수 호출 종료 } ..
1. 퀵 정렬이란 https://visualgo.net/en/sorting 선택, 버블, 삽입 정렬은 데이터가 1만개만 넘어가도 사용하기가 어려운 시간복잡도를 가진 알고리즘이다 퀵 정렬은 분할 정복 알고리즘을 사용하여 원소들을 나누어서 계산한다. 특정 값을 기준(= 기준값 = Pivot)으로 반으로 나눔(pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 모으는 함수를 만듦) 피벗은 왼쪽 끝, 오른쪽 끝, 중간으로 선택하여 사용할 수 있다. 피벗을 기준으로 왼쪽에서는 피벗보다 큰 값을 찾고 오른쪽에서부터는 피벗보다 작은 값을 찾는다. 찾은 값을 바꾼다 2, 3을 반복한다 2, 3을 반복하다가 인덱스가 같아지거나 엇갈리는 때가 생기는데 그러면 해당인덱스와 피벗을 바꾼다. 바꾼 후 인덱스를 하나씩 증가/감소..
https://visualgo.net/en/sorting 1. 삽입 정렬 각 숫자를 적절한 위치에 삽입하는 방법 → 무조건 위치를 바꾸는 선택정렬과 버블정렬과는 달리 필요할 때만 위치를 바꿈 → 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교해서 자신의 위치를 찾아서 삽입 → 5를 기준으로 봤을 때 들어갈 수 있는 곳은 → _ 1 _ 10 _ → 이렇게 3군데 중 가운데 삽입 → 7의 경우 1 5 8 10 으로 앞부분이 정렬되어 있음 → 1 5 7 8 10 이렇게 삽입 2번째 인덱스부터 시작하여 해당 인덱스(key) 값과 앞의 인덱스 값을 비교해서 key가 더 작으면 앞으로 이동 → key값보다 더 큰 값을 만날때까지 반복 → 큰 데이터 값을 만난 위치 바로 뒤로 key값을 이동 2. 시간 복잡..
https://visualgo.net/en/sorting 1. 선택 정렬이란 주어진 데이터 중 최소값을 찾은 후 선택해서 제일 앞으로 보내는 알고리즘 → 맨 앞을 제외한 나머지 데이터들로 반복 비효율적인 알고리즘 중 하나로, 처리해야할 개수가 많은 경우 피해야할 알고리즘임 데이터의 개수가 조금만 커져도 연산의 개수가 엄청나게 커짐 2. 시간 복잡도 : O(N^2) 반복문이 2개 -> O(N^2) 1번 반복 할 때마다 집합의 크기가 1씩 줄어듦 → 10 + 9 + 8 + ... + 1 = 10 * (10 + 1) / 2 = 55번의 비교연산을 해야 함 → n * (n + 1) / 2 → 수가 엄청나게 커지게 되면 덧셈과 나누기2 정도는 별 의미가 없음 → n * n ⇒ O(n^2) public static..
https://visualgo.net/en/sorting 1. 버블 정렬이란 : 옆에 있는 값과 비교해서 작은 값을 반복적으로 앞으로 보내는 알고리즘 한 번의 반복이 끝나면 가장 큰 값이 가장 뒤로 이동됨 구현은 가장 쉽지만 가장 비효율적인 알고리즘 → 정렬 알고리즘 중 가장 느린 알고리즘 2. 시간 복잡도: O(N^2) 선택정렬과 동일한 시간 복잡도를 가지지만 실제로는 더 느림 선택정렬은 위치를 바꾸는 연산을 최소값 비교를 하고 마지막에 1번 수행하지만 버블정렬은 매번 위치를 바꾸는 연산을 하기 때문에 실제 수행시간은 버블정렬이 더 느림 두 인접한 데이터를 비교해서 앞의 데이터가 뒤의 데이터보다 크면 자리를 바꾸는 알고리즘 뒤에서부터 큰 수부터 정렬됨 n개의 리스트가 있는 경우 최대 n-1번의 반복문 ..
