Category: Study

2019
0
StudyData Structure

동적 프로그래밍(Dynamic Programming)

동적 프로그래밍(Dynamic Programming) 알고리즘 문제Memoization 반복되는 결과를 메모리에 저장해서 다음에 같은 결과가 나올 때 빨리 실행되도록 하는 기법 함수의 입력이 같다면 그에 따른 출력이 같을 때만 사용할 수 있다.123456789101112131415161718192021# 재귀 함수 - 피보나치def fibo(n): i

0
StudyData Structure

최단 경로(Shortest path)

최단 경로 음수 사이클은 안되지만 음수 가중치는 된다. 방향 그래프(directed graph) - 방향 그래프는 대칭이 아니다. 가중치 그래프(weighted graph) 경로의 길이 = 에지 가중치의 합 최단 경로 알고리즘의 종류 하나의 출발점과 나머지 모든 목적지 Dijkstra Algorithm(음수 가중치가 없음) Bellman-Ford Alg

0
StudyData Structure

최소 비용 신장 트리(Minimum Cost Spanning Tree)

신장 트리 Spanning Tree 연결되어 있다(Connected) 최소 에지 수 = |E| = |V| - 1 트리의 조건 E와 V가 같으면 사이클을 돌게 되므로 |V| - 1이다. 최소 비용 신장 트리 MST(Minimum Cost Spanning Tree) 무방향 그래프 가중치 그래프 비용이 최소가 된다. 에지들의 비용이 가장 작은 트리를 구한다

0
StudyData Structure

그래프 순회(Graph traversal)

그래프(Graph)정의 그래프는 객체와 객체 사이의 ‘관계’를 표현하기 위한 자료구조이다. 그래프 G는 두 ‘집합’ V, E로 나타낸다. V(G) : 노드(node) 혹은 정점(vertex)의 집합 E(G) : 정점을 잇는 에지(edge)의 집합 방향1. 무방향 그래프(Undirected graph) 출처 : https://github.com/yth

0
StudyData Structure

균형 이진 트리(balanced-binary tree)

이진 탐색 트리(BST)는 O(log(n))의 시간 복잡도를 가진다. 이것은 탐색 트리가 균형 트리일 경우에만 해당된다. 출처 : https://github.com/ythwork/CS 위 그림처럼 최악의 경우, O(n)의 시간 복잡도를 가지게 된다. 균형 이진 트리 self-balancing(balanced-binary tree) 균형 이진 트리

0
StudyData Structure

분할 정복(Divide and Conquer)

분할 정복(Divide and Conquer) 알고리즘 문제분할 정복(Divide and Conquer) 먼저 분할하고 정렬하는 경우 - merge sort 먼저 정렬하고 분할하는 경우 - quick sort recursion(재귀)에서 중요한 것 base case(기저 조건) 재귀할 때 문제의 사이즈(부분 문제, sub problem)를 줄여야 한다

0
StudyData Structure

완전 탐색(Brute-force Search)

완전 탐색(Brute-force Search) 알고리즘 문제알고리즘 해결 전략 1권 p.157 소풍을 간 학생들을 두 명씩 짝 지어 행동하게 하려 한다. 서로 친구인 경우에만 짝을 지어야 한다. 서로 친구인 경우의 쌍이 주어질 때, 학생들을 짝 지을 수 있는 방법의 수를 구현해보자. 데이터 개수 n은 항상 짝수이다.12345678910111213141516

0
StudyData Structure

MAX HEAP

MAX HEAP 완전이진트리 배열, heapsize(배열의 개수가 아닌 데이터의 개수) Priority Queue 때문에 구현한다. ADT 1) is_empty() -> bool 2) is_full() -> bool 3) push(data) -> 반환없음 4) pop() -> 삭제된 원소 반환 5) top() -> 다음 번에 반환

0
StudyData Structure

동적 배열 vs 연결 리스트

동적 배열(Dynamic array) vs 연결 리스트(Linked list) 동적 배열(Dynamic array) 장점 : search - O(1) = Indexing 단점 : insert, delete - O(n) python의 동적배열은 list이다. append, pop - O(1)123456789다음과 같이 이미 할당된 배열의 공간이 있을 경

0
StudyData Structure

트리 순회(Tree traversal)

순회 재방문을 허용하지 않고 트리를 구성하는 모든 노드에 다해서 반드시 한번씩 방문하는 것 Queue 계열의 알고리즘 BFS(Breadth First Search) : 너비 우선 탐색 레벨 순서 순회(levelorder traversal) root를 시작으로 다음 레벨 왼쪽부터 방문123456789101112131415161718192021222324252