bright jazz music

그래프와 이진 힙을 사용한 우선순위 큐를 알아야 한다. 다익스트라 알고리즘의 목적은 그래프의 두 정점(vertex) 사이에 존재하는 최단 경로를 찾는 것이다.- 서울에서 부산으로 가는 최단경로(GPS)- 인간 사이의 바이러스의 감염 경로- 목적지까지의 가장 저렴한 경로 이를 위해 선행되어야 하는 작업은 두 정점 사이에 가중치(예를 들면 거리) 가 존재하도록 해야 한다는 것이다. 이전 포스팅에서는 양방향 무가중치 그래프만을 다뤘다. 그래프(Graph)무방향 그래프를 인접 리스트로 구현한 예시.class Graph { constructor() { this.adjacencyList = {}; // 인접리스트 생성 } /* 정점(노드) 추가 */ addVertex(vertex) { // 인접리스트에 입력한 정점..

1. 브루트 포스 알고리즘브루트포스 알고리즘- 모든 가능한 경우의 수를 탐색하여 문제를 해결하는 방법이다- 가장 단순하고 직관적인 문제 해결 방식이다- 완전 탐색이라고도 한다장점:- 구현이 쉽고 단순하다- 확실하게 정답을 찾을 수 있다단점:- 시간복잡도가 높다 (대부분 O(n²), O(2ⁿ) 등)- 데이터가 커지면 시간이 기하급수적으로 증가한다간단한 예제// 1. 배열에서 두 수의 합이 target이 되는 조합 찾기function findTwoSum(arr, target) { for(let i = 0; i 브루트 포스가 주로 사용되는 경우:1. 문제의 크기가 작을 때2. 더 효율적인 알고리즘을 찾기 어려울 때3. 여러 알고리즘의 결과를 검증할 때4. 최적화 문제를 해결할 때실제 코딩테스트나 알고리즘..

백트래킹은 가능한 모든 해결책을 탐색하면서, 현재 선택이 잘못된 방향으로 가고 있다고 판단되면 이전 단계로 돌아가서(백트랙) 다른 선택을 시도하는 알고리즘이다. N-Queen 문제를 대표적인 예로 들 수 있다. N-Queen 문제는 체스판 위에 N개의 퀸을 배치하는 문제이다. 어떤 두 퀸도 같은 행, 열, 또는 대각선에 위치하지 않도록 하는 모든 가능한 배치를 찾는 것이다. 만약 같은 행, 열, 대각선에 하나라도 위치하게 된다면 일치한 퀸은 서로가 공격할 수 있는 상황에 노출된다. 이 문제에서는 각 행에 퀸을 배치하면서 이미 배치된 퀸과 충돌하지 않는 위치를 찾는다. 만약 충돌하지 않는 위치가 없다면 그 행에 대한 배치를 포기하고 이전 행으로 돌아가 다른 위치를 시도한다. 이러한 방식을 시도하면 모든 가..

탐욕법(Greedy Algorithm)은 각 단계에서 그 순간에 최적이라고 생각되는 선택을 하는 알고리즘이다.  탐욕법의 주요 특징:단순성: 구현이 비교적 간단다지역적 최적: 각 단계에서 최적의 선택을 한다빠른 실행: 일반적으로 실행 속도가 빠다주의할 점:탐욕법이 항상 최적의 해를 보장하지는 않다특정 문제에만 적용 가능하다탐욕법이 잘 동작하는 다른 예제들:회의실 배정 문제크루스칼 알고리즘(최소 신장 트리)허프만 코딩 가장 대표적인 탐욕법 예제가 "거스름돈 문제"이다. function getChange(amount) { // 사용 가능한 동전들 (큰 단위부터 정렬) const coins = [500, 100, 50, 10]; const result = []; for (l..

동적 프로그래밍은 하나의 문제를 여러 개의 작은 문제로 나누어 해결하고 해당 결과를 저장한 후에 더 큰 문제를 해결할 때 사용하는 방법론이다. 따라서 알고리즘이라기보다는 문제 해결 방법론으로 보는 관점도 있다. 동적 프로그래밍은 개발자의 관점에서 볼 때, '큰 문제'에 중점을 두어야 한다. '큰 문제'가 있어야 동적 프로그래밍의 효율성이 극대화 된다. 즉, 동적계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 특징:작은 문제의 해결책을 저장(메모이제이션)하여 재사용중복 계산을 피함으로써 성능 향상상향식(bottom-up) 또는 하향식(top-down) 방식으로 구현 가능피보나치 수열을 예로 들어 보면,// 일반적인 재귀 방식 (비효율적): n이 커질수록 함수가 재귀적으..

깊이우선탐색과 너비우선탐색은 그래프 데이터를 탐색하는 강력한 두 가지 알고리즘이다. 이 두 방식의 초점은 정점(vertex 또는 node)에 있다. 모든 정점을 순회하거나 정점 사이의 최단 거리를 찾아내는 것이다. 반면 최소신장트리는 정점을 이어주는 '간선'을 위한 알고리즘이라 할 수 있다.  MST는 아래의 경우 주로 사용된다.네트워크 설계 (최소 비용으로 모든 지점 연결)도로 건설 (최소 비용으로 모든 도시 연결)전기 회로 설계파이프라인 설계네트워크 비용 계산 및 최적화:통신망을 배치할 때마다 얼마나 비용이 들어갈 수 있는지 계산할 수 있다. 이는 최소신장트리가 간선 가중치의 합이 최소인 트리를 구성할 수 있기 때문이다. 효율적 전력망:A에서 B까지 전기를 보내야 할 때 가장 빠르고 저렴한 공급 경로..

BFS는 그래프나 트리 구조에서 노드를 탐색하는 알고리즘으로, 루트 노드(혹은 시작 노드)에서 시작하여 인접한 노드들을 먼저 탐색하는 방식이다. 주요 특징:큐(Queue) 자료구조를 사용같은 레벨(depth)에 있는 노드들을 먼저 탐색최단 경로를 찾는 문제에서 많이 사용됨BFS의 실제 활용 사례:최단 경로 찾기 (예: 네비게이션)웹 크롤링SNS에서 친구 추천 시스템네트워크 탐색아래 코드는 A 노드에서 출발하여 BFS를 하는 과정을 출력한다.// 그래프를 인접 리스트로 표현const graph = { A: ['B', 'C'], B: ['A', 'D', 'E'], C: ['A', 'F'], D: ['B'], E: ['B', 'F'], F: ['C', 'E']};function..

깊이우선 탐색은 그래프나 트리 구조에서 가능한 한 깊이 탐색하다가, 더 이상 탐색할 수 없을 때 다른 경로로 돌아가서 탐색을 계속하는 알고리즘이다. DFS의 주요 특징:한 방향으로 끝까지 탐색한 후 다음 경로를 탐색한다.재귀 또는 스택을 사용하여 구현할 수 있다.시간 복잡도는 O(V + E)입니다. (V: 정점 수, E: 간선 수)DFS의 활용 사례:미로 찾기위상 정렬연결 요소 찾기순환 감지경로 찾기실제로 사용할 때는 방문한 노드를 표시하는 것이 중요하며, 무한 루프를 방지하기 위해 visited 세트를 사용한다. // 인접 리스트를 사용한 그래프 구현const graph = { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], '..

이진탐색은 데이터를 반으로 나눠가면서 데이터를 찾는 방식을 뜻한다.이진탐색은 특성상 데이터가 정렬된 상태여야 한다. 데이터가 정렬된 상태라면 아래의 순서로 진행한다. 1단계: 전체 배열의 중간 인덱스의 원소와 검색값을 비교한다.2단계: 검색값이 배열의 좌우 중 한 곳에 포함되면 다시 1단계를 반복한다. 즉, 중간을 자르고 크기를 비교하는 것을 반복하는 것이 이진탐색 알고리즘이며, 선형탐색보다 검색 횟수가 적기 때문에 시간 복잡도에서 우위가 있다. // 중앙 값을 구해서 나머지를 버린다.(이 때문에 mid가 left값과 더 가까울 수 있음)// 배열에서 mid인덱스 값이 타겟값인 경우 리턴한다.// mid인덱스 값이 타겟보다 작으면 mid에 1을 더한 값을 left에 할당한다. 새로 만들 mid값을 오..

모든 데이터를 찾아 보는 가장 단순하면서도 직관적인 방법이다. //pnpm exec ts-node codeTest.tsconst dictionary = [ { word: 'a', mean: '라틴 문자의 첫 번째 글자' }, //...];function findMean (keyword, array) { for (let i = 0; i el.word === 'a');console.log(result?.mean);// 라틴 문자의 첫 번째 글자 하나의 반복문을 돌면서 주어진 값이 나올 때까지 검색하는 방식이다. 그러므로 선형 탐색의 시간 복잡도는 O(n)이라 할 수 있다. 자바스크립트에서는 선형 탐색을 사용해 배열에서 원하는 값을 반환받는 메서드가 존재한다. Array.prototype.find() 이..