성장일기

✅ 다익스트라 알고리즘이란? 가중 그래프에서 최적의 경로를 찾을 때 사용하는 알고리즘 다익스트라라는 네덜란드 프로그래머가 20분만에 카페에서 만듬 GPS, 네트워크 라우팅 등 최적의 경로를 찾아야하는 경우에 많이 사용됨 💡 원리 및 실행과정 출발, 도착 노드를 설정 ex) 1 출발 노드부터 연결된 노드의 최소 거리 저장 ex) 1과 연결된 노드가 2, 4 이므로 두 노드에 최소 거리 저장 2(1), 4(2) 방문하지 않은 노드 중에서 가장 거리가 짧은 노드 선택 ex) 2(1), 4(2) 중 비용이 1로 적은 2 선택 선택한 노드와 연결된 노드의 최소 거리 저장 (저장한 값보다 작다면 최소로 갱신) ex) 3(4), 5(3) 3,4번 반복 ⇒ 도착 노드를 뺀 모든 노드까지의 최소 경로 알 수 있음 도착 ..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 📌 BFS (넓이 우선 탐색) 이진 트리 // 노드 형식 class Node { constructor(val) { this.value = val; this.left = null; this.right = null; } } BFS(rootNode) { if(!rootNode) return null; let queue = [rootNode]; let visited = []; let current; while(queue.length) { current = queue.shift(); visited.push(current.value); if(current.left) queue.push(curren..

들어가기 전에... 해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 최대한 간결하고 효율적이도록 만들었으며, 주어진 코드보다 좋은 코드일 것이라 생각한다! 💡 정렬별 시간·공간복잡도 정리 Algorithm Big-O (상한) Big-θ (평균) Big-Ω (하한) 공간 복잡도 버블 정렬 O(n^2) θ(n^2) Ω(n) O(1) 삽입 정렬 O(n^2) θ(n^2) Ω(n) O(1) 선택 정렬 O(n^2) θ(n^2) Ω(n^2) O(1) 합병 정렬 O(n log n) θ(n log n) Ω(n log n) O(n) 퀵 정렬 O(n^2) θ(n log n) Ω(n log ..

1. 주어진 str를 거꾸로 나열하는 함수를 작성하시오. ex) 'awesome' => 'emosewa' 나의 풀이 function reverse(str){ if(str.length === 1) return str; return str[str.length-1] + reverse(str.slice(0,-1)); } 모범 풀이 function reverse(str){ if(str.length true 나의 풀이 function isPalindrome(str){ function helper(str) { if(str.length === 1) return str; return str[str.length-1] + helper(str.slice(0,-1)); } if(str === hel..

📌 Sliding Window (기준점 간 이동) 배열 속 연속한 값을 이용해서 답을 도출하는 문제 예시 배열 속 n만큼 연속한 숫자들의 합 중, 최대값 구하기 ⇒ 맨 처음부터 n개의 연달은 숫자의 합을 구하고, 두 개의 포인터를 이동해가며 (i-n, i) 앞꺼는 빼고, 뒤는 더해주면서 합계 비교 if(arr.length < n) return null; let maxSum = 맨 처음 연달은 n개의 값의 합 let tempSum = maxSum; // 비교할 임시값 for (let i = n; i < arr.length; i++) { // maxSum에 더한 수 바로 다음 값부터 순회 tempSum = tempSum - arr[i-n] + arr[i]; maxSum = Math.max(maxSum, te..

📌 Multiple Pointers (다중 포인터) 배열 속의 값을 비교해서 답을 도출할 때 사용 (주로 쌍으로 비교) 예시 양쪽 끝에 포인터 배치 오름차순으로 정렬된 배열 요소 중, 합치면 0이 되는 두 요소를 찾아 배열로 반환 ex) [-2,1,0,2] ⇒ return [-2, 2] best 양쪽 끝에서 출발하는 포인터 설정 후, 비교하고 포인터 변경하면서 값 찾기 let left = 0; // 왼쪽에서 출발하는 인덱스 let right = arr.length -1 // 오른쪽 출발 인덱스 while(left 0) right -..

✅ frequency counter(빈도 카운터)란? 주어진 배열 속 요소의 빈도를 확인하는 문제 worst : 중첩 for문 best : 객체 사용 의사코드 A배열의 각 요소의 제곱이 B요소에 포함되었는지 확인하시오 (갯수도 같아야 함) 👍best 시간 복잡도 : O(n) A 순회해서 {요소: 개수, ...} 객체 만듬 B 순회해서 {요소: 개수, ...} 객체 만듬 A객체의 key 순회해서 B객체 값과 비교 같지 않으면 return false 순회 마쳤으면 return true 👎worst 시간 복잡도 : O(n^2) for A 순회 B.indexOf(n) 찾아서 삭제 없으면 return false 순회 마쳤으면 return true 문제 풀이 주어진 두 숫자가 같은 숫자, 같은 빈도를 가지고 있는지..

✅ 다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 쪼개 결과값을 저장해서 점차 큰 문제를 해결하는 방식 💡 사용 조건 Overlapping Subproblems (겹치는 부분 문제) 동일한 작은 부분이 반복하여 나타나야 함 Optimal Substructure (최적 부분 구조) 작은 문제의 최적 결과 값을 사용해 큰 문제의 최적 결과값을 낼 수 있는 경우 💡 다른 알고리즘과의 차이점 재귀 재귀는 단순히 작은 문제들을 반복적으로 불러내어 비효율적임. 다이나믹 프로그래밍은 문제를 해결한 값을 저장해서 다시 호출하지 않음. 분할 정복 분할 정복도 큰 문제를 작은 문제로 쪼개 해결하지만, 작은 문제들이 중복되지 않고 독립적 📌 예시 - 피보나치 수열 피보나치 수열은 F(0) = 0, F(1) = 1일 때, ..

A에 있는 모든 원반을 B로 옮기는 횟수의 최소값을 구하는 알고리즘 제한조건 작은 원반 위에 큰 원반이 올라갈 수 없다. 한 번에 원반 하나만 옮길 수 있다. 🔑 설명 얄팍한 코딩사전님의 영상이 큰 도움이 되어 가져왔다. 아래 영상을 시청하고 설명을 읽으면 이해가 쉽다. B로 원반을 옮기려면, 가장 큰 원반이 맨 아래로 가는 것이 첫번째 순서다. 이게 가능하려면 그 위 원반들이 C로 옮겨져야 한다. 그래야 맨 아래 원반을 B로 옮길 수 있기 때문이다. 그들을 C로 옮기는 과정은 다시 위 과정을 반복한다. 위 과정과 똑같이 맨 아래 파란색 원반을 목적지로 옮기는 것이 우선이다. (보라색 맨 아래 원반을 없다고 생각하면 쉽다) 그러려면 위쪽 원반이 B에 순서대로 쌓여야 한다. 그래야 파란색 원반을 옮길 수 ..

주어진 넓이를 주어진 타일로 채우라는 문제인 타일링은 다이나믹 프로그래밍의 기본 알고리즘이다. 타일링은 재귀적 사고방식으로 봐야 패턴을 확인 할 수 있다. f(1), f(2), f(3) ... 같이 순차적으로 값을 파악하기보다 f(n), f(n-1), f(n-2) 같이 ... 역순으로 파악하며 구조와 패턴을 찾아야 한다는 것이다. 타일링의 패턴을 찾으려면 거쳐야 하는 과정을 다음과 같다. 맨 마지막에 들어갈 수 있는 타일의 경우의 수 찾기 -> 넓이가 증가할 때마다 나타나는 특이 케이스 찾기 가장 기본인 2xn 타일링부터 더 큰 넓이까지 차례대로 따라가보자. (이해를 돕기 위해 그림을 그렸으나... 그림판 발그림이라는 것을 감안해주세요) 📌 2xn 타일링 2x1 크기의 직사각형 타일을 이용해 2xn 넓이..