망고

📍거품 정렬(Bubble Sort) 시간복잡도 : O(n^2) 공간복잡도 : O(n) -> 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되기때문 거품 정렬은 선택 정렬과 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 아래는 버블 정렬의 코드 예시이다. function bubbleSort(array) { for(i in array) { for(i in array) { if(array[i] < array[j]){ swap(array, i, j); } } } return array; } bubbleSort([6,1..

스택 가장 나중에 집어넣은 데이터를 가장 먼저 추출하는 LIFO(Last In First Out) 배열에서 push, pop이 해당한다. 가장 마지막에 있는 데이터를 확인할 수 있다.(보통 stackTop이라고 부른다) class Node { constructor(data, next) { this.data = data; this.next = null } } class Stack { constructor(top, count) { // 가장 마지막에 들어온 top에 해당하는 값 this.top = null; this.count = 0; } push() { // return 값으로는 증가한 배열의 길이를 담는다. } pop() { // return 값으로는 top에서 나온 값 그 자체를 담는다. 여기서는 da..

- 보통 재귀로 구현하며 조건이 맞지 않으면 종료한다. - DFS(깊이 우선 탐색) 기반 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 코딩에서 반복문의 횟수까지 줄일 수 있으므로 효율적이다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 즉 답이 될만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것을 백트래킹이라고 생각하면 된다. 예를 들어 A,B,C라는 사람이 각각 순서를 정할때 가능한 모든 경우의 수를 찾는 것으로 첫번째 순서가 A일경우 ,B일경우, C일경우 각각 차례대로 따지는 식이다.

완전 탐색은 모든 경우의 수를 다 시도해 보는 것으로 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게된다. 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용하다. 📍 단순 Brute-force 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법 이 방법만을 사용하는 문제는 거의 나오지 않는다. 📍 비트마스크 (Bitmask) 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두가지 선택으로 구성되는 경우 유용하게 사용 ex) '원소가 n개인 집합의 모든 부분 집합' 을 구한다고 할 경우, 각 원소가 포함되는지 포함되지 않는지를 0,1로 구분하여 배열에 저장해둘 수 있음 📍 재귀함수 비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 ..

Big-O(또는 Big-Oh) notation은 알고리즘의 시간 복잡도를 나타내는 표기법이며,알고리즘 최악의 경우 복잡도를 측정한다.나타내는 표현방식은 O(f(n))으로 나타내는데 여기에서 n은 입력의 개수를 나타낸다. 1) 빅 오 표기법 알고리즘의 복잡도를 판단하는 척도로는 시간복잡도(실행시간)와 공간 복잡도(실행공간) 두가지가 있는데, 빅 오 표기법은 시간복잡도를 다룬다. 빅 오 표기법을 고민할 때 가장 대표적으로 생각해야 할 질문이 "n이 무한으로 접근하면 무슨 일이 일어날까?" 대표적은 O(n)에 대해 예를 통해 이해해보자. O(n)은 선형시간이고, 위의 예에서 최악의 경우 i는 0부터 n-1까지 n번의 연산을 수행해야 한다. 이를 이해했다면 다음은 O(n²), O(n³)의 시간복잡도를 살펴보자...