코딩 오름길

깊이 우선 탐색 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) 특성을 가지는 문제들을 해결하는..

예제 1: 특정 단어로만 이루어진 문자열 검사이 문제는 문자열이 apple, banana, cherry만으로 이루어졌는지 확인하는 문제입니다. 중간에 다른 단어가 들어가면 안 됩니다.function solution(words) { const pattern = /^(apple|banana|cherry)+$/; // apple, banana, cherry만 반복 가능 return words.filter(word => pattern.test(word)).length;}console.log(solution(["apple", "banana", "applebanana", "cherrycherry"])); // 4console.log(solution(["apple", "orange", "banana"])); // ..

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(): 큐의..

큐(Queue)란?큐는 FIFO(First In First Out) 방식으로 데이터를 처리하는 자료구조입니다.데이터가 들어가는 순서대로 처리되는 특성을 가집니다.일반적인 작업 처리 순서나 요청을 순차적으로 처리하는 시스템에서 자주 사용됩니다.비교항목큐(Queue)메모리 구조선형 구조 (배열 또는 연결 리스트 기반)접근 속도O(1) (양 끝에서만 접근 가능)삽입/삭제 속도O(1) (앞에서 삭제, 뒤에서 삽입)메모리 사용량데이터를 저장정렬기본 제공되지 않음큐(Queue)의 주요 연산 enqueue: 큐에 데이터를 추가하는 연산dequeue: 큐에서 데이터를 제거하고 반환하는 연산peek: 큐에서 가장 앞에 있는 데이터를 반환 (제거하지 않음)isEmpty: 큐가 비어있는지 확인하는 연산size: 큐에 들어있..

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