Algorithms

정렬

선택 정렬

정렬 알고리즘은 다음과 같이 나눠볼 수 있다.

• 단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬

• 복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

그 중에서 이번에는 선택 정렬에 대해 알아보려 한다.

✨ 개념

• 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.

• 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순 정렬)과 최대 선택 정렬(내림차순 정렬)로 나뉜다.

✨ 로직

1. 주어진 배열에서 첫번째 인덱스를 기준으로 잡는다. 기준은 처음부터 시작한다.

2. 주어진 배열에서 기준 이후의 값 중 최소값을 찾는다.

3. 최소값과 그 기준의 값을 교체한다.

4. 기준 이후의 나머지 배열을 같은 방법으로 교체한다.

✨ 장점

• 알고리즘이 단순하다.

• 정렬을 위한 비교는 여러번 수행되지만, 실제로 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적인 면이 있다.

• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

✨ 단점

• 시간 복잡도가 O(N^2)이므로 비효율적이다.

• 불안정 정렬(Unstable Sort)이다.

거품 정렬

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

• 인접한 2개의 원소를 비교해 크기가 순서대로 되어 있지 않으면 서로 교환한다.

• 선택 정렬과 기본 개념이 유사하다.

✨ 로직

1. 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, ... 이런 식으로 마지막 - 1 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않으면 서로 교환한다.

2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

✨ 시간 복잡도

(n-1)+(n-2)+(n-3)+ ... +2+1 => n(n-1)/2이므로, O(N^2)이다.

버블 정렬은 정렬이 되어있건, 안되어있건 2개의 원소를 비교하기 때문에 최악의 경우, 최선의 경우, 평균의 경우 모두 시간 복잡도가 O(N^2)으로 동일하다.

✨ 공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

✨ 장점

• 구현이 간단하고 소스코드가 직관적이다.

• 이미 정렬된 데이터를 정렬할 때, 가장 빠르다.

• 정렬하고자 하는 배열 안에서 정렬하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

• 안정 정렬이다.

✨ 단점

• 시간 복잡도가 최악, 최선, 평균 모두 O(N^2)이므로 비효율적이다.

• 다른 정렬에 비해 정렬 속도가 느리다.

• 교환 횟수가 많다.

• 역순배열을 정렬할 때, 가장 느리다.

삽입 정렬

✨ 개념

• 손 안의 카드를 정렬하는 방법과 유사하다.

• 새로운 카드를 기존의 정렬된 카드 사이에 올바른 자리를 찾아 삽입한다.

• 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.

• 최선의 경우, O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될만큼 좋은 정렬 알고리즘이다.

✨ 로직

1. 정렬은 2번째 위치(index)의 값을 standard에 저장한다

2. standard와 이전에 있는 원소들과 비교하여 자리를 바꾸며 삽입해 나간다.

3. 1번으로 돌아가서 다음 위치(index)의 값을 standard에 저장하고 이 과정을 반복한다.

✨ 시간 복잡도

• 최악의 경우(역으로 정렬되어 있을 경우), 선택 정렬과 마찬가지로 (n-1)+(n-2)+ ... +2+1 => n(n-1)/2 즉, O(N^2)이다.

• 하지만, 모두 정렬이 되어 있는 경우, 한번씩만 비교하므로 O(N)의 시간 복잡도를 가지게 된다. 또한, 이미 정렬되어 있는배열에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

• 최선의 경우 : O(N)

• 평균과 최악의 경우 : O(N^2)

✨ 공간 복잡도

• 주어진 배열 안에서 교환을 통해 정렬이 이루어지기 때문에 O(N)이다.

✨ 장점

• 알고리즘이 단순하다.

• 대부분의 원소가 이미 정렬되어 있는 경우, 매우 효율적일 수 있다.

• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

• 선택 정렬이나 버블 정렬에 비하여 상대적으로 빠르다.

✨ 단점

• 비교적 많은 수들의 이동을 포함한다.

• 비교할 수가 많고 크기가 클 경우에 적합하지 않다.(배열의 길이가 길어질수록 비효율적)

• 평균과 최악의 시간 복잡도가 O(N^2)이므로 비효율적이다.

병합 정렬

합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현한다.

✨ 개념

• 빠른 정렬로 분류되며, Quick Sort와 함께 많이 언급되는 정렬 방식이다.

• Quick Sort와는 반대로 안정 정렬에 속한다.

시간복잡도

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로 쪼개는 방식은 퀵 정렬과 유사.

✨ 장점

• 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. -> O(N logN)

• 크기가 큰 레코드를 정렬한 경우, LinkedList를 사용한다면 병합 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적이다.

• 안정 정렬에 속한다.

✨ 단점

• 레코드를 배열로 구성한다면, 임시 배열이 필요하다.

  • 메모리 낭비를 초래한다.

  • 제자리 정렬이 아니다.

• 레코드의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.

✨ 시간 복잡도

• 평균 : O(N logN)

• 최악 : O(N logN)

• 최선 : O(N logN)

이분 탐색

탐색 범위를 두 부분으로 분할하면서 찾는 방식

처음부터 끝까지 돌면서 탐색하는 것보다 훨~~~씬 빠른 장점을 지님

• 시간복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN)

✨ 진행 순서

• 우선 정렬을 해야 함

• left와 right로 mid 값 설정

• mid와 내가 구하고자 하는 값과 비교

• 구할 값이 mid보다 높으면 : left = mid+1 구할 값이 mid보다 낮으면 : right = mid - 1

• left > right가 될 때까지 계속 반복하

퀵 정렬

✨ 개념

• 퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다.

  • 분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

• 또한, Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

✨ 로직

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소는 피벗(pivot)이라고 한다.

2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3. 분할 된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

• 분할(Divide) : 주어진 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다.(피벗을 중식으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)

• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.

✨ Qucik Sort 개선

위의 코드에서는 피벗을 배열의 가운데 원소로 지정함으로써 어느 정도 성능을 개선한 형태이다.

하지만, 피벗 값이 최소나 최대값으로 지정되면 피벗을 기준으로 원소들이 들어갈 값을 찾는데 오래 걸린다. O(N^2)의 시간 복잡도를 갖는다.

즉, 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있으면 O(N^2)의 시간복잡도를 가진다. 이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간 복잡도 O(N logN)으로 개선할 수 있다.

하지만, 이 방법으로 개선한다 하더라도 Quick Sort의 최악의 시간 복잡도가 O(N logN)이 되는 것은 아니다.

✨ 시간 복잡도

최선의 경우 : T(N) = O(N logN)

• 비교 횟수 : logN

✨ 공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

✨ 장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(N logN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

✨ 단점

• 불안정 정렬이다.

• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.

✨ 결론

Quick Sort는 평균적으로 가장 빠른 정렬 알고리즘이다.

Java에서는 Arrays.sort()가 내부적으로 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘이다.

또한, 기술 면접에서 빈번하게 나오므로 반드시 숙지해야 한다.

힙 정렬

완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식이다.

불안정 정렬에 속한다.

[완전 이진 트리?]

• 삽입할 때, 왼쪽부터 차례대로 추가하는 이진 트리

✨ 시간 복잡도

• 평균 : O(N logN)

• 최선 : O(N logN)

• 최악 : O(N logN)

✨ 로직

1. 최대 힙을 구성한다.

2. 현재 힙 루트는 가장 큰 값이 존재한다. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈를 하나 줄인다.

3. 힙의 사이즈가 1보다 크면 위의 과정을 반복한다.

이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 Heap Sort이다.

기수 정렬

✨ Comparison Sort

---

N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N!임

따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도임)

이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것

✨ Radix sort

---

데이터를 구성하는 기본 요소 (Radix) 를 이용하여 정렬을 진행하는 방식

입력 데이터의 최대값에 따라서 Counting Sort의 비효율성을 개선하기 위해서, Radix Sort를 사용할 수 있음.

자릿수의 값 별로 (예) 둘째 자리, 첫째 자리) 정렬을 하므로, 나올 수 있는 값의 최대 사이즈는 9임 (범위 : 0 ~ 9)

• 시간 복잡도 : O(d * (n + b))

  • d는 정렬할 숫자의 자릿수, b는 10 (k와 같으나 10으로 고정되어 있다.)

  ( Counting Sort의 경우 : O(n + k) 로 배열의 최댓값 k에 영향을 받음 )

• 장점 : 문자열, 정수 정렬 가능

• 단점 : 자릿수가 없는 것은 정렬할 수 없음. (부동 소숫점)

  중간 결과를 저장할 bucket 공간이 필요함.

계수 정렬

✨ Comparison Sort

---

N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N!임

따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도임)

이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것

✨ Counting Sort 과정

---

시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값

공간 복잡도 : O(k) -> k만큼의 배열을 만들어야 함.

Counting이 필요 : 각 숫자가 몇 번 등장했는지 센다.

• 사용 : 정렬하는 숫자가 특정한 범위 내에 있을 때 사용

  (Suffix Array 를 얻을 때, 시간복잡도 O(nlgn)으로 얻을 수 있음.)

• 장점 : O(n) 의 시간복잡도

• 단점 : 배열 사이즈 N 만큼 돌 때, 증가시켜주는 Counting 배열의 크기가 큼.

  (메모리 낭비가 심함)

해시 테이블 구현

알고리즘 문제를 풀기위해 필수적으로 알아야 할 개념

브루트 포스(완전 탐색)으로는 시간초과에 빠지게 되는 문제에서는 해시를 적용시켜야 한다.

연습 문제 링크

✨ 해시 테이블 구현

해시 테이블은 탐색을 최대한 줄여주기 위해, input에 대한 key 값을 얻어내서 관리하는 방식이다.

동적 계획법 (Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

흔히 말하는 DP가 바로 '동적 계획법'

한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다.

즉, 똑같은 연산을 반복하지 않도록 만들어준다. 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있다.

동적 계획법은 Optimal Substructure에서 효과를 발휘한다.

Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 계속 반복하는 문제 구조

✨ 접근 방식

커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다.

즉, 동적 계획법은 간단한 작은 문제들 속에서 '계속 반복되는 연산'을 활용하여 빠르게 풀 수 있는 것이 핵심이다.

✨ 조건

• 작은 문제에서 반복이 일어남

• 같은 문제는 항상 정답이 같음

이 두 가지 조건이 충족한다면, 동적 계획법을 이용하여 문제를 풀 수 있다.

같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization)으로 큰 문제를 해결해나가는 것이다.

메모이제이션(Memoization) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

피보나치 수열에서 재귀를 활용하여 풀 경우, 같은 연산을 계속 반복함을 알 수 있다.

이때, 메모이제이션을 통해 같은 작업을 되풀이 하지 않도록 구현하면 효율적이다.

이처럼 같은 연산이 계속 반복적으로 이용될 때, 메모이제이션을 활용하여 값을 미리 저장해두면 효율적`

피보나치 구현에 재귀를 활용했다면 시간복잡도는 O(2^n)이지만, 동적 계획법을 활용하면 O(N)으로 해결할 수 있다.

✨ 구현 방식

• Bottom-up : 작은 문제부터 차근차근 구하는 방법

• Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀 방식)

Bottom-up은 해결이 용이하지만, 가독성이 떨어짐

Top-down은 가독성이 좋지만, 코드 작성이 힘듬

동적 계획법으로 문제를 풀 때는, 우선 작은 문제부터 해결해나가보는 것이 좋다.

작은 문제들을 풀어나가다보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해내어 동적 계획법을 적용시키자

탐욕법 (Greedy)

다익스트라(Dijkstra) 알고리즘

DP를 활용한 최단 경로 탐색 알고리즘

다익스트라 알고리즘은 특정한 정점에서 다른 모든 정점으로 가는 최단 경로를 기록한다.

여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다.

다익스트라를 구현하기 위해 두 가지를 저장해야 한다.

• 해당 정점까지의 최단 거리를 저장

• 정점을 방문했는 지 저장

시작 정점으로부터 정점들의 최단 거리를 저장하는 배열과, 방문 여부를 저장하는 것이다.

다익스트라의 알고리즘 순서는 아래와 같다.

1. 최단 거리 값은 무한대 값으로 초기화한다.

2. 시작 정점의 최단 거리는 0이다. 그리고 시작 정점을 방문 처리한다.

3. 시작 정점과 연결된 정점들의 최단 거리 값을 갱신한다.

4. 방문하지 않은 정점 중 최단 거리가 최소인 정점을 찾는다.

5. 찾은 정점을 방문 체크로 변경 후, 해당 정점과 연결된 방문하지 않은 정점의 최단 거리 값을 갱신한다.

6. 모든 정점을 방문할 때까지 4~5번을 반복한다.

✨ 다익스트라 적용 시 알아야할 점

• 인접 행렬로 구현하면 시간 복잡도는 O(N^2)이다.

• 인접 리스트로 구현하면 시간 복잡도는 O(N*logN)이다.

  선형 탐색으로 시간 초과가 나는 문제는 인접 리스트로 접근해야한다. (우선순위 큐)

• 간선의 값이 양수일 때만 가능하다.

투 포인터 알고리즘

투포인터 알고리즘(Two Pointers Algorithm) 또는 슬라이딩 윈도우(Sliding Window)라고 부른다. 이번에 20년도 상반기 라인 공채 코딩 테스트에서 이를 활용할 만한 문제가 나왔다. 그래서 예전에 정리했던 내용을 떠올리며, 다시 정리하려 글을 쓴다.

알고리즘 문제를 풀다 완전탐색으로 해결하면 시간 초과가 나는 문제가 종종 있다. 어떻게 풀어야 하는지 그 당시 검색했을 때, 투 포인터 알고리즘 이 대안이었다.

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 이때문에 투포인터 알고리즘이라 부른다.

N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 모든 경우의 수를 다 테스트 해보면 구간 합을 구간 배열로 O(1)만에 구한다고 해도 경우의 수는 O(N^2)이 된다. 따라서 문제를 풀 수 없다. N의 최대 범위가 너무 크기 때문이다.

순열

BFS & DFS

그래프 알고리즘으로, 문제를 풀 때 상당히 많이 사용되는 개념이다.

문제의 상황에 맞게 BFS와 DFS를 활용하면 된다.

여기서 사용되는 코드는 백준에 있는 DFS와 BFS 문제를 기반으로 한다.

V : 정점, E : 간선

BFS

• 너비 우선 탐색이라 하며 BFS(Breadth-First Search)라 부른다.

• 루트 노드 혹은 임의의 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법.

• 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

• 즉, 깊게 탐색하기 전에 넓게 탐색하는 것이다.

• 큐를 사용한다. (해당 노드의 주변부터 탐색해야 하기 때문이다.)

• 최소 비용(즉, 모든 곳을 탐색하는 것보다 최소 비용이 우선일 때)에 적합하다.

시간 복잡도

• • 인접 행렬 : O(V^2)

  • 인접 리스트 : O(V+E)

DFS

• 깊이 우선 탐색이며 DFS(Depth-First Search)라고 부른다.

• 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

• 넓게 탐색하기 전에 깊게 탐색하는 것이다.

• 예를 들어, 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.

• 스택이나 재귀함수를 통해 구현한다.

• 모든 경로를 방문해야 할 경우 사용에 적합하다.

• 시간 복잡도

  • 인접 행렬 : O(V^2)

  • 인접 리스트 : O(V+E)

그래프 구현

탐색

✨ 완전 탐색

✨이분 탐색(Binary Search)

• 이진 탐색 혹은 이분 탐색이라고 부른다.

• 이미 정렬되어 있는 자료 구조에서 특정 값을 찾을 때, 탐색 범위를 절반씩 나눠가면서 해당 값을 찾아가는 것이다.

• 즉, 탐색 범위를 두 부분으로 분할하면서 찾는 방식이다.

• 처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠르다는 장점을 가지고 있다.

시간 복잡도

• 전체 탐색 : O(N)

• 이분 탐색 : O(logN)

진행 순서

• 정렬을 한다.

• left와 right로 mid 값을 설정한다.

• mid와 구하고자 하는 값을 비교한다.

• 구할 값이 mid보다 크면 -> left = mid + 1

• 구할 값이 mid보다 낮으면 -> right = mid - 1

• right < left가 될 때까지 계속 반복한다

최대 공약수와 최소 공배수

✨ 최대공약수 GCD(Greatest Common Divisor)

• 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

• ex) 72와 30의 최대 공약수는 6이다.

✨ 최소 공배수 LCM(Least Common Multiple)

• 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

• 최소 공배수 = 두 자연수의 곱 / 최대 공약수

• ex) 72와 30의 최소 공배수는 360이다.

✨ 유클리드 호제법(Euclidean Algorithm)

2개의 자연수를 입력 받아 최대 공약수를 구하기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다. 하지만, 이 방법으로 문제를 풀면 시간 복잡도는 O(N)이 된다. 나쁜 방법은 아니지만, 보다 효율을 높일 수 있는 방법이 존재하며 유클리드 호제법이란 알고리즘을 사용하면 시간 복잡도를 O(logN)으로 줄일 수 있다.

호제법이란? 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 방법

최장 증가 수열 (LIS)

✨ LIS (Longest Increasing Sequence)

최장 증가 수열 : 가장 긴 증가하는 부분 수열

[ 7, 2, 3, 8, 4, 5 ] → 해당 배열에서는 [2,3,4,5]가 LIS로 답은 4

✨ 구현 방법 (시간복잡도)

1. DP : O(N^2)

2. Lower Bound : O(NlogN)

✨ DP 활용 코드

최소 공통 조상 (LCA)

✨ LCA(Lowest Common Ancestor) 알고리즘

최소 공통 조상 찾는 알고리즘

→ 두 정점이 만나는 최초 부모 정점을 찾는 것!

비트마스크(BitMask)

집합의 요소들의 구성 여부를 표현할 때 유용한 테크닉

✨ 왜 비트마스크를 사용하는가?

• DP나 순열 등, 배열 활용만으로 해결할 수 없는 문제

• 작은 메모리와 빠른 수행시간으로 해결이 가능 (But, 원소의 수가 많지 않아야 함)

• 집합을 배열의 인덱스로 표현할 수 있음

• 코드가 간결해짐

✨ 비트(Bit)란?

컴퓨터에서 사용되는 데이터의 최소 단위 (0과 1)

2진법을 생각하면 편하다.

✨ 비트 연산

AND, OR, XOR, NOT, SHIFT

• AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환

• OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일때, 1 반환

• XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환

• NOT(~) : 비트 값 반전하여 반환

• SHIFT(>>, <<) : 왼쪽 혹은 오른쪽으로 비트 옮겨 반환

  • 왼쪽 시프트 : A * 2^B

  • 오른쪽 시프트 : A / 2^B

  [왼 쪽] 0001 → 0010 → 0100 → 1000 : 1 → 2 → 4 → 8 [오른쪽] 1000 → 0100 → 0010 → 0001 : 8 → 4 → 2 → 1

비트연산 연습문제 : 백준 12813

Iru cache (Least Recently Used)

✨ Cache 개념

캐시는 데이터나 값을 미리 복사해 놓는 임시 장소를 가리킨다. 캐시는 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하는 경우 사용한다. 캐시에 데이터를 미리 복사해 놓으면 계산이나 접근 시간 없이 빠른 속도로 데이터에 접근할 수 있다. (캐시가 사용하는 리소스의 양도 제한이 있다.)

✨ LRU Cache 개념

LRU는 Least Recently Used의 약자로 OS의 페이지 교체 알고리즘의 하나로 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다. 캐시에 공간이 부족하면 가장 최근에 사용하지 않은 항목을 제거한다.

✨ LRU Cache 구현

LRU Cache 구현은 Doubly Linked List를 통해 구현한다. head에 가까운 데이터일수록 최근에 사용한 데이터이고, tail에 가까울수록 가장 오랫동안 사용하지 않은 데이터로 간주하여 새로운 데이터를 삽입할 때, 가장 먼저 삭제되도록 한다.

삽입된 데이터를 사용하면 head로 옮겨 우선순위를 높이게 되고, 삭제될 우선순위에서 멀어지게 된다.