Trie 자료구조는 트리 응용 자료구조로 문자열 검색에 사용되는 자료구조이다. 래딕스 트리(radix tree), 접두사 트리(prefix tree), 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다. 장점: 문자열을 탐색할 때, 하나씩 전부 비교하면서 탐색하는 방식보다 문자열을 빠르게 검색할 수 있으며, 특히 검색 대상이 많을 때 유용하다. 단점: 각 노드에서 다음 문자를 가리키는 노드가 필요하기 때문에 문자열이 길어질수록 공간 복잡도 측면에서 불리하다. 구조 Trie 자료구조는 루트 노드에서 시작하여 각 문자의 글자에 맞는 자식 노드로 이어지는 트리이다. 예시 아래는 "apple", "app", "banana"를 trie 자료구조로 표현한 그림이다. 색깔이 있는 노드는 문자열이 종료되는 지점이다. <img src="https://velog.velcdn.com/images/foxrain_gg/po

코테 언어를 파이썬에서 JS로 바꾸기로 마음먹은 뒤 전에 풀었던 알고리즘들을 다시 풀어보고 있다. 연산자 끼워넣기 문제를 풀던 중 문제가 발생했는데 작성한 코드가 분명 예제 입력에 대해서도 정상적으로 작동되었고 다른 사람들이 올린 예제 입력에서도 잘 작동되었는데 제출을 하면 정답이 아니라고 채점되었다. 이미 파이썬으로 풀어본 문제여서 JS로 변환만 하는 느낌으로 풀었지만 파이썬에서는 정답이였던 코드가 JS에서 동작하지 않아 당황했다. 아무리 디버깅을 해도 문제가 될만한 부분을 찾지 못하고 다른 원인들을 찾아보던 중 결국 해당 코드의 문제를 찾을 수 있었다. 문제의 코드 먼저 [연산자 끼워넣기](https://velog.io/@foxrain_gg/%EB%B0%B1%EC%A4%80BOJ-

정렬 알고리즘은 데이터를 특정한 기준에 따라 정렬하는 알고리즘으로 정렬 알고리즘은 데이터 처리에서 매우 중요한 역할을 한다. 이번 글에서는 가장 많이 사용되고 또 헷갈릴 수 있는 정렬 알고리즘들에 대해 정리해보며 JavaScript 구현 코드까지 같이 작성해봤다. 선택 정렬(Selection Sort) 선택 정렬은 주어진 리스트에서 최소값을 찾아 맨 앞에 위치한 값과 교체하고, 그 다음 최소값을 찾아 두 번째 위치한 값과 교체하는 방식으로 정렬하는 알고리즘이다. 선택 정렬 알고리즘의 시간 복잡도는 O(n^2)이다. 선택 정렬1 ![선택 정렬2](https://upload.wikimedia.org/wikipedia/commons/9/94/Selection-Sort-Animation.gi

알고리즘 문제들을 풀다보면 순열과 조합을 이용해 문제를 해결하는 경우가 있다. 기존에는 알고리즘 문제들을 파이썬을 사용해 풀어와서 파이썬의 라이브러리를 사용해 순열과 조합을 해결했지만 JavaScript로 언어를 변경하고 순열과 조합에 관련된 라이브러리가 없어 직접 구현을 해야했다. 그래서 이번에는 순열과 조합 구현을 정리해보고자 한다. 조합 > 서로 다른 n개 중에서 r개를 골라 순서를 상관하지 않고 나열한 경우의 수.(nCr) 예를 들어 [1, 2, 3, 4]중 3개를 골라 순서를 상관하지 않고 나열한다면(4C3) 결과는 아래와 같다. 위의 결과값은 아래와 같은 과정을 통해 구할 수 있다. 1을 선택하고 나머지 [2, 3, 4]중 2개를 골라 순서 상관 없이 나열한다(3C2) [1, 2, 3], [1, 2, 4], [1, 3, 4] 2를 선택하고 나머지 [3, 4]중 2개를 골라 순서 상관 없이 나열한다(2C2) [2, 3, 4] 즉 배열의

for in과 for of의 사용에 대해 헷갈리는 경우가 있어 짧게 정리해볼까 한다. 자바스크립트에서 for...in과 for...of은 둘 다 반복문(loop)을 사용하여 객체(object)의 프로퍼티(property)를 반복(iterate)하는 데 사용된다. 그러나 두 반복문의 작동 방식과 사용 용도에 차이가 있는데 다음과 같다. for...in for...in은 객체(object)의 모든 열거 가능한(enumerable) 속성들을 반복한다. 이때 반복 변수로는 객체의 속성 이름이 사용된다. 사용법 주의점 for...in은 특정 순서에 따라 인덱스를 반환하는 것을 보장하지 않기 때문에 만약 배열에 사용하게 되면 일관된 순서로 요소를 방문하지 못할 수도 있다. 그렇기 때문에 순서가 중요한 배열의 반복에는 for...of나 Array.prototype.forEach()를 사용하는 것을 추천한다. 따라서 for...in은 키-값 쌍을 가지고

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42891?language=javascript 정답 풀이 음식의 번호(idx)와 음식 시간(time)을 객체 형태로 저장하는데 이 과정에서 sort를 사용해 음식 시간이 가장 적은 것부터 배열에 저장되게 한다. 음식 시간이 가장 적은 것 부터 순서대로 음식을 다 먹는데 걸리는 시간을 구한다. 음식을 먹는데 걸리는 시간 = (현재 음식 시간 - 이전 음식 시간) * 남은 음식의 수 현재 음식을 다 먹는데 걸리는 시간보다 남은 시간(k)이 더 작다면 남은 음식중 먹어야 할 음식이 무엇인지 구한다. 방송 중단 후 먹어야할 음식 인덱스 = k % 남은 음식 개수 느낀점 이 문제는 시간내에 푸는 것을 실패한 문제이다. 정확성에서는 통과를 하여도 과도한 for문 사용으로 인해 효율성에서 문제가 발생했고 주어진 시간에 끝내 풀지 못했다. 이 문제의 핵

자바스크립트를 배우면서 가장 초반에 배우는 주요 개념은 let과 var의 차이점이다. 개념을 공부할 때는 이해가 되서 금방 지나갔지만 시간이 지나 잊어버리는 경우가 많아 복습도 할겸 let과 var의 차이첨을 정리해서 적어보고자 한다. var var hoisting 덕분에 변수를 선언하기도 전에 값 할당이 가능하다. var hoisting: 선언의 위치에 상관 없이 제일 위로 선언을 끌어올리는 것 hoisting: 인터프리터가 코드를 로드할 때 변수의 선언을 항상 코드 내의 최상위로 끌어올리는 것을 의미한다. 선언과 동시에 대입하는 코드는 호이스팅 하지 않는다. 즉 선언부는 호이스팅하지만 대입부는 호이스팅하지 않는다. var 키워드를 생략하고 사용할 수 있다. 중복 선언이 가능하다. 함수 레벨 스코프를 가진다. 함수 레벨 스코프 (Function-level scope) 함수 내에서 선언된 변수는 함수 내에서만 유효하며 함수 외부

require? VS code를 사용해 require로 모듈을 불러오다보면 VS code가 아래와 같은 안내 문구를 띄워주는 것을 경험했다. ES모듈로 변환해 보면 import로 변환되는 것을 볼 수 있는데 require과 import의 차이점이 뭘까? require vs import require은 NodeJS에서 사용하고 있는 CommonJS의 키워드이고 import는 ES6(ECMA2015)에서 새로 생긴 키워드이다. CommonJS와 ES6는 내보내기(export) 키워드에서도 차이점이 있는데 exports가 CommonJS, export가 ES6의 키워드이다. 즉 정리해보면 다음과 같다. > require / exports => CommonJS > import / export => ES6

그래프의 구조 DFS/BFS 알고리즘을 공부하기 위해 먼저 그래프의 기본 구조를 알아야 하므로 짧게나마 공부해보도록 하자. 그래프 그림 그래프는 위의 그림과 같이 노드(Node)와 간선(Edge)으로 표현된다. 두 노드가 간선으로 연결되어 있으면 두 노드는 인접(Adjacent)하다 라고 말한다. 그래프는 크게 2가지 방식으로 표현이 가능하다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현 인접행렬 | |

코딩테스트를 풀다보면 아래 문제와 같이 2차원 배열 90°회전을 요구하는 문제가 있다. 2020 KAKAO BLIND RECRUITMENT 그래서 for문을 사용한 2차원 배열 90°회전에 대해 공부한 것을 작성해볼 것이다. 과정 90° 회전하기 전 b a - c - - - - - 90° 회전후