본문 바로가기
728x90

전체 글73

Git 브랜치란? 💡 Git 브랜치 브랜치란 독립적으로 어떤 작업을 진행하기 위한 개념이다. 개발을 하다 보면 한 페이지 안의 여러 기능을 따로 구현하기 위해, 코드를 여러 개로 복사하는 일이 자주 생기게 된다. 브랜치 기능을 활용하면, 코드를 통째로 복사한 후 원래 코드가 변경될 우려 없이 독립적으로 개발할 수 있다. 다시 말해, 각각의 브랜치는 다른 브랜치의 영향을 받지 않기 때문에 여러 작업을 동시에 진행할 수 있다. 브랜치기능의 장점 1. 한 소스코드에서 동시에 다양한 작업을 할 수 있게 해준다. 2. 소스코드의 한 시점과 동일한 상태를 만들고, 브랜치를 넘나들며 작업을 수행할 수 있다. 3. 각각의 브랜치에서 생긴 변화가 다른 브랜치에 영향을 주지 않고 독립적으로 코딩을 진행할 수 있다. hotfix, relea.. 2022. 8. 4.
정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS*의 길이를 리턴해야 합니다. LIS 문제 정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS*의 길이를 리턴해야 합니다. LIS: 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열(Longest Increasing Subsequence) 배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] 입니다. 엄격한 오름차순: 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우를 말합니다. 입력 인자 1 : arr number 타입을 요소로 갖는 배열 arr.length는 60,000 이하 arr[i]는 100,000 이하의 양의 정수 출력 number 타입을 리턴해야 합니다. 주의사항.. 2022. 7. 13.
최장 증가 부분 수열(LIS, Longest Increasing Subsequence), 자바스크립트로 구현하기 💡최장 증가 부분 수열 (LIS, Longest Increasing Subsequence) 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. 방법 A[i] : 수열의 i 번째 수 D[i] : A[i]를 마지막 값으로 가지는 가장 긴 증가 부분 수열의 길이 수열 A = [3, 5, 7, 1] 첫 번째 방법은 i=0 부터 D[i]를 계산하는데, 각각의 D[i]를 계산할 때마다 앞에 위치한 수들을 모두 확인하여 자신보다 작은 숫자들의 D 값 중 최댓값을 찾고 1을 더해 D[i]를 계산한다. i 0 1 2 3 4 A[i] 0 3 5 7 1 D[i] 0 배열 A에 수열을 다음과 같이 저장.. 2022. 7. 12.
구간 트리, 세그먼트 트리 (Segment Tree), 자바스크립트로 구현 💡세그먼트 트리, 구간 트리 (Segment Tree) 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료로 세그먼트 트리가 있다. 구간 트리는 배열의 특정 구간에 대한 질의를 빠르게 하기 위해 사용될 수 있다. 구간 트리는 주어진 배열의 구간들을 표현하는 이진 트리를 만든다. 루트는 배열의 전체 구간을 표현하고, 한 트리의 왼쪽 자식과 오른쪽 자식은 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 각 노드는 해당 구간에 대한 계산 결과를 저장해둔다. ✓ 특정 구간의 합을 가장 빠르게 구하는 방법은? 예시 데이터 : 1 9 3 8 4 5 5 9 10 3 4 5 💻 방법1. 단순 배열을 이용해 선형적으로 구하기 0 1 2 3 4 5 6 7 8 9 1.. 2022. 7. 11.
알고리즘 문제 풀이 - largestRectangularArea, 구간트리란? 문제 히스토그램(histogram)은 표(도수 분포표, 빈도표)로 되어 있는 도수 분포(frequency distribution)를 정보 그림으로 나타낸 것입니다. 예를 들어, 대학교의 한 학과에서 신입생들의 현재 거주 지역을 조사한 결과가 다음과 같다고 가정해 봅시다. 서울 2명, 경기 1명, 대전 4명, 부산 5명, 대구 1명, 광주 3명, 제주도 3명... 이 자료를 히스트그램으로 나타내면 각각 높이 2, 1, 4, 5, 1, 3, 3인 직사각형이 왼쪽부터 그려지게 됩니다. 편의상 직사각형의 너비는 1이라고 가정합니다. 이를 그림으로 나타내면 아래와 같습니다. 6 | 5 | x 4 | x x 3 | x x x x 2 | x x x x x 1 | x x x x x x x ----------------.. 2022. 7. 11.
이진 힙(Binary Heap), 자바스크립트로 구현하기 ✓ 힙 (Heap) 힙이란 트리 기반 자료구조로 힙 속성을 만족하는 거의 완전한 트리이다. 힙 속성이란 예를 들어, 최대힙의 경우 부모 노드는 반드시 자식 노드보다 커야 한다는 법칙이다. 따라서 최상위 노드는 최대값을 가지게 된다. 따라서 최상위 노드는 최대값을 가지게 된다. 이러한 힙의 특성으로 힙은 우선수위 큐를 구현하는데 적합한 자료구조이다. 힙은 부모와 자식 노드 간의 관계만이 정의되어 있을 뿐, 현제 또는 사촌 노드 간의 우선수위는 정해진 것이 없다. ✓ 이진 힙 (Binary Heap) 이진 힙은 힙 중에서 가장 널리 쓰이는 형태 중 하나로 이진 트리 형태인 힙이다. 이진 트리는 각 노드의 자식 노드가 반드시 2개 이하인 트리이다. 이진 힙은 완전 이진 트리라는 조건을 만족해야한다. 모든 레벨.. 2022. 7. 6.
이진탐색트리 (Binary Search Tree) 💡이진 탐색 트리 (binary search tree) 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 한다. 트리 구조는 가지고 있는 특징에 따라 여러 가지 이름으로 불리는데 이진 트리(binary tree)와 이진 탐색 트리(binary search tree)가 가장 많이 사용된다. 먼저 이진트리는 자식 노드가 최대 두 개인 노드들루 구성된 트리이다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있는데, 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화이 이진 트리로 나뉘게 된다. 정 이진 트리(Full binary tree) 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. 포화 이진 트리(Perfect binar.. 2022. 7. 6.
[알고리즘 문제 풀이] 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. bubbleSort 문제 정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다. 버블 정렬(bubble sort)은 여러 정렬 알고리즘(삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬 등) 중 가장 기본적인 알고리즘입니다. 버블 정렬 알고리즘은 아래와 같습니다. 첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 두 번째 요소와 세 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap) 1, 2를 마지막까지 반복합니다. (마지막에서 두 번째 요소와 마지막 요소를 비교) 1~3의 과정을 한 번 거치게 되면, 가장 큰 요소가 배열의 마지막으로 밀려납니다. 1~3의 과정을 첫 요소부터 다시 반복합니다. 5를 통해 두 번째로 큰 요소가 배열의 마지막 바로 .. 2022. 7. 3.
[알고리즘 문제 풀이] 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다. isSubsetOf 문제 두 개의 배열(base, sample)을 입력받아 sample이 base의 부분집합인지 여부를 리턴해야 합니다. 입력 인자 1 : base number 타입을 요소로 갖는 임의의 배열 base.length는 100 이하 인자 2 : sample number 타입을 요소로 갖는 임의의 배열 sample.length는 100 이하 출력 boolean 타입을 리턴해야 합니다. 주의사항 base, sample 내에 중복되는 요소는 없다고 가정합니다. 입출력 예시 let base = [1, 2, 3, 4, 5]; let sample = [1, 3]; let output = isSubsetOf(base, sample); console.log(output); // --> true sample.. 2022. 7. 3.
728x90

티스토리툴바