Computer Science (42) 썸네일형 리스트형 [Algorithm] DFS 1. DFS (Depth First Search, 깊이 우선 탐색) 그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로 탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다. DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder tr.. [Algorithm] Binary Search Algorithm Binary Search Algorithm (이진 탐색 알고리즘) 이진 탐색 알고리즘은 탐색 알고리즘의 하나로 이미 정렬되어 있는 배열을 대상으로 원하는 값을 찾는 알고리즘이다. 정렬되어 있는 배열의 중간의 값과 타겟이 되는 값을 비교해서 탐색을 진행한다. 중간값과 타겟이 동일하다면 해당 값을 반환한다. 만약 타겟이 되는 값이 중간값보다 큰 경우 중간 값을 기준으로 우측, 작다면 중간 값을 기준으로 좌측의 부분 배열을 대상으로 반복적으로 탐색을 진행한다. 이때 대상이 되는 배열의 왼쪽 인덱스가 오른쪽 인덱스보다 크다면 값이 없는 것으로 판단하여 탐색을 중단한다. 위의 예제 이미지는 정렬되어있는 배열에서 타겟 값인 23을 탐색하려고 한다. 첫번째 과정에서 중간값은 16 이다. 16은 타겟 값인 23 보다 .. [DS] Hashing 1. hash table hash table은 hashing을 통해서 데이터를 저장하는 데이터 구조이다. hashing은 내부적으로 hash function 을 사용하여서 key와 value를 mapping 하여 hash table에 저장하여 데이터 구조를 형성하는 것을 의미한다. hash table에 데이터의 key와 value가 mapping 되어 저장되기 때문에 탐색에서 average case에 대해서 시간 복잡도가 O(1)이 된다. collision이 발생하는 경우에는 O(1)의 시간 복잡도를 보장할 수 없다. 그렇기 때문에 hash table에서의 성능은 hash function과 collision 발생 시의 정책에 따라 달라진다. 다음 예제는 hash table의 크기가 6이고 hash fun.. [DS] Graph MST & Shortest path - 이전 글: [DS] Graph 개념과 탐색방법 3. MST (Minimum Spanning Tree) 최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다. 최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 1) Kruskal algorithm greedy 한 방법으로 간선을 선택하여서 .. [DS] Graph 개념과 탐색방법 1. Graph 그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다. 1) 용어 Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프 Directed Graph: 정점과 간선의 연결관계에서 간선의 방향.. [DS] Heap 1. Heap 힙은 Tree 구조를 기반으로 한 자료구조의 일종으로 배열로 구현한 Complete Binary Tree (완전이진트리) 구조로 이루어져 있다. 힙은 root 노드에 위치하는 값의 성질에 따라 max heap과 min heap 두가지로 나뉜다. 1) max heap: 각 노드의 값이 해당 child 노드들의 값보다 큰 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 큰 값을 가진다. 2) min heap: 각 노드의 값이 해당 child 노드들의 값보다 작은 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 작은 값을 가진다. 2. 배열을 통한 구현 heap을 배열로 구현하게 되면 root 노드의 인덱스가 0이 되고, 뒤이어서 나머지 노드들의 값이 저장된다. 이때 heap은 완.. [DS] Tree & Binary Tree 1. Tree 트리는 비선형 자료구조로 부모와 자녀로 이루어진 계층적 관계를 가진 자료구조이다. 1) 용어 - Node: 노드. 트리를 구성하고 있는 각각의 요소를 의미한다. - Edge: 간선. 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미하다. - Root Node: 루트 노드. 트리 구조에서 최상위에 있는 노드 (뿌리)를 의미한다. - Terminal Node (leaf Node): 단말 노드. 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. - Internal Node: 내부 노드, 비단말 노드. 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. - degree: 차수. 자식 노드의 개수. - height: 높이. 트리에서 루트 노드부터 가장 깊은 리프 노드까지의 길이. -.. [DS] Stack & Queue 1. Stack 스택은 선형 자료구조의 하나로 LIFO (Last In First Out) 또는 FILO (First In Last Out)라 불리는 구조로 이루어져 있다. 데이터 삽입시에 삽입되는 순서대로 스택 안에 차곡차곡 쌓이고, 출력시에는 마지막에 삽입된 데이터부터 역순으로 출력되는 식으로 데이터가 운영된다. 수식의 계산이나 서브 함수 실행 후의 복귀 등 재귀적인 상황에서 많이 사용한다. - Stack 자바 구현 더보기 import java.util.Arrays; import java.util.EmptyStackException; public class CustomStack { private static final int DEFAULT_CAPACITY = 10; private Object[] el.. 이전 1 2 3 4 5 6 다음
