본문 바로가기

자료구조와 알고리즘40

1. 선택정렬 다음 숫자를 오름차순으로 나열하고 싶다면? 10 9 8 7 6 5 4 3 2 1 첫 번째로 가장 직관적인 생각은 가장 작은 것을 선택해서 앞으로 보내는 방법은 어떨까? 이 방법을 바로 "선택 정렬" 알고리즘이라고 합니다. package algorithm; public class algorithm01 { public static void main(String[] args) { int min =0 , temp =0, index = 0; int[] array = {10,9,8,7,6,5,4,3,2,1};//index배열을 크기값10으로 초기화.및 선언 for(int i =0; i 2021. 5. 30.
Shell Sort 셸 정렬 목표 삽입 정렬을 이해한다. 삽입 정렬을 구현할 수 있다. 삽입 정렬의 시간 복잡도 삽입 정렬에서 장점으로부터 착안된 쉘 정렬을 이해한다. 셸 정렬을 구현할 수 있다. 셸 정렬의 gap sequence에 대해서 이해한다. 셸 정렬의 시간 복잡도 셸 정렬은 삽입 정렬이 어느 정도 정렬된 상태에서 상당히 빠른 정렬 속도를 보인다는 점에서 착안하여 삽입 정렬을 수행하기 전에 어느 정도를 정렬한 상태에서 삽입 정렬을 하면 좋은 시간 복잡도를 기대할 수 있다는 생각에 만들어진 알고리즘이다. 그렇기 때문에 삽입 정렬에 대한 기본적인 이론을 익힌 이후 추가적으로 셸 정렬까지 공부해본다. 삽입 정렬 삽입 정렬은 현재 비교하고자 하는 target과 그 이전의 원소들과 비교하여 자리를 swap 하는 정렬 알고리즘이다. 삽.. 2021. 5. 30.
백 트래킹 기법 1. Back Tracking 백트래킹 혹은 퇴각 검색으로 불려진다. 제약 조건 만족 문제에서 해를 찾기 위한 전략 중 하나로 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약조건을 만족할 수 없다고 판단되는 즉시 다시는 이 후보군을 체킹 하지 않을 것을 표기한 다음 다른 후보군으로 넘어가는 방법이다. 실제 구현시 모든 경우의 수를 상태 공간 트리를 통해 표현한다. - 각 후보군을 DFS 방식으로 확인 1) Promising : 해당 루트가 조건에 맞는지를 검사하는 기법 2) Pruning : 조건에 맞지않으면 포기하여 탐색 시간 절약하는 기법 즉 백트래킹은 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는 지제크 하고 조건이 다르다면 더 이상 자식 노드.. 2020. 9. 9.
프림 알고리즘 프림 알고리즘(Prim's algorithm) 대표적인 최소 신장 트리 알고리즘으로 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고 해장 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해나가는 방식이다. 크루스 칼 알고리즘과 프림 알고리즘 두 개의 알고리즘 다 탐욕 알고리즘을 기초로 하고 있다. 다만 크루스칼 알고리즘은 가장 가중치가 작은 간선을 선택하면서 MST를 구하지만 프림 알고리즘은 특정 정점에서 시작해 해정 정점에 연결된 가장 적은 가중치를 가진 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구한다. 파이썬 코드 from collections import def.. 2020. 9. 9.
크루스칼 알고리즘 신장 트리에서도 말했듯이 크루스 칼 알고리즘은 최소 신장 트리를 구현하기 위한 알고리즘이다. 이때 크루스칼의 시간 복잡도를 낮추기 위해 path-compression 기법과 , union-by-rank기법을 사용한다. 구현 트리는 노드와 브랜치로 이루어져 사이클을 돌지 않는 그래프에서 나온 데이터 구조이다. 따라서 그래프를 먼저 생성한다. graph ={ 'vertices' : ['A','B'.....'G'], 'edges' : [ (7,'A','B') .... ] } 여기서 vertices는 노드를 이야기하며 edges는 간선으로 연결된 노드와 간선의 가중치를 의미한다. 변수 선언 parent =dict() //path-compression을 위한 부모 딕셔너리이다. rank = dict() //uni.. 2020. 9. 9.
신장 트리 신장 트리란? Spanning Tree, 또는 신장 트리라 불린다. 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프를 말한다. 조건은 다음과 같다 - 본래의 그래프의 모든 노드를 포함해야한다. - 모든 노드가 서로 연결되어야 한다. - 트리의 속성을 만족시켜야 한다. (사이클이 존재하지 않는다.) 최소 신장 트리 MST 가능한 ST 중에서 간선의 가중치 합의 최소인 ST를 지칭한다. 최소 신장 트리 알고리즘 그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재한다. 대표적으로 크루스 칼 알고리즘과 프림 알고리즘이 있다. 1) 크루스칼 알고리즘 1. 모든 정점을 독립적인 집합으로 만든다. 2. 모든 간선을 비용 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 .. 2020. 9. 9.
탐욕 알고리즘 탐욕 알고리즘이란? Greedy algorithm 또는 탐욕 알고리즘 이라고 불리운다. 최적의 해에 가까운 값을 구하기 위해서 사용되며 여러 경우 중 하나를 선택해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종값을 구하는 방식이다. 예를 들어 4720원을 1원 50원 100원 500원으로 지불하되 가장 적은 동전만 낸다고 생각하자. 여러 경우중 500원을 가장 많이내는 경우가 최적이고 그 다음은 100원 ... 이렇게 진행해서 최종값을 구할 수 있게된다. coin_list=[500,100,50,1] price = 4720 def coin(coin_list,price): total_coin =0 details=list() for coin in coin_list: coin_.. 2020. 9. 8.
너비 우선 탐색 && 깊이 우선 탐색 1. BFS와 DFS란? 대표적인 그래프 탐색 알고리즘이다 BFS는 Breadth-First Search약자로 너비 우선 탐색이며 정점들과 같은 레벨에 있는 형제 노드들을 먼저 탐색하는 방식이다. 이와 다르게 DFS는 Depth First Search의 약자로 깊이 우선 탐색이며 정점의 자식들을 먼저 탐색하는 방식이다. BFS 알고리즘 구현 자료구조 큐를 사용한다. 각 노드에 연결된 정점의 노드들을 나타낸 표이며 KEY와 VALUE형식으로 나타낸다. 그래프는 위 이미지의 DFS를 따른다. KEY VALUE a b c b a d e c a f g d b h e b i j f c k g c h d i e j e k f 탐색을 위한 큐 방문한 큐 a 최상위 노드의 a를 방문해야 하는 큐에 넣는다. 방문해야 하.. 2020. 9. 8.
병합 정렬 병합 정렬은 재귀 용법을 활용한 정렬 알고리즘이다. 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이 병합 정렬은 분할 정복의 알고리즘 기법입니다. 분할 정복은 문제를 부분 문제로 나누며 이때 나누어진 부분 문제는 중복되지 않아야 합니다. 이러한 부분 문제를 통해 상위 문제를 해결하는 방법이며 하향식 즉 아래에서부터 위로 해결하는 방식입니다. 자바 코드 배열을 받아 분할한다. public static List split(List data) { List leftSplit = new ArrayList(); List rightSplit = new ArrayLis.. 2020. 9. 7.
힙 힙이란? 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고 최대, 최솟값을 찾기 위해선 O(n)이 걸림 이에 반해서 힙에 데이터를 넣고 최대 최소를 찾기위해선 O(logn)이 걸림 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다. 힙의 구조 힙은 최댓값을 구하기 위한 구조와 최솟값을 구하기 위한 구조로 분류할 수 있다. 힙의 조건 1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙) 2. 최소 힙은 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다. 3. 완전 이진트리 .. 2020. 9. 3.

티스토리툴바