자료구조 & 알고리즘/알고리즘
-
[ Algorithm ] Kruskal & UnionFind 알고리즘자료구조 & 알고리즘/알고리즘 2022. 6. 6. 02:33
크루스칼 알고리즘을 이해하는데 필요한 최소신장트리, UnionFind 알고리즘과 함께 공부 내용을 정리해보려고 합니다. 📌 최소신장트리 최소 비용 신장트리, 최소신장트리, MinimumspanningTree , MST 등등으로 불림 그래프 내의 최소 비용으로 모든 정점을 포함하는 트리 트리라는 말 속 노들들의 연결과 함께 사이클이 존재하지 않음을 내포하고 있음 크루스칼알고리즘과 프림 알고리즘등을 통해 구현가능 📌 크루스칼 알고리즘 코스트, 거리 등에 대해 오름차순으로 정렬한다. 오름차순으로 순회하며 사이클이 발생하지 않는다면 해당 노드를 연결 시킨다. 사이클에대한 판단은 UnionFind 알고리즘을 사용한다. 📌 Union-Find 알고리즘 여러개의 노드가 존재할 때 노드들 끼리 서로 같은 그래프에 속하..
-
[알고리즘] 힙 (programmers.이중우선순위큐)자료구조 & 알고리즘/알고리즘 2022. 5. 14. 15:48
📌 힙 알고리즘 이란? 완전 이진트리 기반의 트리형 자료구조 최댓값, 최소값을 찾아내는데 용이 최대힙 : 부모가 최대 값 , 최소힙 : 부모가 최소값 📌 힙 구조 (최대 힙) 부모 노드가 최대 값을 가짐 같은 깊이 내에서 왼쪽 >= 오른쪽 값 📌 시간 복잡도 힙 추가,삭제 : O(log N) 힙 정렬 : O(N log N) 일반 리스트를 힙 구조로 바꾼 다고 생각했을 때 한개씩 N 개 추가함 == 힙 정렬 시간 복잡도 📍 사용 의의 다른 고급 정렬과 같은 시간복잡도를 가지지만, 최대 최소 원소의 삽입, 삭제가 반복해서 일어나는 경우에 대해서 힙 자료구조를 사용하면 정렬이 아닌 원소 추가, 삭제 시간 복잡도가 적용되서 효율적임 📌 예제 : Programmers.이중 우선순위 큐 힙은 자바, 코틀린 에서 우..
-
[ 알고리즘 ] 그래프 & DFS , BFS자료구조 & 알고리즘/알고리즘 2022. 3. 8. 00:49
인접행렬에 대한 탐색문제에서 대표적으로 쓰이는 DFS 와 BFS 를 정리해보고자 합니다. 처음에는 DFS , BFS 의 구현에 있어서 잘 이해가 되지 않았지만 틀을 외워서 사용하다 보니 잘 이해가 되었습니다. 저와 같은 분이 계시다면 이 방법을 추천드립니다!! 공통 간선의 데이터를 자료형에 맞게 저장할 수 있어야합니다. 이차원 배열 형태 이차원 배열 + 내부적으로 mutablelis 필요에 따라서 방문한 위치를 표시 할 수 있어야 합니다. 위에서 저장한 이차원 배열을 수정 할 수 도 있음 따로 행렬을 만들어 관리 할 수 도 있음 BFS 너비 우선 탐색으로서 그래프와 트리 탐색 알고리즘이다. 자식 노드보다 형제 노드를 우선적으로 방문한다는 특징을 가진다. 구현의 핵심은 방문할 리스트를 생성하고 방문할 리스..
-
[알고리즘] Sliding Window자료구조 & 알고리즘/알고리즘 2021. 10. 29. 14:59
Sliding Window 슬라이딩 윈도우는 연속적인 리스트나 배열의 원소들의 값들을 비교하기 위한 알고리즘입니다. 예제 > 현수의 아빠는 제과점을 운영합니다. 현수 아빠는 현수에게 N일 동안의 매출기록을 주고 연속된 K일 동안의 최대 매출액이 얼마인지 구하라고 했습니다. 만약 N=10이고 10일 간의 매출기록이 아래와 같습니다. 이때 K=3이면 [2, 4, 7, 10, 8, 4, 5, 6, 7, 1] 연속된 3일간의 최대 매출액은 7+10+8=25만원입니다. 직관적인 방법으로 구현한다면 다음과 같이 구할 수 있습니다. public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); i..
-
[고급정렬 ]: 병합정렬자료구조 & 알고리즘/알고리즘 2021. 9. 16. 15:57
병합 정렬(merge sort) 알고리즘 핵심 안정 정렬에 속하며 대표적인 분할정복 알고리즘중 하나이다. 분할정복이란? 분할정복은 일반적으로 재귀 호출을 사용한다. devide : 문제를 한개 또는 둘 이상으로 나눈다 conquer : 나누어진 문제가 충분히 작고 해결 가능하다면 해결한다. devide 와 conquer 를 반복하며 결과를 합쳐서 문제를 해결한다 과정 리스트의 길이가 1일때 가지 두개로 양분하여 분할한다. (재귀 호출) 길이가 충분해졌다면 해당 리스트들을 정렬하여 합친다. 시간복잡도 O(nlogn) 을 갖게된다. 병합 정렬(merge sort) 예제 코드(파이썬) # 병합정렬 def splite_merge(lst:list): if len(lst) < 2: return lst else: l..