상권's

-오늘의 코플릿 2021.11.25- LCS 문제 두 문자열을 입력받아 다음의 조건을 만족하는 LCS*의 길이를 리턴해야 합니다. LCS: 두 문자열에 공통으로 존재하는 연속되지 않는 부분 문자열(Longest Common Subsequence)문자열 'abc'의 subseqeunce는 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc' 입니다. // 입출력 예시 let output = LCS('abcd', 'aceb'); console.log(output); // --> 2 ('ab' or 'ac') output = LCS('acaykp', 'capcak'); console.log(output); // --> 4 ('acak') 최근 들어서 토이 문제의 난이도가 많이 올라가서 구현보다..

정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS*의 길이를 리턴해야 합니다. LIS: 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열(Longest Increasing Subsequence) 배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 입니다. 엄격한 오름차순: 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우를 말합니다. Advanced LIS를 계산하는 효율적인 알고리즘(O(N^2))이 존재합니다. 쉽지 않기 때문에 바로 레퍼런스 코드를 보고 이해하는 데 집중하시기 바랍니다. subsequence는 문자열 또는 배열같이 순서가 ..

히스토그램(histogram)은 표(도수 분포표, 빈도표)로 되어 있는 도수 분포(frequency distribution)를 정보 그림으로 나타낸 것입니다. 예를 들어, 대학교의 한 학과에서 신입생들의 현재 거주 지역을 조사한 결과가 다음과 같다고 가정해 봅시다. 서울 2명, 경기 1명, 대전 4명, 부산 5명, 대구 1명, 광주 3명, 제주도 3명... 이 자료를 히스트그램으로 나타내면 각각 높이 2, 1, 4, 5, 1, 3, 3인 직사각형이 왼쪽부터 그려지게 됩니다. 편의상 직사각형의 너비는 1이라고 가정합니다.// 이 히스토그램 내에서 만들 수 있는 가장 큰 직사각형의 면적은 8입니다 (O로 표시한 부분). 이처럼 임의의 히스토그램 내에서 가장 큰 직사각형의 면적을 리턴해야 합니다. 해당 문제에..

문제 정수를 요소로 갖는 배열과 특정 구간을 입력받아, 해당 구간 내에서 최소값을 리턴해야 합니다. Advanced Advanced1: 주어진 배열에서 특정 구간의 최소값을 구하는 단순한 알고리즘은 단순 순회(O(N))입니다. 같은 배열에 대해서 다양한 구간에 대한 최소값을 구할 경우, 단순 순회는 O(N^2) 입니다(구간의 개수도 N개라 가정할 경우). 적절한 자료구조를 통해 이와 같은 구간 조회에 대한 반복 작업을 효율적(O(N * logN))으로 수행할 수 있습니다. 구간 트리(segment tree)에 대해서 학습하시고, Advanced 테스트 케이스를 통과해 보시기 바랍니다.트리를 객체 또는 배열로 구현할 수 있습니다. 객체로 구현하는 것이 보다 직관적이기 때문에 객체로 먼저 도전하시기 바랍니다..

Associations Sequelize는 '1 대 1', '1 대 다', '다 대 다' 관계를 지원합니다. The A.hasOne(B.foreign key) association A와 B의 '1 대 1' 관계를 만들어 주는데, foreign key는 B에서 정의된다. The A.belongsTo(B) association A와 B의 '1대 1' 관계를 만들어 주는데, foreign key는 A에서 정의된다. The A.hasMany(B) association A와 B의 '1 대 다' 관계를 만들어 주는데, foreign key는 B에서 정의된다. 이 세 가지 호출을 통해 Sequilize는 적절한 모델에 외래 키를 자동으로 추가한다(이미 존재하지 않는 경우). The A.belongsToMany(B, ..

이번 한 주는 지난 주에 학습했던 SQL로 과제를 진행했고, sequelize, MVC 패턴, ORM, MongoDB 에 대해서 학습했습니다. SQL 을 이용해서 원하는 정보를 찾고, 수정하고, 삽입하는 게 처음에는 쉬웠지만, 과제를 진행하면서 원하는 정보가 까다로워지니 JOIN 부분이 쉽지 않았습니다. MVC는 전체적인 흐름을 이해하는 데에 학습하는 시간이 좀 걸렸습니다. 가장 어려웠던 건 sequelize 를 활용하는 것이었습니다. 다행스럽게 sprint hour을 통해서 전반적인 프로세스를 이해할 수 있었습니다. boiler-plate를 할 때, MongoDB에서 데이터를 찾고, 수정하는 부분을 학습해서 자신있었지만, 데이터베이스에 조금 더 깊게 들어가니 복잡해져서 자신감은 다시 숨어들었습니다. 학..

문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 배열arr[i]는 -100,000 이상 100,000 이하의 정수arr.length는 100,000 이하 출력 number 타입을 요소로 갖는 배열을 리턴해야 합니다. 주의사항 힙 정렬을 구현해야 합니다.arr.sort 사용은 금지됩니다.입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.최소 힙(min heap)을 구현해야 합니다.최소 힙 구현을 위해 선언된 함수들(getParentIdx, insert, removeRoot)을 전부 완성해야 합니다.swap, getParentIdx, insert, removeRoot를 전부 사용해야 합니다.swap, binaryH..

문제 정수를 요소로 갖는 배열을 입력받아 이진 힙(binary heap)*을 리턴해야 합니다. 이진 힙(binary heap)은 노드의 값이 특정한 순서를 가지고 있는 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트리는 이진 트리의 (마지막 레벨 또는 마지막 깊이를 제외하고) 모든 레벨이 노드로 가득 채워져 있어야 합니다. 마지막 레벨은 왼쪽부터 차례대로 채워져 있습니다.이진 힙에서 부모 노드의 값이 (이진 트리이므로 2개의) 자식 노드의 값보다 큰 경우를 최대 힙(max heap), 반대의 경우를 최소 힙(min heap)이라고 합니다. 주의사항 최대 힙(max heap)을 구현해야 합니다. 입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다. 최대 힙 구현을 위해 선언..