코딩 오름길

깊이 우선 탐색 DFS란?- 트리나 그래프를 탐색하는 기법 중 하나로, 시작 노드에서 자식의 노드들을 순서대로 탐색하면서 깊이를 우선으로 탐색하는 알고리즘- 깊이를 우선시하여 모든 경우의 수를 탐색하기 때문에, 완전탐색 알고리즘에 속하기는 하지만, 항상 완전탐색으로는 사용되지 않음- DFS는 주로 반복문을 활용하거나 재귀문을 통하여 구현- ex) 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것 1. 시작 노드에 방문한다. (무한 루프를 돌지 않기 위해 방문 여부 체크 필수!)2. 시작 노드와 인접한 노드 중 하나를 방문하여 인접 노드를 시작 노드로 다시 DFS를 진행한..

너비 우선 탐색(Breadth First Search)란?트리나 그래프를 탐색하는 기법 중 하나로, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로 깊게 탐색하기 전에 넓게 탐색하는 것이다.두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.미로 찾기 등 최단 거리를 구해야 할 경우 사용된다. 루트에서 시작한다 -> 큐: 1자식 노드들은 [1]에 저장한다. -> 큐: 2 3 4[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. -> 큐: 3 4 5[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. -> 큐: 4 5 6 7위의 과정을 반복한다.모든 노드를 방문하여 탐색을 마친다. Java..

그리디 알고리즘(탐욕법, Greedy Algorithm)이란"매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘이다그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다. 노드에서 가장 합이 높은 방법을 선택하는 방법은? 브루트 포스로 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 경우 또는 외판원 순회 문제 문서에 나와있는 복잡한 전략을 쓸수 도 있음.일반적인 문제 해결 그리디 알고리즘을 사용할경우  그리디 알고리즘의 특징그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는..

reduce란 JavaScript에서 배열을 순회하면서 누적된 값을 계산할 수 있게 도와주는 메소드입니다. 이 메소드는 배열의 각 요소에 대해 주어진 함수를 실행하며, 누적된 결과를 반환합니다. 이 함수는 배열을 하나의 값으로 축소(reduce)하는 역할을 합니다.기본 사용법reduce() 메서드는 다음과 같은 형태로 사용됩니다array.reduce(callback(accumulator, currentValue, currentIndex, array), initialValue);callback: 배열의 각 요소에 대해 실행되는 함수입니다.accumulator: 누적된 값 (처음에는 initialValue로 시작하고, 그 이후에는 이전 단계에서 반환된 값이 사용됩니다).currentValue: 현재 처리되는..

그래프(Graph)란그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조입니다. 간선은 두 노드를 연결하며, 방향이 있을 수도 있고 없을 수도 있습니다.  ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 선수 과목 등 그래프와 트리의 차이 그래프트리정의노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조그래프의 한 종류DAG(Directed Acycli Graph, 방향성이 있는 비순환 그래프)의 한 종류방향성방향 그래프(Directed),무방향 그래프(Undirected) 모두 존재방향 그래프(Directed)사이클사이클(Cycle) 가능,자체 간선(self-loop)도 가능,순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모..

해시(Hash)란- 데이터를 고정된 크기의 값으로 변환하는 함수 또는 그 값을 저장하는 자료구조입니다.- 해시 함수는 데이터를 일정한 규칙에 따라 변환하여 빠르게 조회할 수 있도록 도와주며, 해시 테이블은 이를 활용하여 데이터를 저장하는 자료구조입니다. 해시의 주요개념해시 함수 (Hash Function): 입력 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 입력값에 대해 고유한 해시 값을 생성하려고 하지만, 동일한 해시 값을 가질 가능성도 있습니다. 이를 충돌(Collision)이라고 합니다.해시 값 (Hash Value): 해시 함수의 결과물로, 일반적으로 고정 길이의 숫자 또는 문자열입니다.해시 테이블(Hash Table): 데이터를 키와 값의 쌍으로 저장하는 자료구조로, 키를 해시 함수..

데큐(Deque, Double-endend Queue)란?데큐는 "Double-ended Queue"의 약자로, 큐의 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. 일반적인 큐는 FIFO(First In First Out) 방식으로, 데이터를 한쪽 끝에서 삽입하고, 다른 한쪽 끝에서 데이터를 삭제합니다. 하지만 데큐는 양쪽 끝에서 모두 삽입 및 삭제가 가능하다는 점에서 유연성을 제공합니다. 이러한 특성 덕분에, 여러 상황에서 더 효율적이고 강력한 연산을 제공할 수 있습니다.데큐의 주요 연산enqueueFront(item): 큐의 앞쪽에 데이터를 삽입enqueueBack(item): 큐의 뒤쪽에 데이터를 삽입dequeueFront(): 큐의 앞쪽에서 데이터를 삭제하고 반환dequeueBack(): 큐의..

스택(stack)이란?- 스택은 한쪽 끝에서만 데이터를 넣고 뺄 수 있는 제한적으로 접근할 수 있는 후입선출(Last-In-First-Out) 형태의 선형 구조이다.  스택의 주요 연산Push: 데이터를 스택의 맨 위에 추가하는 연산Pop: 스택의 맨 위 데이터를 제거하고 반환하는 연산Peek(Top): 스택의 맨 위 데이터를 제거하지 않고 확인하는 연산isEmpty: 스택이 비어있는지 확인하는 연산 (boolean 타입을 반환) 스택의 구조Bottom: 가장 밑에 있는 데이터 또는 인덱스Top: 가장 위에 있는 데이터 또는 인덱스Capacity: 스택에 담을 수 있는 데이터의 총 용량Size: 현재 스택에 담겨져있는 데이터의 개수 스택의 동작원리[초기 상태](Stack이 비어있음)Push(1) → [1..

리스트란?- 리스트는 배열 기반 자료구조로, JavaScript에서 Array 객체를 통해 사용된다. 🔹 리스트 주요 연산const list = [10, 20, 30, 40, 50];// 조회 (O(1))console.log(list[2]); // 30// 삽입 (끝: O(1), 앞/중간: O(n))list.push(60); // [10, 20, 30, 40, 50, 60]list.unshift(0); // [0, 10, 20, 30, 40, 50, 60]// 삭제 (끝: O(1), 앞/중간: O(n))list.pop(); // [0, 10, 20, 30, 40, 50]list.shift(); // [10, 20, 30, 40, 50]// 탐색 (O(n))console.log(list.indexO..

배열이란?- 배열은 같은 종류의 데이터를 연속된 메모리 공간에 저장하는 자료구조- JavaScript에서 배열은 객체(Object)의 한종류로, 가변 길이를 가지며 다양한 자료형을 포함 배열의 특징- 인덱스를 기반으로 접근 가능 (0부터 시작)- 연속된 메모리 공간을 사용 (자바스크립트의 경우 내부적으로 다르게 동작할 수도 있음)- 삽입/삭제 성능이 위치에 따라 다름(끝에서 하면 빠르고, 앞에서 하면 느림) 배열 선언 방법// 기본 배열 선언const arr1 = [1, 2, 3, 4, 5]; const arr2 = new Array(5).fill(0); // [0, 0, 0, 0, 0] 배열의 시간 복잡도 배열 메서드🔹 탐색 및 조회const arr = [10, 20, 30, 40, 50];conso..