본문 바로가기

알고리즘37

[MST] Chapter 04. Prim 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/9b505b2dbc9bb895add268c2114b1ba33fec4f3a Prim 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@9b505b2 developeSHG committed Aug 17, 2023 github.com 크루스칼 알고리즘과 거의 유사하다. 다른 부분은 간선을 어떻게 수집할 것인지 순서가 달라진다. 크루스칼 알고리즘은 탐욕적인 방법을 이용했다. 작은 간선부터 탐색해서 사이클이 발생하지 않는 간선을 추가해줬다. 위처럼 그룹을 나누다가 경우에 따라 그룹을 병합했다. 프림 알고리즘은 하나의 시작점으로 구성된 트리에.. 2023. 8. 16.
[MST] Chapter 03. Kruskal 알고리즘을 이용한 맵 생성 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/ea4d99bf27f79da3e7b4f924d6e2ca50d9c63744 Kruskal 알고리즘을 이용한 맵 생성 · developeSHG/Data_Structure-Algorithm@ea4d99b developeSHG committed Aug 17, 2023 github.com 미로라면, 랜덤성이 보장이 되야하는데 코드 특성상 아래랑 우측이 일직선으로 뚫린 현상으로 맵이 만들어지게 했었다. 이 부분을 개선시키기 위해 Kruskal 알고리즘을 이용한 맵 생성을 해볼 것이다. Kruskal을 어떻게 응용할 지 생각해보면 BST를 만들 때, 어떻게 만들었는지를 생각해보자. 이전까지.. 2023. 8. 16.
[MST] Chapter 02. Kruskal 알고리즘 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/e91776c4a5ed1f8b2a4cb1104ac89349e77c8bcf Kruskal · developeSHG/Data_Structure-Algorithm@e91776c developeSHG committed Aug 17, 2023 github.com 다시 복습하면 그래프는 [현실 세계의 사물이나 추상적인 개념간]의 [연결 관계]를 표현한다 했었다. 전형적인 그래프는 정점들과 정점들을 연결하는 간선으로 이루어진 것이 그래프였고, 예로 소셜 네트워크 관계도, 지하철 노선도를 그래프로 표현할 수 있었다. 위 사진처럼 정점에 대한 간선을 연결해서 모든 길을 뚫어놓은 상태이고, BF.. 2023. 8. 16.
[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.

티스토리툴바