문제 출처 Lv.2 연속된 부분 수열의 합- JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/178870 문제 설명 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작..
투 포인터(Two Pointer) 알고리즘 투포인터 알고리즘은 이름에서도 알 수 있듯이, 두 개의 포인터를 이용해 배열이나 리스트 등의 자료구조에서 원하는 값을 찾아내는 방법입니다. 주로 정렬된 배열에서 두 수의 합, 연속된 부분 배열의 합 등을 효율적으로 찾을 때 사용됩니다. 아래는 투포인터 알고리즘의 기본 개념을 사용하여, 정렬된 배열에서 두 수의 합이 특정 값인 타겟을 만족하는 첫 번째 쌍을 찾는 자바스크립트 함수입니다. function twoPointers(arr, target) { let left = 0; let right = arr.length - 1; while (left < right) { const sum = arr[left] + arr[right]; if (sum === target) ..
문제 출처 Lv.3 네트워크 - JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/43162 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한 조건 ..
문제 출처 Lv.2 타겟 넘버 - JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/43165 DFS 풀이 https://naho199345.tistory.com/entry/f-7 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때..
BFS(Breadth-First Search) 그래프 탐색 알고리즘 중 하나로, 너비 우선 탐색이라고도 합니다. 이 알고리즘은 그래프를 너비 방향으로 탐색하여 시작 노드에서부터 레벨별로 탐색을 진행합니다. BFS는 시작 노드에서부터 가까운 이웃 노드부터 순차적으로 방문하며, 레벨별로 탐색하면서 최단 경로를 찾는 데 유용합니다. BFS의 동작 방식은 다음과 같습니다: 시작 노드를 방문하고, 방문한 노드를 큐(Queue)에 추가합니다. 큐에서 노드를 하나씩 꺼내어 방문하고, 해당 노드의 모든 이웃 노드를 큐에 추가합니다. 큐가 빌 때까지 위 과정을 반복합니다. BFS는 레벨 단위로 탐색하기 때문에, 같은 레벨에 있는 노드들을 모두 탐색한 후에 다음 레벨로 넘어갑니다. 이로 인해 시작 노드로부터의 최단 경로를..
문제 출처 Lv.2 타겟 넘버 - JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/43165 BFS 풀이 https://naho199345.tistory.com/entry/%E3%84%B7 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로..
문제 출처 Lv.2 귤 고르기 - JavaScript https://school.programmers.co.kr/learn/courses/30/lessons/138476 문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 ‘k’개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다..
다익스트라 알고리즘 네트워크에서 최단 경로를 찾는 알고리즘이며, 이 알고리즘은 엣지 가중치의 합이 최소가 되는 경로를 찾아줍니다. 즉, 그래프의 한 정점에서 다른 정점으로 가는 가장 짧은 경로를 찾는 문제를 해결하는데 사용됩니다. 1. 초기화: 시작 노드의 거리를 0으로, 나머지 모든 노드의 거리를 무한대로 설정합니다. 시작 노드를 현재 노드로 설정합니다. 2. 현재 노드에서 인접한 노드들의 거리를 계산합니다. 이 때, 기존에 설정한 거리보다 새로 계산한 거리가 짧으면 거리 정보를 업데이트합니다. 3. 모든 인접 노드에 대해 거리를 업데이트한 후에는 방문하지 않은 노드 중 거리가 가장 짧은 노드를 새로운 '현재 노드'로 설정합니다. 4. 모든 노드를 방문할 때까지 이 과정을 반복합니다. 다음과 같은 그래..
DFS(Depth-First Search) 그래프 탐색을 위한 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다. DFS는 그래프의 모든 노드를 방문하고, 각 노드를 한 번씩만 방문하며 연결된 모든 노드를 탐색합니다. DFS의 작동 방식은 다음과 같습니다: 시작 노드를 방문하고, 방문한 노드를 "방문한 노드" 목록에 추가합니다. 현재 노드와 연결된 이웃 노드들을 확인합니다. 이웃 노드들 중 방문하지 않은 노드가 있으면, 그 이웃 노드로 이동하여 재귀적으로 탐색합니다. 모든 이웃 노드를 방문했거나 더 이상 방문할 이웃 노드가 없으면, 이전 단계로 돌아가서 탐색을 계속합니다. DFS는 스택(Stack) 또는 재귀 함수를 사용하여 구현할 수 있습니다. 스택을 사용하는 경우, 방문한 노드들을 스택에 차례로 쌓..
그래프 노드(node)와 그 노드들을 연결하는 간선(edge)으로 이루어진 자료 구조입니다. 그래프는 현실 세계에서 다양한 상호 관계를 표현하는데 사용됩니다. 예를 들면 지도에서 도시들을 노드로, 도로를 간선으로 표현하는 것이 그래프의 한 예입니다. JavaScript에서 그래프를 구현하는 방법 중 가장 일반적인 두 가지 방법은 "인접 행렬"과 "인접 리스트"입니다. 인접 행렬 (Adjacency Matrix) 인접 행렬은 2차원 배열로 그래프의 연결 정보를 표현합니다. 노드 간 연결 여부를 행렬의 값으로 표현하며, 노드 수가 N개인 그래프라면 NxN 크기의 행렬이 필요합니다. 예를 들어, 노드 1과 노드 2가 간선으로 연결되어 있다면, 인접 행렬의 1행 2열과 2행 1열에 해당하는 값에 연결 정보를 표..
