티스토리

코딩은 잼있어

검색하기

블로그 홈

코딩은 잼있어

gold-jae.tistory.com/m

코딩은 잼있어 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

Prim 알고리즘 - 최소 신장 트리(MST) Prim 알고리즘 - 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(mst)란 ? 그래프에 있는 모든 정점들을 가장 적은 가중치의 합으로 연결하는것을 말한다. MST의 특징 N개의 정점과 N-1개의 간선으로 이루어진 무방향 그래프 사이클을 형성하면 안된다. 대표적인 알고리즘으로 Prim 알고리즘, Kruskal 알고리즘, dijkstra알고리즘이 있다 MST는 도로건설이나 통신 등 거리나 비용을 최소로 요구하는곳에 사용됨 Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택면서 MST를 만들어가는 방식 시작 정점을 기준으로 하여 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택 N-1개의 간선을 가질때 까지 반복 과정 시작정점인 0번에서 가중치가 가장 작.. 공감수 0 댓글수 0 2020. 11. 7.
[자료구조] 힙(heap) 나만의정리 자료구조 힙(heap)이란 ? 힙은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 여러개의 값중에서 최대값이나 최소값을 빠르게 찾아내는 구조다. 힙 트리의 경우에는 중복된 값을 허용한다(이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙(heap)의 종류 힙의 종류는 최대힙과 최소힙이있다. 최대힙(max heap) 부모의 노드값이 자식 노드의 값보다 큰 완전 이진 트리 최소힙(min heap) 부모의 노드값이 자식 노드의 값보다 작은 완전이진트리 힙(heap)의 성질 힙에서 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모 인덱스) x 2 오른 자식의 인덱스 = (부모 인덱스) x 2 + 1 부모의 인덱스 = (자식 인덱스) / 2 예시) 2 (숫자 7의 인덱스) =.. 공감수 0 댓글수 0 2020. 11. 4.
퀵정렬(Quick Sort) 퀵정렬(Quick Sort) 퀵정렬은 분할정복 알고리즘으로, 병합정렬과 달리 비균등하게 분할하고 병합해 나갑니다. 과정 리스트안에 하나의 원소을 고른다. 이때 이 원소를 pivot 이라고 한다. pivot을 기준으로 피봇보다 작은건 왼쪽으로, 큰건 오른쪽으로 옮겨진다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하기 위해 분할된 리스트들에 대해 1, 2번과정을 반복한다. 더이상 분할이 불가능할때까지 반복한다 예시로 알아보는 퀵정렬 처음 pivot = 3으로 설정한뒤 3을 기준으로 왼쪽과 오른쪽을 정렬한다. pivot을 기준으로 두개의 리스트로 나눠진 부분에서 각각 1과 6을 pivot으로 정한뒤 왼쪽과 오른쪽으로 정렬한다. 이런 과정을 더이상 분할이 불가능할때까지 반복한다 퀵정렬 코드 def .. 공감수 0 댓글수 0 2020. 11. 3.
병합정렬(Merge Sort) 병합정렬(Merge Sort) 병합정렬은 전체 리스트를 두 개의 균등한 크기로 분할하면서 하나의 원소로 분할될때까지 계속해서 반복합니다. 분할을 끝내면 합병하는 과정을 거치면서 리스트를 정렬해나갑니다. 분할 정렬되지 않은 리스트를 하나의 단위로 각각 분할합니다. 병합 하나의 단위로 분할된 원소들을 비교해나가면서 병합을 진행합니다. 2개의 리스트를 병합할때 매번 sort를 진행하는데 2개의 리스트의 첫번째 자리부터 비교해나가면서 sort를 진행하면 됩니다. python 코드 # 1. 분할 def merge_sort(arr): # arr : 정렬이 안된 리스트 if len(arr) 공감수 0 댓글수 0 2020. 10. 13.
최소신장트리(MST) 나만의 정리 최소 신장 트리(Minimum Spanning Tree) 최소 신장 트리(mst)란 ? N개의 정점으로 이루어진 무방향 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리 최소 신장 트리란 무방향 가중치 그래프에서 사이클을 형성하지 않고 가중치의 합이 최소를 구하는 트리 알고리즘 대표적인 알고리즘으로 Prim 알고리즘, Kruskal 알고리즘, dijkstra알고리즘이 있다 0. 목차 Prim 알고리즘 Kruskal 알고리즘 dijkstra 알고리즘 1. Prim 알고리즘 하나의 정점에서 연결된 간선들 중에 하나씩 선택면서 MST를 만들어가는 방식 임의 정점을 하나 선택해서 시작 선택한 정점과 인접하는 정점들 중의 최소비용의 간선이 존재하는 정점을 선택 모든 정점이 선택될 때 까지 1,2과정을 반.. 공감수 0 댓글수 0 2020. 9. 3.
Trie 나만의정리 Trie 트라이는 문자열 비교를 위해 필수적인 알고리즘이다. 특히 특정 긴 문장에서 임의의 단어를 찾기위해 효율적으로 쓰이는 자료구조이다. 문자열 비교를 할때 이진검색트리의 경우 한 레벨당 한문자씩 저장되므로 문자열의 최대길이 M을 곱한 시간복잡도 O(MlogN)이지만, 트라이를 이용할경우 O(M)의 시간복잡도를 갖는다. 아래는 Trie의 동작과정을 나타낸다. chj, ckv, bq, ba의 문자열이 있다고 가정할때, 아래는 해당 문자열의 트리구조를 보여준다 Trie 코드 # 트라이 구조에 필요한 노드 class Node(object): def __init__(self, char, data=None): self.char = char self.data = data self.children = {} clas.. 공감수 0 댓글수 0 2020. 8. 23.
그래프 나만의 정리 그래프 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현한다. 그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조 선형자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기 용이하다 0. 목차 그래프 유형 그래프 표현 그래프 순회 서로소 집합 1. 그래프 유형 무향그래프(Undirected Graph) 방향이 없는 그래프 유향 그래프(Directed Graph) 방향이 있는 그래프 가중치 그래프(Weighted Graph) 간선에다 가중치를 부여 사이클 없는 방향 그래프(DAG, Directed Acyclic Graph) 시작과 끝점이 같은 단순 경로 그래프 2. 그래프 표현 인접행렬(Adjacent matrix) v.. 공감수 2 댓글수 0 2020. 6. 29.
백트래킹(Backtracking) 나만의 정리 백트래킹(Backtracking) 여러가지 선택지들이 존재하는 상황에서 한가지를 선택한다. 선택이 이루어지면 새로운 선택지들의 집합이 생성된다. 이런 선택을 반복하면서 최종상태에 도달한다. 올바른 선택을 계속하면 목표상태(goal state)에 도달한다. 1. 백트래킹 개념 모든후보를 검사?? Nope!! 백트래킹 기법 어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가(backtracking) 다음 자식노드로 감 어떤 노드를 방문하였을때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망한다고 한다. 가치지기(pruning) : 유망하지 않는 노드가 포함된 경로는 더 이상 고려하지 않는.. 공감수 0 댓글수 0 2020. 6. 29.
분할정복 (Devide and Conque)과 이진검색 분할정복 (Devide and Conque)과 이진검색 분할정복을 이용한 대표적인 정렬알고리즘인 병합정렬과 퀵정렬에 대해 알아볼것이다. 실제 전략 : 분할 => 정복 => 통합과정으로 이루어진다 (1). 병합정렬 정렬된 자료의 집합을 한 개의 정렬된 집합으로 만드는 정렬 알고리즘 ex) 6 2 5 1 => 26 15 => 1256 자료를 최소단위로 나눈후에 차례 소스코드 방법 1. append와 pop을 이용한 방법 # 분할과정 def merge_sort(arr): # 문제를 절반으로 나누는 함수 # print(arr) if len(arr) == 1: print(arr) return arr # 절반으로 나누어서 각각 별도의 정렬실행 mid = len(arr)//2 left = arr[:mid] right.. 공감수 0 댓글수 0 2020. 6. 29.
탐욕알고리즘(greedy) 나만의 정리 탐욕알고리즘(greedy) 탐욕 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법 각 선택 시점에서 이루어지는 결정은 지역적으로는최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다 쉬운예) 지금 선택하면 사탕 10개를 주고, 1분뒤 선택하면 사탕 20개를 준다고할때, 탐욕알고리즘은 지금 선택하지만 이 선택이 최선은 아니다. 1. 탐욕알고리즘 동작과정 해 선택 현재 상태에서 부분 문제의 최적해를 구한뒤, 이를 부분해 집합에 추가한다. 실행 가능성 검사 새로운 부분해 집합이 실행가능한지를 확인한다. 곧, 문제의 제약 조건을 위반하지 않는지를 검색한다. 해 검사: 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. ex) 2370원을 거슬러주자!( 결.. 공감수 0 댓글수 0 2020. 6. 29.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.