본문 바로가기

자료구조와 알고리즘40

트리 1. 트리 구조 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조입니다. 실제로는 이진트리 (Binary Tree) 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용됩니다. 2. 용어 Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 Sibling.. 2020. 9. 2.
해쉬 테이블 해쉬 구조 Hash Table : 키에 데이터를 저장하는 데이터 구조 key를 통해 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 용어 해쉬 : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소 : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음 슬롯 : 한 개의 데이터를 저장할 수 있는 공간 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음. 장점 - 데이터 저장/읽기 속도가 빠르다 - 해쉬는 키에 대한 데이터가 .. 2020. 9. 2.
링크드 리스트 1. Linked List의 구조 연결된 리스트이다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 반면 링크드 리스트는 물리적으로 떨어진 데이터를 포인터를 사용해 연결해 관리하는 구조이다. 2. 기본 용어 Node : 데이터 저장 단위이다 (데이터의 값, 포인터(다음 데이터의 주소)로 구성된다. Pointer : 각 노드 안에서 다음이나 , 이전 노드와의 연결정보를 가지고 있는 공간 장점 - 미리 데이터공간을 할당하지 않아도 된다. 단점 - 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음 - 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 - 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요 3. 더블 링크드 리스트 기본구조 이중 연결 리스.. 2020. 8. 26.
스택 데이터를 제한적으로 접근할 수 있는 구조 - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 1. 스택 구조 스택은 LIFO (Last In, First Out) 또는 FILO(Frist In, Last Out) 데이터 관리 방식을 따름 LIFO : 마지막에 넣은 데이터를 먼저 추출하는 데이터 관리 정책 FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 스택의 장단점 장점 구조가 단순해서 , 구현이 쉽다 데이터 저장/읽는 속도가 빠르다. 단점 데이터 최대 개수를 미.. 2020. 8. 18.
큐 (Queue) 1. 큐 구조 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조입니다. FIFO(First-in, First-Out) 또는 LILO(Last-in , Last-Out) 방식으로 스택과 꺼내는 순서가 반대입니다. 2. 큐 용어 - Enqueue : 큐에 데이터를 넣는 기능 - Dequeue : 큐에서 데이터를 꺼내는 기능 3. 큐 관련 라이브러리 1) java Queue 인터페이스를 제공해주며 구현체인 LinkedList, priorityQueue, priorityBlockingQueue를 사용합니다. method - void offer(Type data) : 순차적으로 데이터를 저장합니다. - Type poll() : 가장 먼저 보관한 값을 꺼내고 반환합니다. - Type peek() : 가장 먼저.. 2020. 8. 17.
배열 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 1. 배열이 왜 필요할까? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 인덱스는 각 각의 저장공간에 번호를 새겨서 바로 데이터를 찾을 수 있도록 도와주는 번호 배열의 장점 - 데이터에 빠른 접근이 가능합니다. 배열의 단점 - 배열은 공간을 미리 설정을 해야합니다. 따라서 공간을 넘어서는 데이터를 추가하기 위해선 새로운 배열을 만들어야 합니다. - 배열은 데이터의 추가/삭제에 대해서 많은 비용이 발생합니다. 2020. 8. 17.
퀵 정렬 퀵 정렬(Quick Sort) 버블 정렬, 선택 정렬, 삽입 정렬 알고리즘은 모두 시간 복잡도 O(N^2)을 가지기 때문에 데이터의 개수가 많을수록 사용하기 힘든 알고리즘입니다. 더욱 빠른 정렬 알고리즘이 필요한데 그중 하나인 퀵 정렬입니다. 퀵 정렬은 말 그대로 엄청나게 빠른 정렬 기법입니다. 이 퀵 정렬은 분할 정복(Divide and Conquer)에 근거하며, 퀵 정렬은 다른 정렬과는 달리 기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측에, 기준값보다 큰 데이터는 우측으로 분할하고 다시 퀵 정렬을 적용합니다. 이러한 기준값을 피벗(Pivot)이라고도 하는데 보통 첫 번째 원소를 피벗 값으로 설정하고 사용합니다. 위 그림에서의 과정을 글로 나타내면 아래와 같습니다. 5를 기준값으로.. 2020. 8. 13.
3. 삽입정렬 삽입 정렬은 도대체 어떤 정렬 방식일까요? 간단히 말하면 삽입 정렬은 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘이라고 말할 수 있습니다. 삽입 정렬도 버블 정렬과 마찬가지로 구현이 간단하여 많이 사용이 되기도 합니다. 버블 정렬과 선택 정렬 같은 경우 모든 요소를 매번 검사하여 정렬을 했다면 삽입 정렬은 앞의 요소들이 정렬이 되었다는 가정 하에서 해당 요소보다 큰 값들의 맨 앞에 넣어 주도록 구현되어 버블 정렬과 선택 정렬보다는 효율성이 더 좋습니다. 위 그림에서의 과정을 글로 나타내면 아래와 같습니다. 6 과 4를 비교하여 4가 더 작으므로 6 앞으로 4를 삽입한다. 6과 1을 비교하여 1이 더 작으므로 4 앞으로 1을 삽입한다. 6과 7을 비교하여 정렬할 필요가 없으므로 변동 사.. 2020. 8. 11.
자료구조 자료구조는 무엇일까? 우리는 수많은 데이터들을 다룬다. 이러한 데이터를 구조적으로 표현하는 방식입니다. 어떻게 표현한다는 걸까? 데이터들을 효율적으로 메모리에 배치한 뒤 저장하여 관리까지 하기 위함입니다. 데이터마다 적절한 자료구조가 다르며 자료구조의 사용은 메모리의 사용 용량을 절약해주며 실행시간까지 단축시켜줄 수 있습니다. 구조적이라는 것은 뭘까? 데이터 값의 모임, 데이터 간의 관계 그리고 데이터에 적용할 수 있는 함수나 명령체계 등을 이야기합니다. 즉 이러한 데이터들을 현실에서 우리가 나열하듯이 컴퓨터로 표현 가능한 형태로 구조화시킨 것이 자료구조입니다. 자료구조에서는 Search 자료의 탐색, Insert 자료의 추가, delete 자료의 삭제 등이 수행됩니다. 자료구조를 선택할 때는 여러 가지.. 2020. 7. 29.
2.버블정렬 다음 숫자를 오름차순으로 나열하고 싶다면? 10 9 8 7 6 5 4 3 2 1 선택 정렬을 이용해 가장 작은 값을 반복적으로 앞으로 보냈다면 이번에 배울 버블 정렬은 인접한 옆 숫자끼리 비교해 더 작은 값을 앞으로 보내는 알고리즘입니다. 버블 정렬 알고리즘은 구현은 쉽지만 가장비효율적인 알고리즘입니다. 단순히 반복적으로 두 숫자를 비교하여 큰 숫자를 뒤로 보냅니다. 첫 번째 최댓값을 뒤로 보낼 때 (10,9), (10,8), (10,7), (10,6), (10,5), (10,4), (10,3), (10,2), (10,1) 9번의 연산을 해서 최댓값을 뒤로 보냄(n-1) 번 즉 두 번째 for문에 조건식이 9 8 7로 줄어야 하므로 9-i의 식으로 돌림. public class algorithm02 { .. 2020. 3. 9.

티스토리툴바