🏷️JavaScript 퀵 정렬 분할 정복 알고리즘의 하나 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 피벗이라는 기준 값을 잡아서 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합쳐서 전체가 정렬하게 되는 방법. 방법 퀵 정렬은 다음의 단계들로 이루어진다. 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀)을 이용하여 다시 분할 정복 방법을 적용한다. 결합(C..
🏷️JavaScript 선택정렬 가장 작은 것을 선택해서 제일 앞으로 보내는 것을 반복하는 알고리즘 가장 기초적이고 원시적이다. 방법 첫 인덱스부터 마지막 인덱스까지 반복문을 돌린다. 원소들 중 제일 작은 원소를 찾는다. 현재 인덱스의 원소와 제일 작은 원소의 자리를 바꾼다. ⇒ 바꿀 때는 스와핑 정렬이 완료되었으므로 다음 인덱스로 넘어간다. 시간복잡도 O(N*N) ⇒ 매우 비효율적이다. 버블정렬 옆에 있는 값과 비교하여 더 작은 숫자를 앞으로 보내주는 것을 반복하는 알고리즘 가장 비효율적인 알고리즘이다. 방법 첫 인덱스부터 반복문을 돌린다. 현재 인덱스의 원소와 오른쪽 원소의 값을 비교하여 현재 원소가 더 크면 자리를 바꾼다. 인덱스를 하나씩 증가시키며 위 과정을 반복한다. 마지막 인덱스는 가장 큰 원..
힙 트리 우선순위 큐를 위해 만들어진 자료구조 최소 값이나 최대 값을 빠르게 찾아내기 위해 완전 이진 트리를 기반으로 한 자료구조 우선순위 큐 : 우선순위 개념을 큐에 도입한 자료구조. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나간다. 반 정렬 상태 완전 이진 트리의 일종 중복 값을 허용 종류 최대 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙 : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 구현 힙 구현의 표준은 배열이다. 부모와 자식 인덱스는 항상 정해져 있다. 왼쪽 자식 index = (부모 index) * 2 오른쪽 자식 index = (부모 index) * 2 + 1 부모 index = (자식 inde..
트리 노드들이 나뭇가지처럼 연결된 비선형 계층적 자료구조 그래프의 한 종류이다. 하나의 루트 노드와 0개 이상의 하위 트리 비선형 자료구조 : 데이터를 순차적으로 저장하지 않음 재귀적 자료구조 : 트리 내에 또 다른 트리가 있다. loop가 없는 연결 무방향 그래프 모든 자식 노드는 하나의 부모 노드만 갖는다. 노드가 n개인 트리는 항상 n-1개의 간선을 가진다. 관련 용어 노드(Node) : 그래프의 정점 루트 노드 : 트리의 기준이 되는 노드. 나무의 뿌리를 생각하면 된다. 루트 노드에서 가지가 뻗어나가는 이미지. 부모 노드 : 자신과 인접한 노드들 중 루트 노드로 향하는 노드 자식 노드 : 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드 단말 노드 : 자식 노드가 존재하지 않는 노드..
그래프 노드와 그 노드를 연결하는 간선을 모아 놓은 자료구조 즉, 연결된 객체 간의 관계를 표현하는 자료구조 관련 용어 정점(vertex) : 위치라는 개념. node라고도 부름 간선(edge) : 위치 간의 관계. 즉, 노드를 연결하는 선. link, branch라고도 부름 인접 정점 : 간선에 의해 직접 연결된 정점 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진입 차수(내차수) : 방향 그래프에서 외부에서 오는 간선의 수 진출 차수(외차수) : 방향 그래프에서 외부로 향하는 간선의 수 경로 길이 : 경로를 구성하는 데 사용된 간선의 수 단순 경로 : 반복되는 정점이 없는 경로 (한붓그리기) 사이클 : 단순 경로의 시작과 종료 정점이 동일한 경우 그래프 구현 방법 1. 인접 행렬(2차원..
스택(Stack) LIFO(Last In First Out) 구조로, 가장 나중에 들어온 게 먼저 나간다. 맨 위만 바라보는 구조 ex) 뒤로가기(ctrl+Z) 사용 스택 구현체 없음 Array.prototype 사용 arr.push() // 삽입 arr.pop() // 삭제 // peek()은 없음! 배열의 마지막 인덱스로 접근 큐(Queue) FIFO(First In First Out) 구조로, 가장 먼저 들어온 게 먼저 나간다. 맨 아래에서만 꺼낼 수 있음 ex) 인터넷 쇼핑 배송, 마트 진열 사용 큐 구현체 없음 Array.prototype 사용 arr.push() // 삽입 arr.shift() // 삭제 // peek()은 없음! 배열의 0 인덱스로 접근
연결리스트 순서가 있는 데이터들을 저장할 때 그 다음(이전) 순서의 데이터가 있는 주소를 현재 데이터에 포함시키는 방식으로 자료를 저장하는 구조 노드 연결 리스트에서 노드는 데이터와 포인터를 가지는 객체를 의미 포인터 : 다음 노드의 주소 각 포인터 변수의 주소도 따로 존재한다. 장점 필요할 때마다 데이터를 생성하여 연결하면 되기 때문에 메모리 효율 좋음 삭제 및 추가 시 데이터 재구성 용이 단점 탐색 시 느림 (처음 또는 마지막 노드 탐색은 빠름) 구현이 까다롭다 데이터를 저장할 공간 뿐만 아니라 다음 노드의 주소를 저장하는 공간이 추가적으로 필요 사용 자바스크립트에서는 포인터가 없다. 때문에 객체를 참조하는 방식으로 구현 (오히려 더 간단하다) 연결리스트 구현 function Node(val) { t..
Hash Table Hash 고유한 데이터를 다루는 기법 또는 고유한 값 key-value 구조이다. hash table에서 hash는 해시 함수를 통해 만들어진 고유한 값이다. Hash Function 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수 함수 내부적인 패턴에 의해 고유한 값(hash)이 생성되어 반환된다. Input : key // output : Hash 이렇게 나온 해시가 저장위치가 된다. Hash Table 해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시 값을 주소 또는 색인 삼아 데이터를 key와 함께 저장하는 자료구조 자바스크립트에서 Object, (Map, Set) 시간복잡도 : O(1) 아래 구조로 되어있다. 구성 key : 고유한 값. Input key..
feet. 반복문 불변식, 귀류법, 비둘기집 원리 알고리즘의 정당성 증명 알고리즘을 시작하기에 앞서 알고리즘의 정당성 증명이라는 것을 알아야 한다. 말 그대로 알고리즘을 증명하는 것이다. 우리가 머리로 생각한 알고리즘이 실제로 정확하게 잘 돌아간다고 보장할 수 없기 때문에 정당성을 입증해야 한다. 명제 수학적 증명을 위해서 명제를 기억해내야 한다. 부끄럽게도 고딩때 배운 건 다 까먹었다.😳 명제는 참, 거짓을 판단할 수 있는 문장이나 식을 뜻한다. 두 조건 $P, Q$가 있을 때 "$P$이면 $Q$이다."가 명제이다. 기호로는 $P→Q $로 나타낸다. 여기서 오늘 배울 "증명"에 있어서 중요한 문제가 있다. 바로 Vacuous이다. Vacuous는 "P이면"이라는 것이 애초에 거짓인 상태이다. 이건 예를..
