본문 바로가기

📚 Algorithm/Algorithm Note

(10)

Union-find 알고리즘 (Disjoint Set), 서로소 집합 Disjoint Set이란? 서로 중복되지 않은 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조라고 생각하면 된다. 흔히 서로소 집합 자료구조 라고도 한다. Union-Find 란? Union-Find는 서로소 집합을 표현할 때 사용하는 알고리즘이다. 집합을 표현하는 방법으로는 배열, 연결리스트 등을 이용할 수 있다. 그 중 가장 효율적인 트리 구조를 이용하여 구현한다. 보통 MST의 크루스칼 알고리즘에서 사용된다. 트리를 이용한 집합의 처리 - 같은 집합의 원소들은 하나의 트리로 관리한다. (자식 노드가 부모 노드를 가리킴) - 트리의 루트를 집합의 대표 원소로 삼는다. Union-Find 연산 Make-Set(x)..

알고리즘 - 유전 알고리즘 (Meta Heuristic), 최적해 찾기, 금괴 문제 유전 알고리즘 : Meta Heuristic 계열의 알고리즘 다양한 문제에 대해 경험적으로 솔루션을 제시하는 알고리즘 목적 주어진 문제에 대해서 최적의 솔루션을 찾는 것 (즉, 최적해를 찾는 것) 유전 알고리즘은 알고리즘 특성상 과정과 결과 설명이 굉장히 어려움. 무작위성이 존재함 생물학에서 생물들의 생존 법칙인 적자생존을 기반으로 한 알고리즘 환경에 적합한 개체가 살아남는다. 살아남은 개체는 번식을 한다. 살아남은 개체는 각각 부모가 되어 자손을 생성하는데, 자손은 부와 모의 유전자를 받고 때때로 돌연변이 유전자를 받아 다음 세대를 살아간다. → 위의 세 가지를 반복하면 환경에 적합한 개체들이 살아남고 그 개체들이 좋은 솔루션을 제시한다. 알고리즘에 쓰이는 용어와 표현 - 개체 : individual ..

Dynamic Programming(DP) 알고리즘 - 동적프로그래밍, Python으로 푸는 피보나치 Dynamic Programming 큰 문제를 나누어 작은 문제로 푸는 것 하나의 문제는 단 한 번의 풀이만 한다. Dynamic Programming 과 Recursion(재귀)의 차이점 DP와 재귀는 얼핏보면 '같은 문제가 반복적으로 일어나는 점' 에서 비슷하다고 생각할 수 있다. 하지만, 큰 차이점은 일반적인 재귀를 단순히 사용하면 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다. 가장 대표적인 예시는 피보나치 함수이다. DP 조건 두 가지 조건을 만족해야 한다. 1. 같은 문제가 반복적으로 발생 2. 최적 부분 구조 동일한 작은 문제들이 반복적으로 일어날 때, 같은 문제는 항상 정답도 같다. 즉, 중복 사용이 가능하다. DP 문제 풀이 방법 모든 작은 문제는 한 번..

알고리즘 - Greedy (탐욕 알고리즘, 욕심쟁이 알고리즘), 최적해 찾기 Greedy Alogrithm Greedy는 사전적인 의미로 '탐욕스러운', '욕심많은' 이라는 뜻을 가지고 있다. 탐욕 알고리즘 또는 욕심쟁이 알고리즘 라고도 불린다. 미래를 생각하지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 선택을 하는 기법 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 그리디 알고리즘 해결 방법 선택 : 현재 상태에서 최적의 해답 선택 적절성 검사 : 선택된 답이 문제의 조건을 만족하는 지 확인 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다. 그리디 알고리즘 조건 그리디 알고리즘을 적용하기 위해서는 2가지 조건을 성립해야 한다. 1. 탐욕적 선택 속성 (Greedy Choice Prop..

알고리즘 - Sort 정렬 (Merge sort, Quick sort), Python 코드 Merge Sort (병합정렬) - 일반적인 방법으로 구현했을 때 이 정렬은 안정정렬에 속하며, 분할 정복 알고리즘 중의 하나이다. - 분할 정복 알고리즘 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 대개 순환호출을 이용하여 구현한다. - 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. - 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. - 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다. - 결합(Com..

알고리즘 - Sort 정렬 (Selection sort, Insertion sort, Bubble sort), Python 코드 Sort (정렬) n개의 숫자가 입력으로 주어졌을 때, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘 Sort 알고리즘 종류 Selection sort Insertion sort Bubble sort Merge sort Quick sort 기초적인 정렬 알고리즘 평균적으로 O(n^2)의 시간이 소요되는 정렬 알고리즘 - Selection sort (선택정렬) - Insertion sort (삽입정렬) - Bubble sort (버블정렬) 고급 정렬 알고리즘 평균적으로 O(nlogn)의 시간이 소요되는 정렬 알고리즘 - Merge sort (병합정렬) - Quick sort (퀵정렬) - Heap sort (힙정렬) Selection sort (선택정렬) - 제자리 정렬 알고리즘 - 해당 순..

이전 1 2 다음

728x90

티스토리툴바