🏷️JavaScript 퀵 정렬 분할 정복 알고리즘의 하나 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 피벗이라는 기준 값을 잡아서 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합쳐서 전체가 정렬하게 되는 방법. 방법 퀵 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀)을 이용하여 다시 분할 정복 방법을 적용한다. 결합(C..
🏷️JavaScript 선택정렬 가장 작은 것을 선택해서 제일 앞으로 보내는 것을 반복하는 알고리즘 가장 기초적이고 원시적이다. 방법 첫 인덱스부터 마지막 인덱스까지 반복문을 돌린다. 원소들 중 제일 작은 원소를 찾는다. 현재 인덱스의 원소와 제일 작은 원소의 자리를 바꾼다. ⇒ 바꿀 때는 스와핑 정렬이 완료되었으므로 다음 인덱스로 넘어간다. 시간복잡도 O(N*N) ⇒ 매우 비효율적이다. 버블정렬 옆에 있는 값과 비교하여 더 작은 숫자를 앞으로 보내주는 것을 반복하는 알고리즘 가장 비효율적인 알고리즘이다. 방법 첫 인덱스부터 반복문을 돌린다. 현재 인덱스의 원소와 오른쪽 원소의 값을 비교하여 현재 원소가 더 크면 자리를 바꾼다. 인덱스를 하나씩 증가시키며 위 과정을 반복한다. 마지막 인덱스는 가장 큰 원..
feet. 반복문 불변식, 귀류법, 비둘기집 원리 알고리즘의 정당성 증명 알고리즘을 시작하기에 앞서 알고리즘의 정당성 증명이라는 것을 알아야 한다. 말 그대로 알고리즘을 증명하는 것이다. 우리가 머리로 생각한 알고리즘이 실제로 정확하게 잘 돌아간다고 보장할 수 없기 때문에 정당성을 입증해야 한다. 명제 수학적 증명을 위해서 명제를 기억해내야 한다. 부끄럽게도 고딩때 배운 건 다 까먹었다.😳 명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다. 두 조건 $P, Q$가 있을 때 "$P$이면 $Q$이다."가 명제이다. 기호로는 $P→Q $로 나타낸다. 여기서 오늘 배울 "증명"에 있어서 중요한 문제가 있다. 바로 Vacuous이다. Vacuous는 "P이면"이라는 것이 애초에 거짓인 상태이다. 이건 예를..
시간복잡도 개념 프로그램을 작성할 때 입력의 크기에 따라 프로그램의 계산 횟수가 크게 달라진다. 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이것을 알고리즘의 시간 복잡도라고 한다. 예제 자연수 N이 주어졌을 때 1부터 N까지의 합을 구하는 프로그램 만들기 [소스 1] import java.util.Scanner; public class example{ public static void main(String[] args){ int res = 0; Scanner sc = new Scanner(System.in); int N = sc.nextInt(); for(int i=1; i
