개발새발 민다니

백트래킹(Backtracking) 개념가능한 모든 해결책을 탐색하면서 조건에 맞지 않으면 돌아가 다시 시도한다.문제 해결을 위한 모든 경우의 수를 고려하는 동시에,조건에 맞지 않는 경로라면 더 이상 진행하지 않는 방식을 채택해 효율성을 높인다.미로에서 출구를 찾는 과정을 상상해보자.갈림길에서 길을 선택하다가 막다른 길에 도달하면 되돌아와 다른 길을 시도한다. ※ Backtrack은 '되돌아'라는 의미이다.동작방식1. 하나를 선택한다.2. 선택한 길이 유효한지 검사한다.3. 유효하다면 다음 결정 지점으로 이동한다.4. 유효하지 않다면, 이전 결정 지점으로 돌아가 다른 선택을 한다. 사용하는 경우 모든 경우의 수를 고려하면서도 불필요한 경로를 배제하기 때문에 문제를 효율적으로 해결할 수 있다.가능한 해결책의..

힙(Heap)이란? 이진 트리 구조의 하나다.주로 우선순위 큐를 구현할 때 사용한다.  - 최대 힙(Max Heap): 부모 노드가 자식 노드보다 크거나 같은 값을 가진다.  - 최소 힙(Min Heap): 부모 노드가 자식 노드보다 작거나 같은 값을 가진다.JavaScript는 힙 자료구조를 내장하지 않기 때문에,효율적으로 문제를 해결하기 위해 힙을 직접 구현해야 한다.삽입과 삭제 연산에서 O(log n)의 시간 복잡도를 유지할 수 있기 때문에효율성 측면에서 매우 효과적이다. Array.prototype.sort를 힙(Heap)으로 대체해야하는 이유기본적으로 사용하는 알고리즘의 시간 복잡도가 최선의 경우 O(n log n),최악의 경우 O(n log n)의 시간 복잡도를 가진다.이는 힙을 사용한 해결법..

완전 탐색과 탐욕법은 몇 번 사용해보면 다른 매커니즘을 통해 돌아가지만,사실 코딩테스트 학습 초반에는 꽤나 헷갈렸던 알고리즘이다. 어떤 경우에 사용하는지 간단하게 정리해보겠다. 완전탐색(Brute Force)완전탐색은 왜 Brute Force(무자비한 힘)일까?이 방법이 무차별 공격처럼 가능한 모든 경우를 하나하나 시도하기 때문이다.이러한 무식한 방법 때문에 Brute(야수, 잔인한)라는 단어가 사용되었다.힘으로 밀어붙이는 상황처럼, 가능한 모든 경우를 다 시도해본다는 의미에서 파생되었다.직관적이고 단순하지만 비효율적일 수 있다. 이 알고리즘은, 미로 안에서 출구를 찾기 위해 모든 길을 가보는 것과도 같다.모든 경로를 시도하며 출구를 찾게되면, 반드시 출구를 찾겠지만 시간이 많이 걸릴 수 있다. 조합 문..

배열과 객체, 집합(Set) 자료구조는 각기 다른 시간 복잡도를 갖는다.따라서, 적절한 상황에 적절한 자료구조를 선택할 수 있어야한다. 배열:: 빈번한 접근이 필요한 경우Access(접근)O(1)Search(탐색)O(n)Insert/Delete(삽입/삭제)O(n) 따라서 데이터가 순서대로 정렬되어있고, 특정 인덱스로 자주 접근하는 경우에 사용함. - 순차적으로 데이터에 저장하고 접근 - 학생 성적 및 목록 등 // 배열 생성let arr = [1, 2, 3, 4, 5];// 접근 (Access)console.log(arr[2]); // 3// 탐색 (Search)console.log(arr.indexOf(3)); // 2// 삽입 (Insert)arr.splice(2, 0, 10); // 2번째 인덱스에..