Computer Science/Data_Structure
-
선택 정렬(selection sort) 란?Computer Science/Data_Structure 2020. 1. 7. 02:07
선택 정렬의 원리 선택 정렬(selection sort)은 가장 이해하기가 쉬운 정렬 방법이다. 선택 정렬은 다른 추가 메모리를 요구하지 않는 정렬 방법인 제자리 정렬(in-place-sorting)을 이용한다. 초기 배열에서 최소값을 찾는다. 이 최소값을 배열의 첫번째 요소와 교환한다. 그리고 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 위의 절차를 (배열원소-1)만큼 반복하면 추가적인 배열을 사용하지 않고 정렬 가능하다. 이제 자바를 이용해서 선택 정렬을 구현해보자. 선택 정렬의 분석 선택 정렬의 성능 분석을 위하여 비교 횟수와 이동 횟수를 따로 구하여 보자. 먼저 비교 횟수를 구하기 위하여 두개의 for 루프의 실행 횟수를 계산해보자. 외부루프는..
-
해싱(Hashing) 이란?Computer Science/Data_Structure 2020. 1. 4. 16:08
오늘은 해싱의 개념에 대해서만 정리해보고자 한다 해싱(hashing) 이란? 선형 탐색이나 이진 탐색은 모두 키를 저장된 키 값과 반복적으로 비교함으로써 탐색하고자 하는 항목에 접근한다. 이런 방법들은 최대 가능한 시간 복잡도가 O(logn)에 그친다. 이정도만 되어도 괜찮은 응용도 있지만, 어떤 응용에서는 더 빠른 탐색 알고리즘을 요구한다. 해싱은 키에 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해시 테이블(hash table) : 이렇게 키에 대한 연산에 의해 직접 접근이 가능한 구조 해싱(Hashing) : 해시 테이블을 이용한 탐색 더 효율적인 알고리즘은 없을까? 예를들어 O(1)의 시간안에 탐색할 수 있는건 없을까? 해싱은 O(1)의 시간안에 탐색을..
-
그래프(graph)의 구현 2가지Computer Science/Data_Structure 2020. 1. 4. 06:05
그래프를 구현하는 방법은 책을 보거나, 구글링을 해보아도 전부 인접행렬 or 인접리스트를 이용하여 구현을 한다. 상황에 맞게 시간복잡도를 고려하여 더 효율적인 것을 사용하면 된다. 그래서 각각의 장단점을 공부하려 글을 쓰려 한다. https://kosaf04pyh.tistory.com/131 [자료구조] 그래프(Graph) 이번시간에는 그래프에 대해 공부해 보겠습니다. 그래프란 ? 그래프는 정점(Vertex)간의 관계를 표현하는 자료구조 입니다. 그래프 G = (V,E)로 정의하는데, V(Vertex)는 그래프에 있는 정점들의 집합을 의미하고.. kosaf04pyh.tistory.com https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html ..
-
너비 우선 탐색(BFS) 란?Computer Science/Data_Structure 2020. 1. 4. 05:30
그래프 탐색에는 2가지가 있다고 했는데 그 중에 하나인 BFS 탐색에 대해서 정리하려고 한다. 너비 우선 탐색(breath first search : BFS) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 위와 같은 그래프에서 화살표의 방향대로 탐색을 한다. (시작 정점에서 가까운 노드부터 탐색하는 것을 알 수 있다) 너비 우선 탐색을 위해서는? 가까운 거리에 있는 정점들을 차례로 정한 후 꺼낼 수 있는 자료구조인 큐(queue)가 필요함 무조건 큐에서 정점을 꺼내서 정점을 반물하고 인접 정점들을 큐에 추가한다.(큐가 소진될 때 까지 반복) 너비 우선 탐색 과정 다시한번 정리하자면 다음과 같다. 위의 과정을 큐가 공백 상태가 될 때 까지 계속한다...
-
깊이 우선 탐색(DFS) 란?Computer Science/Data_Structure 2020. 1. 4. 00:36
그래프의 탐색 그래프 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 그래프 탐색은 아주 중요하다 도시를 연결하는 그래프가 있을 때, 특정 도시에서 다른 도시로 갈 수 있는지 없는지는 탐색하여 체크 그래프의 탐색 방법은 깊이 우선 탐색과 너비 우선 탐색의 두 가지가 있다. 이 글에서는 깊이 우선 탐색에 대하여 알아보겠다. 깊이 우선탐색(DFS : depth first search) 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이라는 점을 명심하자) 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사 위와 같은 그림의 그래..
-
그래프(Graph) 란?Computer Science/Data_Structure 2020. 1. 3. 21:49
그래프의 소개 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료 구조다. (대표적인 예 : 지도) 지도를 그래프로 표현하면 지하철의 특정한 역에서 다른 역으로 가는 최단 경로를 쉽게 찾을 수 있다. 운영 체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 그래프로 표현할 수 있는 것들 도로 미로 선수과목 1. 그래프의 정의와 용어 그래프의 정의 그래프는 정점(vertex)와 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V,E)와 같이 표시한다. V(G)는 그래프의 G의 정점들의 집합, E(G)는 그래프 G의 간선들의 집합이다. 정점 : 여러 가지 특성을 가질 수 있는 객체 간선 : 이러한 정..
-
힙(heap) 이란 ?Computer Science/Data_Structure 2020. 1. 3. 00:22
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html [자료구조] 힙(heap)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 그림같은 자료를 가져다 쓴 곳입니다! ( 또한 잘 정리가 되어 있어서 참고 하면서 공부 했습니다. ) "C언어로 쉽게 풀어쓴 자료구조" 를 가지고 공부 중에 있습니다. 책의 내용을 정리해서 쓰고 있습니다. 여기는 그냥 제가 공부한 것을 정리하는 TIL 공간입니다. ( 책과 블로그 글 내용이 비슷하네요 ) 우선순위 큐에 대해서는 다른 글에서 따로 정리하려 한다. 힙(heap)의 개념 완전 이진 트리의 일종으로 우선순위 큐를 위..
-
이진 탐색 트리(binary search tree) 란?Computer Science/Data_Structure 2020. 1. 2. 15:50
이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료 구조이다. 탐색은 내가 생각하기에도 코딩테스트와 같은 곳에서도 자주 출제가 되며 또한 컴퓨터 프로그램에서도 많이 사용되며, 가장 시간이 많이 걸리는 작업 중의 하나이므로 탐색을 효율적으로 수행하는 것은 무척 중요하다. 자주 쓰이는 자료 구조이기 때문에 잘 개념을 익혀놔야겠다. ( "C언어로 쉽게 풀어쓴 자료구조" 라는 책으로 정리 중입니다 ) https://songeunjung92.tistory.com/31 [자료구조/java] 이진 탐색 트리 BST (Binary Search Tree) - 연결 리스트 구현 * 이진 탐색 트리 (Binary Search Tree) "탐색을 위한 자료구조로 이진 트리를 사용하기 위해..