> 기초/알고리즘
-
TIL-2024.03.10 - BFS (너비 우선 탐색)> 기초/알고리즘 2024. 3. 10. 09:11
------- BFS 설명: BFS는 너비 우선으로 그래프를 탐색하는 알고리즘. 한 번에 한 레벨씩 탐색하며, 각 레벨에서 모든 노드를 방문한 후에 다음 레벨로 이동 BFS는 큐(queue)를 사용하여 구현 동작 원리: 시작 노드를 큐에 넣고 방문 표시. 큐가 빌 때까지 다음을 반복: > 큐에서 하나의 노드를 빼기. > 해당 노드와 인접한 모든 노드를 방문하고 큐에 넣기. 모든 노드가 방문될 때까지 반복. 특징: 최단 경로를 찾을 때 유용합니다. 메모리를 많이 사용할 수 있습니다. 큐를 사용하므로 반복적으로 구현이 쉽습니다. 예제: function bfs(graph, start) { let visited = new Set(); let queue = [start]; while (queue.length > ..
-
TIL-2024.03.09 - DFS - 깊이 우선 탐색> 기초/알고리즘 2024. 3. 10. 09:10
------- DFS 설명: DFS는 깊이 우선으로 그래프를 탐색하는 알고리즘. 이 알고리즘은 한 경로를 따라 최대한 깊이 탐색한 후, 다른 경로로 이동하여 탐색을 계속 진행. DFS는 스택(stack) 또는 재귀 함수를 사용하여 구현. 동작 원리: 시작 노드를 스택에 넣고 방문 표시. 스택이 빌 때까지 다음을 반복: 스택에서 하나의 노드를 빼기. 해당 노드와 인접한 미방문 노드 중 하나를 선택하여 스택에 넣고 방문 표시. 더 이상 진행할 수 없을 때까지 재귀적으로 반복. 모든 노드가 방문될 때까지 반복. 특징: 깊이 우선 탐색은 해를 찾을 때까지 모든 경로를 탐색. 메모리를 적게 사용. 재귀 함수 또는 스택을 사용하므로 구현이 다소 복잡. 예제: function dfs(graph, start, visi..
-
TIL-2024.03.08 - 재귀함수> 기초/알고리즘 2024. 3. 8. 13:44
------- 재귀함수 설명: 함수가 자기 자신을 호출하는 방식으로 정의되는 함수. 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복. 재귀함수로 작성이 되는 코드는 반복문으로도 작성 특징: 자기 자신을 호출: 재귀 함수는 자신을 호출 베이스 케이스(Base Case): > 재귀 함수는 무한히 호출되지 않도록 멈추는 조건이 필수. > 베이스 케이스를 지정하지 않으면 함수가 무한히 호출되며 스택 오버플로우(Stack Overflow)가 발생. 작업을 작은 문제로 분할: 재귀 함수는 하나의 큰 문제를 해결하는 대신 작은 부분 문제로 분할하고 각 부분 문제는 동일한 함수에 대한 재귀 호출을 통해 해결. 스택 사용: 재귀 함수는 호출 스택(Call Stack)을 사용하여 호출된 순서를 ..
-
TIL-2024.03.07 - 알고리즘 - 이진 탐색(Binary Search) 알고리즘> 기초/알고리즘 2024. 3. 7. 21:00
------- 이진 탐색(Binary Search) 알고리즘 설명: 이진 탐색은 정렬된 배열에서 특정 요소를 찾는 알고리즘. 배열을 반으로 나누어 탐색 범위를 반으로 줄여나가는 방식으로 동작. 이 알고리즘은 탐색 범위를 반으로 줄이기 때문에 일반적으로 선형 탐색보다 효율적으로 동작. 동작 방식: 시작, 중간, 끝 지점 설정: 배열의 시작 지점을 start, 중간 지점을 mid, 끝 지점을 end로 설정합니다. 중간 요소 검사: 배열의 중간 요소를 확인하여 찾고자 하는 값과 비교합니다. 탐색 범위 축소: 중간 값이 찾고자 하는 값보다 작으면 시작 지점을 중간 지점 다음으로 설정하고, 크면 끝 지점을 중간 지점 이전으로 설정합니다. 반복: 찾고자 하는 값이 발견될 때까지 위의 과정을 반복합니다. 예제: fu..
-
TIL-2024.02.29 - 알고리즘 - 정렬 알고리즘> 기초/알고리즘 2024. 2. 29. 23:07
------- 정렬 알고리즘 설명: 데이터를 특정한 기준에 따라 정렬하는 알고리즘 종류: 버블 정렬 (Bubble Sort) 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 퀵 정렬 (Quick Sort) 합병 정렬 (Merge Sort) 버블 정렬 (Bubble Sort): 인접한 두 원소를 비교하여 순서대로 정렬하는 방식. 시간 복잡도는 O(n^2)로 비효율적인 알고리즘, 구현이 간단. 작은 데이터나 교환 횟수가 적은 경우에 적합. 예제: function bubbleSort(arr) { let len = arr.length; for (let i = 0; i ..
-
TIL-2024.02.28 - 알고리즘 - 다이나믹 프로그래밍> 기초/알고리즘 2024. 2. 28. 21:27
------- 다이나믹 프로그래밍 - 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방법 - 각 하위 문제의 해결책을 저장하고 재사용함으로써 전체 문제의 해결책을 효율적으로 찾아냅니다 - 일반적으로, Bottom Up이 더 시간 효율적 핵심 원리: 중복된 하위 문제(Overlapping Subproblems): - 주어진 문제가 같은 작은 문제를 반복적으로 해결해야 할 때, 이를 중복된 하위 문제라 칭함 - 이러한 문제의 해결책을 한 번만 계산하고, 결과를 저장한 후 필요할 때마다 재사용함으로써 계산 시간을 대폭 감소 최적 부분 구조(Optimal Substructure): - 큰 문제의 최적 해결책이 그 문제의 하위 문제의 최적 해결책에서 파생될 수 있을 때, 이를 최적 부분 구조라 칭함 ..
-
TIL-2024.02.22 - 알고리즘 - 보물지도과 비트 연산> 기초/알고리즘 2024. 2. 22. 21:54
문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17681 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 1차 코드 const solution = (n, arr1, arr2) => { const toStringTwo = (n, arr) => { const returnArr = []; for (let i = 0; i < arr.length; i++) { const tempArrLength = arr[i].toString(2).length; const tempString = tempArrLe..