본문 바로가기

[Basic] Data/Algorithm32

[Algorithm] (알고리즘 패턴) Frequency Counters(빈도수 세기) Frequency Counter(빈도수 세기) 알고리즘 패턴 이 패턴은 말 그대로 객체 또는 Set을 사용하여 특정 문자열, 배열 등의 값 / 값의 빈도를 수집해 풀어내는 방식이다. 프로세스 주어진 배열 속 요소의 빈도를 확인할 때, 방식 Worst : 중첩 루프 for문 안에서 indexOf를 사용 -> O(n^2) for A 순회 B.indexOf(n) 찾아서 삭제 없으면 return false 순회 마쳤으면 return true Best : 객체 사용 for문을 3번 반복하여 3n. 즉 -> O(n) A 순회해서 {요소: 개수, ...} 객체 만듬 B 순회해서 {요소: 개수, ...} 객체 만듬 A객체의 key 순회해서 B객체 값과 비교 같지 않으면 return false 순회 마쳤으면 return.. 2023. 3. 25.
[Algorithm] (알고리즘 패턴) 투 포인터(다중 포인터) 투 포인터(Two Pointers. 다중 포인터) 알고리즘 패턴 두 개 또는 그 이상의 포인터를 두고 값들을 비교하여 문제를 해결하는 알고리즘 패턴이다. 배열이나 문자열같은 선형 구조에서 각자 다른 원소를 가리키는 2개의 포인터를 조작해가면서 원하는 것을 얻어내는 개념이다. 정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 한다. 프로세스 그냥 기본 방식인 탐색(반복문)을 쓰다 보면 시간이 오래 걸리거나 시간 초과가 걸리는 경우에 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있다. 시간복잡도 : O(N). 기본 탐색 반복문을 사용한다면 O(N^2) 투 포인터는 2가지 방식이 있다. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터 빠.. 2023. 3. 24.
[Algorithm] 유클리드 호제법 (최대공약수 & 최소공배수 구하기) 유클리드 호제법 유클리드 호제법이란, 2개의 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 의무교육 과정에서 최대공약수를 구하는 방법을 두가지 배울텐데 소인수분해와 호제법을 배운다. 호제법을 쓰다보면 위 경우처럼 수가 크면 계산이 복잡해지고, 약수를 한번에 찾기가 힘든 경우가 있다. 이 때, 유클리드 호제법을 이용해서 쉽게 구할수 있다. 유클리드 호제법은 두 정수의 최대공약수를 빠르게 구하는 방법이다. 하나만 기억해야하면 "A > B 일때, A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다." 큰 수(A)를 작은 수(B)로 나눈다. ( A > B ) 만약 나누고 난 나머지가 0 이라면 작은 수가 최대공약수이다. 만약 나머지가 0이 아니라면, 작은 수(B)를 나머지(R)로 계속 나눈다. 이를.. 2023. 3. 24.
[Algorithm] (알고리즘 패턴) 슬라이딩 윈도우(Sliding Window) 슬라이딩 윈도우(Sliding Window) 알고리즘 패턴 윈도우(특정 범위)가 있을 때, 윈도우 내부 요소의 값을 이용하여 문제를 풀이하는 알고리즘이다. 배열이나 문자열같은 선형 구조에서 요소의 일정 범위값을 비교할 때, 사용하면 유용한 패턴이다. 투 포인터 패턴과 유사하다. 특정한 조건에 따라 window가 커지거나 닫히거나, 새로 생성될수도 있다. 예를 들어, 한 단어의 문자들 중 연속된 고유 문자의 길이가 가장 긴 부분을 출력할 때, 슬라이딩 윈도우와 같은 패턴을 사용할 수 있다. 프로세스 ex. [1, 3, 2, 6, -1, 4, 1, 8, 2] 라는 배열이 있는데, 연속적인 5개의 숫자의 합이 최대값을 구한다고 가정을 해본다. [1, 3, 2, 6, -1], 4, 1, 8, 2 합 : 11 1.. 2023. 3. 24.
[Algorithm] Segment Tree (구간 트리) Segment Tree (구간 트리) 구간 트리는 배열의 특정 구간에 대한 질의를 빠르게하기 위해 사용할 수 있다. 예를 들어 어떤 구간의 최소치를 구하고 싶다고 해보자. 보통 사용하는 방법은 구간 내 숫자를 하나하나 확인하면서 최소치를 찾는 것으로, O(N)의 시간이 걸린다. 이때 배열을 전처리해 구간 트리를 사용하면 O(N log N)의 시간에 찾을 수 있다. 구간 트리는 '주어진 배열의 구간들을 표현'하는 이진 트리를 만든다. 루트는 배열의 전체구간을 표현하고, 한 트리의 왼쪽 자식과 오른쪽 자식은 해당 구간의 왼쪽 반과 오른쪽 반을 표현한다. 각 노드는 해당 구간에 대한 계산 결과를 저장해둔다. 이렇게 전처리해둔 트리가 있다면 어떤 구간 [i, j]가 주어지면 이 구간을 구간 트리의 노드에 포함된.. 2023. 3. 23.
[Algorithm] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm) 문자열 검색 문자열 검색 문제는 문자열 H가 주어졌을 때 문자열 N을 부분 문자열로 포함하는지 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제다. 이 문제를 풀 수 있는 가장 간단한 방법은 H의 가능한 모든 위치에서 다 시도해보는 방법이다. H의 각 위치의 부분 문자열이 N과 일치하는지 일일히 다 확인하는 것이다. 시작 위치의 수는 O(∣H∣)가 되고, 각각 비교에 걸리는 시간은 O(∣N∣)이 걸리기 때문에, 총 걸리는 시간은 O(∣H∣∣N∣)이다. C의 strstr(), C++의 string::find(), 자바의 indexOf(), 자바스크립트의 String.prototype.indexOf() 등 대부분 표준 라이브러리에서 사용된다. KMP(Knuth-Morris-Pratt).. 2023. 3. 23.
[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘 (Kruskal Algorithm) 이란 그래프 내의 모든 정점들을 가장 적은 비용(cost)으로 연결하기 위해 사용되는 알고리즘이다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용한다. 즉, 최소 신장 트리(MST, Minimum Spanning Tree)를 구하기 위한 알고리즘이다. 위 그래프가 있다고 가정할 때 노드의 개수는 5개고 간선의 개수는 6개다. 크루스칼 알고리즘의 핵심은 거리가 짧은 순서대로 그래프에 포함시키는 것이다. 크루스칼 알고리즘을 자세히 다루기 전에 신장 트리와 최소 신장 트리에 대해서 다뤄보자 신장 트리 (Spanning Tree) 신장 트리 (Spanning Tree)는 그래프의.. 2023. 3. 23.
[Algorithm] 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘 (Kadane's Algorithm) 카데인 알고리즘은 DP (Dynamic Programing)의 기법중 하나인데 DP를 간단하게 설명하자면 다음과 같다. Dynamic Programing : 하나의 큰 문제를 풀기위해 그 문제를 작은 문제들로 나눠 풀어나간 후, 결국 하나의 큰 문제를 풀어내는 방법이다. 카데인 알고리즘은 최대 부분합 문제를 풀때 주로 사용된다. 최대 부분합 문제 Arr = [-2,1,-3,4,-1,2,1,-5,4]; 다음과 같은 배열이 주어질 때 위의 순서를 유지하고, 연속적이면서 가장 큰 합을 가지는 부분배열은 다음과 같다. [4, -1, 2, 1] -> 합 : 6 Arr[4] = -1 를 마지막 원소로 갖는 부분 합과, Arr[5] = 2를 마지막 원소로 갖는 부.. 2023. 3. 20.
[Algorithm] 완전 탐색과 종류 (Brute Force Search) 완전 탐색, Brute Force Search 란? 완전 탐색과 브루트 포스의 이름에서 유추할 수 있듯이 이 알고리즘의 방법은 발생 가능한 모든 경우의 수를 전부 탐색하면서 조건에 맞는 답을 찾아내는 방법이다. 이 알고리즘의 대표적인 장점은 모두 확인하기 때문에 100%의 확률로 정답만을 출력한다는 것이다. 하지만 확실하게 확인하는 만큼 시간이 오래 걸리는 탐색기법이다. 💡 Brute : 무식한, 짐승 같은 + Force : 힘 - 무식하게 풀기 완전 탐색의 종류 구조로 나누어보면 선형 구조를 전체적으로 탐색하는 방법인 순차 탐색과 비선형 구조를 전체적으로 탐색하는 방법인 DFS / BFS가 대표적인 탐색 방법이다. 1. 브루트 포스 (Brute Force) 브루트 포스는 반복문과 조건문을 사용하여 가능.. 2023. 3. 20.
[Algorithm] Tail Recursion (꼬리 재귀) 재귀 함수 재귀 함수는 '기저 사례(base case)'와 '재귀적 관계(recurrence relation)'만 알면 정말 간단하게 구현할 수 있다. 그리고 보통 코드가 짧아서 가독성도 좋다. 쪼개지지 않는 가장 작업들을 가리켜 재귀 호출의 기저 사례(base case) 자기 자신과 관계를 맺는 형식을 재귀적 관계(recurrence relation) 하지만 장점이 있으면 단점도 있는 법이다. 재귀 호출을 할 때마다 콜 스택에 새로운 프레임이 쌓이고, 각 프레임은 지역 변수나 인수를 저장하기 위해 메모리를 사용한다. 이게 보통은 문제가 되지 않지만, 만약 각 프레임에서 기가바이트 단위의 데이터를 받아 처리해야 하는 경우에는 문제가 심각해질 수도 있다. 혹은 콜 스택이 너무 깊어지면 스택 공간이 가득차 .. 2023. 3. 19.

티스토리툴바