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의 경우 삽입/삭제를 위해서 값을 찾아주는 과정이 필요했지만, 힙은 일단 배열의 맨 ..

Binary Search Tree란? 👉 개념 Binary Search Tree(BST)는 효율적인 탐색을 위한 데이터 저장 방법이다. 👉 규칙 노드에 저장되는 키는 유일하다. 부모의 키 값이 왼쪽 자식 노드의 키 값보다 크다. 부모의 키 값이 오른쪽 자식 노드의 키 값보다 작다. 왼쪽과 오른쪽 서브트리도 BST이다. 👉 장단점 장점 탐색 연산 시간복잡도가 O(log N)이다. (명확히 말하면 O(h)) 단점 편향 트리의 경우 저장 순서에 따라서 한 쪽으로만 노드가 추가되는 경우가 발생한다. 최악의 경우는 탐색 시간복잡도가 O(N)이다. 배열보다 많은 메모리를 사용한다. Leetcode 문제를 통한 BST 구현 BST를 직접 구현하는 것이 도움이 될 것이라 생각하여 아래 문제를 풀어보았다. 1. 탐색: ..

🤔 문제. Palindromic Substring: 거꾸로 뒤집어도 같은 문자열, 예를들어 aaa, baaab 등. 🤗 풀이. 문자열 DP 문제이다. start포인트와 길이를 담을 변수를 지정한다. (기존 Palindromic Substring의 정보를 저장할 용도) for문을 실행하여 end포인트를 이동시켜준다. 특정 조건일 때 start 포인트와 길이를 변경한다. 기존 Palindromic Substring에 end포인트의 문자를 포함했을 때, Palindromic을 만족한다. Ex. aaa 기존 Palindromic Substring에 end포인트의 문자와 Substring의 앞의 문자를 포함했을 때, Palindromic을 만족한다. Ex. baaab HTML 삽입 미리보기할 수 없는 소스

🤔 문제. 2차원 배열을 시계방향으로 돌리는 간단한 문제입니다. 🤗 풀이. [단순 구현] 처음 풀었던 방식은 순수한 구현이었다. 끝에서 부터 한 바퀴씩 돌며 좌표를 담는 xy_list와 값을 담는 v_list를 만든 뒤, v_list 값을 수정해서 matrix를 재구성하였다. 통과는 했지만, 실행 시간이 오래걸렸다. HTML 삽입 미리보기할 수 없는 소스 [간단한 방법] 위에서는 2차원 배열을 1차원 배열로 바꿔서 풀려는 시도를 했다. 하지만 2차원 배열을 전체적으로 움직이며 푸는 방법이 있었다. matrix를 행을 중심으로 뒤집는다. matrix를 대각선을 중심으로 뒤집는다. HTML 삽입 미리보기할 수 없는 소스 실행속도는 2배 정도 차이난다... 역시 알고리즘 문제는 구현 전에 생각을 해야한다! 😓

🤔 문제. Array에서 3개를 골라 0이 되는 sub-array를 구하는 문제입니다. 처음에는 2Sum을 구한 후에 하나씩 확인하며 구성하는 것으로 구현했는데, 시간초과가 나버렸습니다... 시간을 좀 더 들여 고민한 결과 정렬 후 투포인트로 문제를 풀었습니다. 🤗 풀이. Array를 sort한다. for문을 통해 값을 하나 잡고, left/right 포지션을 지정한다. 투포인트를 옮기면서 합이 0이되는 Array를 저장한다. (이때 중요한 점은 정답에 같은 Array는 포함되지 않도록 함으로 같은 과정을 최소화하는 방향으로 진행한다.) HTML 삽입 미리보기할 수 없는 소스