Scala란 함수형 객체지향 프로그래밍 언어로써 Spark를 사용할 때 빠른 성능을 이용할 수 있음으로 데이터 엔지니어링 역량에 필요한 언어입니다.필자는 Scala언어와 친해지기 위해서 Scala 언어를 활용하여 많은 알고리즘 문제를 풀어보았습니다. https://github.com/DeepFlame-JR/Algorithm_Solving GitHub - DeepFlame-JR/Algorithm_Solving: 알고리즘 문제 풀이알고리즘 문제 풀이 . Contribute to DeepFlame-JR/Algorithm_Solving development by creating an account on GitHub.github.com 아래에 알고리즘에 필요한 Scala 기본 문법에 대해서 정리해보겠습니다. 기본..

https://leetcode.com/problems/unique-binary-search-trees/ Unique Binary Search Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 🤔 문제. n 개의 노드가 주어졌을 때, BST를 구성할 수 있는 경우의 수를 구하는 문제이다. 🤗 풀이. 처음에는 BST를 모두 구현을 해야하나...? 라는 생각이 들었다. (그러나 leetcode 특성상 그런 무식한 문제는 잘 없다.) 하지만 이내 이 문제는 ..

https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 🤔 문제. (0,0)에 있는 자동차가 (n-1,n-1)로 이동하는 데 드는 최소 비용을..

데이터 베이스는 이론상 무한 개의 데이터를 다룰 수 있어야 하기 때문에, 수많은 데이터를 얼마나 빠르게 정렬하는 가는 중요한 문제이다. 🤔 그렇다면 왜 데이터는 정렬되어 있어야할까?간단히 말하자면 탐색을 위해서 이다. 정렬되어 있지 않은 데이터에서는 순차 탐색(O(N)) 밖에 사용할 수 없으나, 데이터가 정렬되어 있다면 이진 탐색(O(logN))이라는 알고리즘을 활용할 수 있다.삽입/삭제가 자주 일어나는 데이터의 경우 정렬에 더 많이 시간이 들어감으로 순차 탐색을 사용하는 경우도 있지만, 보통의 경우는 데이터를 조회하는 경우가 훨씬 많다. 그리고 조회에 필요한 것이 검색(탐색)이다. 1. 버블 정렬최댓값을 우선적으로 정렬하는 알고리즘이다.👉 동작 방식0부터 N-1까지 탐색하면서 인접한 칸과 비교하..

다이나믹 프로그래밍이란? 큰 문제를 작은 문제로 나누어 풀고, 작은 문제의 답을 재활용하는 기법을 의미한다. 메모리 비용을 활용하여 시간적 비용을 줄이는 방식이다. 👉 조건 부분 반복 문제: 작은 문제가 반복되는 경우 최적 부분 구조: 같은 문제는 구할 때마다 정답이 같을 경우 작은 문제가 반복되고 그 문제의 답이 같기 때문에, 굳이 작은 문제에 대한 계산을 반복하지 않고 이를 메모리에 저장하여 활용하는 것이다. Fibonacci 수열 DP를 설명할 때 가장 기본적으로 예를 들 수 있는 것이 Fibonacci 수열이다. 이는 f(n) = f(n-1) + f(n-2)의 점화식을 가진다. 아래 Leetcode 문제를 재귀 함수를 이용하는 방법과 동적 프로그래밍을 사용하는 방법으로 풀어볼 것이다. https:..

Heap이란? 👉 개념 우선순위큐(Priority Queue)에서 사용되는 자료구조이며, 최대값이나 최솟값을 찾는 데 소요되는 시간이 O(1)이다. 하지만 노드 수정시, 힙구조 유지하기 위해 heapify과정을 거쳐 구조를 유지한다. 이는 결국 O(log n)의 시간 복잡도를 가진다. 👉 특징 Tree 중 배열에 기반한 완전 이진 트리 형식(왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리)을 가지며, 최대힙/최소힙 두 종류가 있다. 최대 힙 key(부모 노드) ≥ key(자식 노드) 최소 힙 key(부모 노드) ≤ key(자식 모드) 완전 이진 트리이기 때문에 삽입/삭제 연산이 배열의 가장 끝에서 발생한다. BST의 경우 삽입/삭제를 위해서 값을 찾아주는 과정이 필요했지만, 힙은 일단 배열의 맨 ..