지난번엔 DFS문제를 만나 가볍게 다뤄본 적이 있는데 이렇게나 빨리 BFS를 만났다. BFS는 너비 우선 탐색으로 그래프 탐색 알고리즘 중 하나입니다. 시작 정점으로부터 거리가 가까운 정점부터 탐색해 나가는 방식으로, 레벨 순서대로 탐색하는 방법입니다. BFS는 큐 자료구조를 이용하여 구현할 수 있습니다. 시작 정점을 큐에 넣고, 해당 정점과 인접한 정점을 모두 큐에 넣어 탐색합니다. 그러고 나서 큐에서 하나씩 정점을 꺼내면서 그 정점과 인접한 정점을 다시 큐에 넣어 탐색을 진행합니다. 이 과정을 큐가 비어질 때까지 반복합니다. 최단 경로를 찾는 문제에서 많이 사용되며, 그래프의 정점들이 거리에 대한 정보를 가지고 있을 때 유용합니다. ex) 길찾기, 네트워크 최적 경로, 게임 맵 최단거리, 퍼즐, 탐사..
데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. ADT중 널리 쓰이는 큐, 스택,트리에 대해 알아보자 큐(Queue) - 데이터를 집어넣을 수 있는 선형(linear) 자료형이다. - 먼저 집어넣은 데이터가 먼저 나온다. (FIFO, First In First Out) - 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue - 큐는 순서대로 처리해야 하는 작업을 임시적으로 저장해주는 버퍼(buffer)로 많이 사용 쓰임 - 대기열 예) 프린터에서 인쇄 작업을 처리하는데 사용되는 대기열 - 네트워크 통신 예) 인터넷 라우터는 패킷을 수신하면 해당 패킷을 대기열에 추가하여 다음 목적지로 전송 스택..
DFS란 깊이 우선 탐색이라는 의미로 트리나 그래프에서 한 루트로 탐색하다 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 재귀호출을 사용하여 구현하지만 단순한 스택 배열로 구현하기도 한다. 갈림길이 나타날 때마다 다른길이 있다는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 갈림길까지 돌아가면서 이 길은 아님이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료된다. 👍장점 - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 결과물을 빨리 구할 수 있다. 👎단점 - 결과물이 없는 경로에 깊이 빠질 가능성이 있..
정렬알고리즘이 뭔가요? 📚특정원소들을 사전처럼 일정한 순서대로 열거하는 알고리즘입니다. 왜중요하나요? 🔎탐색에 용이합니다. 정렬이 되지 않은 숫자에서 특정 숫자값을 찾으려면 결국 하나씩 탐색을 해야합니다. 하지만 정렬이된 숫자라면 훨씬 빨리 원하는 숫자를 찾을 수 있습니다. 종류에는 무엇이 있나요? 1. 버블정렬 더보기 인접한 두개의 요소를 비교해서 조건에 따라 위치를 교환해줍니다. 배열길이보다 1번 적게 비교가 일어나며 한번 정렬이 일어나면 마지막요소는 고정되므로 그 때마다 하나 더 적게 비교가 일어나게 됩니다. 두 요소를 비교하고 교환만 이루어지므로 가장 간단하고 쉬운 정렬방법이지만 최악의 경우 모든 요소를 교환해서 시간복잡도O(n^2)가 좋지 않습니다. 저는 왼쪽에서 오른쪽으로 정렬되는 상황만 있는..
메모이제이션은 변수로 미리 배열의 값을 저장해두고 다음 인덱스의 배열을 만들때 사용할 수 있는 방법이다. 동일한 계산을 반복할때 이전에 계산한 값을 메모리에 저장해두어 불필요한 계산을 없애고 실행속도를 빠르게 한다. 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 출처 - 위키피디아 가장 흔히 사용되는 피보나치 수열을 구하는 함수를 살펴보자. let memo = [0,1] function fibonacci(n) { if(memo[n] === undefined){ memo[n] = fibonacci(n-2)+f..
set객체는 중복되지 않는 유일한 값들의 집합이다. 배열과 유사하지만 중복된요소를 가질 수 없다는점, 순서에 의미가 없다는 점, 인덱스로 접근이 불가능하다는 점이 다르다. Set은 수학적 집합을 구현하기위한 자료구조이다. 여집합, 차집합, 교집합, 합집합 등을 구현할 수 있다. Set 객체 생성 set 생성자 함수로 생성한다. 함수에 전달된 인수가 없다면 빈 Set객체가 생성된다. 중복된 배열을 인수로 준다면 저장되지 않는다. Set의 프로토타입을 살펴보면 다양한 메서드들이 있는데 이번 코플릿 문제에서 Set.has을 활용한 문제가 있었다 🏋🏽문제 두 개의 배열(base,sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴 Set.has는 Set객체에 특정 요소 존재 여부를 확인하고..
버블정렬은 배열의 한 요소와 그 다음요소의 대소를 비교한뒤 순서를 바꿔주는 정렬알고리즘이다. [1,3,2,4] [4,3,2,1] 배열의 첫번째 요소를 두번째 요소와 비교한뒤 첫번째 요소가 크다면 서로 순서를 바꾼다. 첫번째 요소: 4 두번째 요소 :3 [3,4,2,1] 두번째 요소가 크다면 바꾸지 않는다. 첫번째 요소 : 1 두번째 요소 : 3 [1,3,2,4] 두번째 요소는 세번째 요소와 크기를 비교한다. 세번째 요소가 크다면 두번째 요소와 순서를 바꾼다. 두번째요소: 3 세번째요소: 2 [1,2,3,4] 두번째요소: 4 세번째요소: 2 [3,2,4,1] 세번째 요소가 크다면 바꾸지 않는다. 세번째 요소는 네번째 요소와 크기를 비교한다. 네번째 요소가 크다면 세번째 요소와 순서를 바꾼다. 세번째요소: ..
문제 피보나치수열을 메모이제이션을 이용해 구현 나의 풀이 let memo = [0,1] function fibonacci(n) { // TODO: 여기에 코드를 작성합니다. if(memo[n] === undefined){ memo[n] = fibonacci(n-2)+fibonacci(n-1) }return memo[n] } 알게된 점 메모이제이션이란 계산된 값을 이전에 계산된 결과를 저장하는것 let memo 배열은 인덱스 값과 같이 피보나치 수열의 n=0, n=1의 값을 기억하고 n번째 값이 없을때 피보나치 수열의 값을 만들어 나갔다. 재귀는 어려워!
function stringifyJSON(obj) { // your code goes here if(typeof obj === 'number'){ return String(obj); } else if(obj === null ){ return `${obj}` }else if(typeof obj === 'string'){ return `"${obj}"` } let result = "" if(Array.isArray(obj)){ result += "["; for(let el of obj){ result += `${stringifyJSON(el)},`; } if(result === "["){ return result+"]" }else{ return result = result.slice(0, result.len..
🏋🏽문제 문자열을 입력받아 문자열에서 숫자를 모두 찾아 더한 뒤에 해당 값을 숫자와 공백을 제외한 나머지 문자열의 길이로 나눈 값을 반올림으로 리턴 🔍나의 풀이 1. 일단 문자열에 있는 숫자는 문자열이기 때문에 그걸 뽑아서 숫자열로 변환해준다. 2. 숫자를 찾아 빈공백으로 처리해서 문자열만 추출한다. 3. 1에서 추출한 숫자열들의 합을 구한다. 4. 2에서 추출한 빈공백 제외의 문자열의 길이를 구한다. 5. 3에서 2를 나눈 후 Math.round메소드를 통해 반올림해준다.' 💡알게 된 점 여기서 사용한 메소드 설명 match() replace() 정규표현식
