프로그래밍
-
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)프로그래밍/알고리즘 2019. 5. 26. 15:45
Goal 너비 우선 탐색(BFS, Breadth-First Search)의 개념 너비 우선 탐색(BFS, Breadth-First Search)의 특징 너비 우선 탐색(BFS, Breadth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색은 시..
-
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)프로그래밍/알고리즘 2019. 5. 23. 11:51
Goal 깊이 우선 탐색(DFS, Depth-First Search)의 개념 깊이 우선 탐색(DFS, Depth-First Search)의 특징 깊이 우선 탐색(DFS, Depth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 미로를 탐색하는 ..
-
[자료구조] 그래프프로그래밍/자료구조 2019. 5. 16. 00:23
그래프란? : 그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. 그래프는 정점과 간선들의 집합이라고 할 수 있습니다. 그래프는 보통 지도에서 자주 사용하는 자료구조인데, 예를 들어 인천에서 서울까지의 최단거리, 최소비용 등을 구하는 데 사용합니다. 필요한 개념 및 용어 1. 정점(vertex) 와 간선(edge) 정점은 그래프의 위치, 간선은 정점들 간의 관계를 의미합니다. 2. 무방향 그래프(undirected graph) 와 방향 그래프(directed graph) 무방향 그래프는 간선을 통해 양 방향 이동이 가능하다. 방향 그래프는 간선을 통해 단 방향 이동이 가능하다. 3. 가중치 그래프(weight graph) 간선에 연결 강도를 표시할 수 있는 그래프 (ex..
-
[알고리즘] 해시 테이블 (Hash Table)프로그래밍/알고리즘 2019. 4. 30. 10:38
개념 Hash Function : 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이 때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다.(H(s1) = H(s2)) 아래 사진의 경우에는 좌측에 파란 색들이 key이며 각 key값들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시 테이블에서는 이 key을 해시한 결과를 배열의 인덱스로 사용한다. 해시 함수를 H()라고 했을 때 H(Jonh Smith) = 02 해시 충돌(Hash Collision) 서로 다른 문자열을 해시한 결과가 동일한 경우 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s..
-
[알고리즘] KD 트리 , KDB 트리프로그래밍/알고리즘 2019. 4. 30. 10:26
개념 이진검색트리를 확장한 것으로 두개 이상의 key 를 사용합니다. 다른 말로 다차원 검색트리로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기합니다. 현재 그림은 두개의 key 를 갖고있는 KD 트리이다. 왼쪽 key 를 x, 오른쪽 key 를 y 라고 생각 한다면 깊이 1 위치에 A 에서는 처음에 x 를 기준으로 작으면 왼쪽 크면 오른쪽으로 분리한다. 그리고 깊이 2 위치에 B,C 에서는 y 의 값을 기준으로 깊이 3 에서는 x의 값을 기준으로 삽입을 한다. 삭제 1. 자식이 없는 경우 : 노드만 제거 2. 자식이 하나뿐인 경우 : 자식이 둘인 경우와 같이 해결 : 왼쪽 자식만 있는경우, 왼쪽 서브트리 중 노드 r에서의 분기에 사용한 필드 값이 가장 큰 노드를 찾아서 이동 3. ..
-
[알고리즘] B 트리프로그래밍/알고리즘 2019. 4. 29. 16:44
기본개념 B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해서 키를 다수 보유하고 있는 트리라고 할 수 있다. B-트리의 조건 모든 단말노드는 동일한 높이를 가진다. 각 내부노드의 자식노드는 M/2 이상 M 이하이다. (M은 2보다 큰 정수로서 트리노드의 최대 자식 수) 루트의 자식 수는 두개 이상이다. ...더보기 우리는 트리의 높이를 최소화 하기 위해 자가균형트리를 배웠다. (레드블랙트리, AVL 트리) B트리는 키의 갯수를 증가시켜 트리의 좌우를 넓히는 방법으로 높이를 낮췄다고 생각하면 도움이 될것이다. 탐색 B트리는 이진트리와 마찬가지로 중위순..
-
[알고리즘] 레드-블랙트리(Red-BlackTree) -Insert프로그래밍/알고리즘 2019. 4. 8. 23:20
이진탐색트리(BST)를 기반으로 구성된 자료구조입니다. BST의 설명은 여기에 있습니다. 따라서 BST의 설명은 본 게시물에서는 하지 않습니다. 개념설명 : 우선 이진탐색트리를 잠깐 봅시다. 이진탐색트리는 Search, Insert, Delete 가 가능한 이진트리였습니다. 이때, 평균 시간복잡도는 O(log n) 이였죠. 하ㄴ지만 이진트리가 극단적으로 편향됬을때시간복잡도는 O(N) 이 됩니다. 이건 이진트리의 깊이(h) 많큼 탐색을 한다는 의미입니다. 이러한 문제들을 해결하기 위해 나온 것이 바로 레드-블랙트리(Red-BlackTree) 입니다. 다른 말로 Balanced Binary Search Tree 라고도 합니다. 이유는 이진탐색트리의 깊이를 항상 log N 으로 유지시켜주기 때문입니다. 따라서..
-
[알고리즘] 이진탐색트리(BST)프로그래밍/알고리즘 2019. 4. 7. 16:11
이진탐색트리(BST)는 링크드리스트를 기반으로 한 탐색 알고리즘입니다.그래서 링크드리스트를 모르시면 꼭! 자료구조를 통해 공부를 하시고 읽으시길 바랍니다. 본 게시물이선 BST에 대해서만 설명합니다. 이해 순서 포인터를 정확히 이해한다. 링크드리스트를 이해한다. 완전 이진트리를 이해한다. 이진 탐색트리를 이해한다. 이진탐색트리(BST) 란 ? : 방탄소년단(BST) ? 죄송합니다. 이진탐색트리는 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종입니다. 이진탐색은 탐색에 필요한 시간복잡도가 O(logN)으로 빠르지만 자료 입력과 삭제가 불가능합니다. 연결리스트의 경우는 입력과 삭제의 시간복잡도가 O(1)로 빠르지만 탐색하는 시간복잡도는 O(n)으로 매우 비효율..