순열 알고리즘 in JS 과정 설명 첫번째 if이 재귀를 빠져나오는 조건인데 요소(selectNumber)가 1개가 되면 각각의 요소를 리턴하게 된다. 순열을 할 배열을 forEach문으로 돈다. 배열의 첫번째 값부터 차례대로 fixer에 저장하고 그걸 제외한 res
깊이 우선 탐색의 기본이 되는 형태이다.1번 노드부터 7번 깊이 우선 탐색하는 코드이다.재귀 호출 앞 뒤 위치에 따라 전위, 중위, 후위 순회가 된다.재귀 앞 코드는 재귀가 실행되기 전에 실행이 되는 거고 재귀 두 코드는 재귀가 끝까지 돌고 리턴을 만나서 돌아오면 그
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.left(start) , mid, right(end), 3가지 변술르 이용하여 원하는 데이터를 찾는다.O(logN)의 시간복잡도를 가진다.자바스크립트를 이용한 구현Parametric Sea
그리디 알고리즘 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.(동적 프로그래밍은 후에 기술 예정) 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다. 매 순간 최적의 해를 선택하며, 현재의 선택이 나중
따로 정해진 이름이 있는 알고리즘이라기 보단 문제를 접해보니 비슷한 패턴이 보여서 정리해두려고 글을 쓴다.기본 패턴이다. 내부함수에 Level 변수를 이용해 깊이 탐색을 하는 방식이고 참여하는 경우와 참여하지 않는 케이스를 나눌 때 사용하면 쉽게 문제를 풀 수 있다.앞
이진트리 : 각 노드가 최대 두 개의 자식을 갖는 트리 즉 자식이 없거나 한 개 이거나 두 개만을 갖는다.트리의 순회는 알고리즘 파트에 정리해뒀다. 완전 이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리이다. 노드는 왼쪽 자식 노드부터 채워져야한
한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조한 줄로 눕혀진 탑을 생각하면 이해가 편하다.pop : 스택의 마지막 요소를 제거한다.push : 스택의 가장 윗부분에 요소를 추가한다.top : 스택의 가장 위에 있는
스택과 달리 먼저 들어간데이터가먼저 나오는 선입선출 자료구조 FIFO(First In First Out) enqueue (add) : 큐의 끝 부분에 요소를 추가한다.dequeue : 큐의 첫번째 요소를 제거한다.front : 큐의 가장 앞 요소를 출력한다.back :
중복되는 원소가 없는 비선형 구조인덱스로 접근하지 않는다.Js 내장 객체가 존재하지만 따로 구현해보려고 한다.add : 원소 추가, 중복 원소는 추가하지 않는다.remove : 특정 원소를 삭제한다.clear : 모든 원소 삭제
다익스트라(Dijkstra) 다이나믹 프로그래밍을 활용한 대표적인 최단거리 알고리즘 선형 탐색을 활용한 다익스트라 알고리즘 선형 탐색을 이용한 다익스트라 알고리즘이다. 출발 노드를 설정한다. 출발 노드 기준으로 각 노드의 최소 비용을 저장한다. 방문하지 않은 노드
DFS(깊이 우선 탐색)을 통해 가능한 모든 경로를 탐색한다.모든 경로를 탐색하는 과정에서 특정 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지않고 되돌아 간다.이 과정을 가지치기라고 한다. 가지치기를 잘하느냐에 따라 효율성이 결정이 된다.유명한 백트래킹 문제로
배낭 알고리즘이라고도 한다. 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 베낭에 넣을 때, 가치의 합이 최대가 되도록 고르는 알고리즘이다.가방에 15kg까지 담을 수 있고, 세가지 물건이 있을 때 가치를 최대로 하려면 어떤 물건을
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.dpi는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미한다.이런 배열이 존재할
각기 다른 크기의 원판들과 판 위에 세워진 세개의 막대로 구성된다. 원판의 순서를 유지한 채 마지막 막대로 옮기는 문제이다. 작은 원판 위에 큰 원판이 올 수 없다. 이러한 과정을 거쳐 간다.n 개의 원판을 옮기는 함수이다.n개의 원판을 1번 기둥에서 3번 기둥으로 옮