성장일기

📌 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 넓이..

📌조합 (Combination) n개 중에서 m개를 선택하는 경우의 수 (nCr = n개 중 r개의 combination) 조합은 순서 상관 없음 ⇒ [1,2] & [2,1]은 같은 것으로 취급 ex) Input: [1, 2, 3, 4] Output: [ [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4] ] 코드 구현 원리 조합을 구현하는 원리는 다음과 같다. let arr = [1,2,3,4]; // arr에서 3개를 선택하는 경우의 수 구하기 시작 1을 선택(고정) -> 나머지 [2, 3, 4] 중에서 2개씩 조합을 구함 => [1, 2, 3] [1, 2, 4] [1, 3, 4] 2를 선택(고정) -> 나머지 [3, 4] 중에서 2개씩 조합을 구함 => [2, 3, 4] 3..

📌 유클리드 호제법 for문을 돌려 찾을 수 있지만 유클리드 호제법을 알면 훨씬 간단하다. 큰 수(max)와 작은 수(min)가 주어졌을 때, 최대공약수를 구하는 과정을 아래와 같다. max % min = e(1) min % e(1) = e(2) e(1) % e(2) = e(3) ... e(n-1) % e(n) = 0 최대공약수 : e(n) 최소공배수 : (max * min) /e(n) 📌 구현 function solution(n, m) { // 최대공약수 구하는 함수 function u(i, j) { let e = i % j; if (e === 0) return j; return u(j, e); } // 최대공배수 반환 alert(u(n,m)); // 최소공배수 반환 alert(n * m / u(n,m..

개요 인터넷의 작동 원리를 이해하려면, 컴퓨터 통신의 구성요소부터 차근차근 알아가는 것이 좋다. 왜냐하면 공부를 시작하면 아래와 같은 과정을 거치기 때문이다. 📄인터넷 작동 원리는 HTTP를 전달해서... 👶 HTTP가 뭐지? → 📄 HTTP는 표준화된 프로토콜로... 👶 프로토콜은 뭐지? → 📄 프로토콜은 컴퓨터 통신을 위해 합의된 통신 약속... 👶 컴퓨터 통신? (ㄷㄷ) 인터넷은 컴퓨터 네트워크 통신을 기반으로 구현했기 때문에 HTTP, 도메인, 패킷 같은 용어로 설명될 수 밖에 없다. 그러므로 이에 대한 기본적인 이해가 필요하다. 원치 않아도 배워야 한다는 것이다! 역순으로 헤매면서 머릿속에 집어넣는 것보다 기초부터 순차적으로 배우는 것이 훨씬 효율적이다. 그럼 지금부터 컴퓨터 통신의 구성 요소,..

웹 관련 용어 정리 웹 페이지 온라인으로 볼 수 있는 단일 문서 또는 텍스트, 이미지, 비디오로 가득찬 페이지 (지금 보고 있는 것도 하나의 웹 페이지) 하이퍼링크를 통해 두 개 이상의 웹 페이지를 연결할 수 있다. 웹사이트 도메인 1개에 속해 있는 웹 페이지의 집합체 웹 페이지가 책의 페이지라면, 웹 사이트는 책 하나의 웹 사이트에 함께 링크된 웹 페이지는 일반적으로 동일한 도메인 이름(URL)을 갖는다. 예시 웹 사이트: www.google.com 웹 페이지www.google.com/drive www.google.com/image 웹 브라우저 웹 페이지의 코드를 이해하고 지시대로 구현하도록 설계된 응용 소프트웨어. 웹 서버와 쌍방향으로 통신하고 HTML문서와 파일을 출력한다. 예시: 크롬, 인터넷 익..