🏷️JavaScript 퀵 정렬 분할 정복 알고리즘의 하나 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 피벗이라는 기준 값을 잡아서 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합쳐서 전체가 정렬하게 되는 방법. 방법 퀵 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀)을 이용하여 다시 분할 정복 방법을 적용한다. 결합(C..
🏷️JavaScript 선택정렬 가장 작은 것을 선택해서 제일 앞으로 보내는 것을 반복하는 알고리즘 가장 기초적이고 원시적이다. 방법 첫 인덱스부터 마지막 인덱스까지 반복문을 돌린다. 원소들 중 제일 작은 원소를 찾는다. 현재 인덱스의 원소와 제일 작은 원소의 자리를 바꾼다. ⇒ 바꿀 때는 스와핑 정렬이 완료되었으므로 다음 인덱스로 넘어간다. 시간복잡도 O(N*N) ⇒ 매우 비효율적이다. 버블정렬 옆에 있는 값과 비교하여 더 작은 숫자를 앞으로 보내주는 것을 반복하는 알고리즘 가장 비효율적인 알고리즘이다. 방법 첫 인덱스부터 반복문을 돌린다. 현재 인덱스의 원소와 오른쪽 원소의 값을 비교하여 현재 원소가 더 크면 자리를 바꾼다. 인덱스를 하나씩 증가시키며 위 과정을 반복한다. 마지막 인덱스는 가장 큰 원..
💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다. 개념 정리는 [자료구조]와 겹침 👉 문제로 직접 풀어보고 링크 남겨 둠 스택 2023.02.21 - [D • A/DataStructure] - [자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 스택(Stack) [자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 스택(Stack) ✅ 자료구조 : 데이터를 저장하는 방식 ✅ 선형 자료구조 : 한 종류의 데이터가 선처럼 길게 나열된 자료구조 랜덤 접근 불가능? 모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들 스택 (Stac jinijana.tistory.com ▶ 정의 먼저 들어간 자료가 나중에 나오는 LIFO 자료구조. 한쪽 끝에서만 데이터 삽입 삭제 가능 ▶연산자(..
💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다. 병합 정렬(Merge Sort) 분할 정복 방법으로 , 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤에 각자 계산하고 나중에 합치는 방법을 채택한다. 즉, 무조건 반으로 나누고 나중에 정렬하는 알고리즘이므로 $O(N*log_{2}{N})$을 항상 보장한다. 하지만 기존의 데이터를 담을 추가 배열이 필요하다는 점에서 메모리 활용이 비효율적일 수 있다. 백준 2750 package Y2023.March.week2; import java.util.Scanner; public class q2750 { static int[] sorted; static void merge(int[] sort, int start, int mid, int end..
💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다. 정렬(Sort)은 알고리즘의 효율성 차이를 극명하게 느낄 수 있다. 아래 배열을 1부터 10까지 오름차순으로 정렬하는 문제를 예제로 다음 정렬들을 살펴보자! int[] arr = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; 선택 정렬(Selection Sort) 선택 정렬은 첫 번째 값을 두 번째 값부터 마지막 값까지 차례대로 비교하고 가장 작은 값과 첫 번째 값을 바꾼다. 두 번째 값을 세 번째 값부터 마지막 값까지 비교하여 바꾸고 이 과정을 마지막까지 반복하여 정렬하는 알고리즘이다. 이 알고리즘은 $N * (N+1) / 2$ 즉, $N^2$만큼 계산을 실행해야 한다. 따라서 시간 복잡도는 $O(N^2)$이다. 데이터의..
feet. 반복문 불변식, 귀류법, 비둘기집 원리 알고리즘의 정당성 증명 알고리즘을 시작하기에 앞서 알고리즘의 정당성 증명이라는 것을 알아야 한다. 말 그대로 알고리즘을 증명하는 것이다. 우리가 머리로 생각한 알고리즘이 실제로 정확하게 잘 돌아간다고 보장할 수 없기 때문에 정당성을 입증해야 한다. 명제 수학적 증명을 위해서 명제를 기억해내야 한다. 부끄럽게도 고딩때 배운 건 다 까먹었다.😳 명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다. 두 조건 $P, Q$가 있을 때 "$P$이면 $Q$이다."가 명제이다. 기호로는 $P→Q $로 나타낸다. 여기서 오늘 배울 "증명"에 있어서 중요한 문제가 있다. 바로 Vacuous이다. Vacuous는 "P이면"이라는 것이 애초에 거짓인 상태이다. 이건 예를..
✅그래프 순회 알고리즘 : 하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것 깊이 우선 탐색(Depth Sirst Search, DFS) 깊은 부분을 우선적으로 탐색하는 알고리즘 실행 과정 첫 정점을 방문한다. 인접한 정점 중 아직 방문하지 않은 정점을 방문한다. 이때 한 길로 쭉 파고 들어간다. 더 이상 들어갈 길이 없으면(인접한 모든 정점에 이미 방문했으면), 방문하지 않은 인접한 정점을 찾을 때까지 들어온 길을 돌아간다. 위 과정을 반복한다. 구현 1. 순환 호출 이용 재귀함수를 필요로 함. 공부 후 내용 추가 더보기 코드 출처 import java.io.*; import java.util.*; /* 인접 리스트를 이용한 방향성 있는 그래프 클래스 */ class Graph {..
순차 탐색(Sequential Search) 시작점부터 순차적으로 탐색하는 것 시간복잡도 10개의 데이터를 순차적으로 탐색했을 때 걸리는 평균 연산 횟수는 이고, 따라서 데이터의 크기가 n일 때 연산횟수는 이므로 전부 탐색했을 때 시간복잡도는 O(n)이다. 사진 출처 : https://earthteacher.tistory.com/43#gsc.tab=0 구현 for (int i = 0; i < list.size(); i++) { if(list.get(i) == searchItem) return i; } 간단하게 살펴보면 리스트(또는 배열)가 있을 때, 첫 데이터부터 하나씩 가져와서 찾는 데이터와 비교한다. 가져온 데이터가 찾는 데이터와 일치하면 인덱스를 반환한다. 이진 탐색(Binary Search) 정렬..
시간복잡도 개념 프로그램을 작성할 때 입력의 크기에 따라 프로그램의 계산 횟수가 크게 달라진다. 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이것을 알고리즘의 시간 복잡도라고 한다. 예제 자연수 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
