CS/자료구조

그래프는 무엇일까?      그래프 (graph) --그래프는노드의 집합과 간선(edge, 엣지)의 집합으로 구성된다. 노드(node)는그래프의 기본 요소로, 보통 정점(Vertex)이라고도 부른다.각 노드는 데이터를 저장할 수 있으며, 다른 노드와의 관계를 나타내는 엣지에 의해 연결된다.엣지(Edge)는두 노드를 연결하는 선으로, 노드 간의 관계나 연결을 표현한다.엣지는 방향이 있는 경우와 없는 경우가 존재한다.- 방향이 없는 엣지는 무방향 엣지(Undirected Edge)라고 부르며 보통 양방향을 의미한다.(무방향 엣지로 이루어진 그래프를 무향 그래프 (Undirected Graph)라고 부른다.)- 방향이 있는 엣지는 유방향 엣지(Directed Edge)라고 부르며 해당 방향을 가리키는 의미다...

캐시란 무엇인가?      캐시 (cache) --캐시는데이터 접근 비용을 줄이기 위해 일부 데이터를 계산이 이뤄지는 곳에서 가까운 위치에 저장하는 자료 구조다. 평소에 컴퓨터의 모든 저장소를 동등하게 취급했지만(여기서 동등하게 취급했다는 것은 모든 저장소에 접근하는 비용이 비슷하게 취급했다는 의미다.)사실 모든 데이터 저장소가 동등하지 않다. 실제 서로 다른 저장 매체들은저장 용량, 속도, 비용 사이에 트레이드 오프 관계가 존재한다. 트레이드 오프(trade-off) 관계는한 가지 이점을 얻기 위해 다른 이점을 포기하는 상황을 의미한다.  저장소 종류 CPU 자체의 메모리 (레지스터 or 지역적 캐시)속도가 매우 빠름저장 공간이 작음컴퓨터의 RAMCPU 메모리보다 더 큰 공간을 제공CPU 메모리보다 속..

해시 테이블이란 무엇일까?      키를 사용한 저장 및 탐색 --정수 값을 효율적으로 탐색하기 위한 이상적인 인덱싱 방법을 생각해 보면모든 값에 대해 개별적으로 배열 상자를 유지하고,값을 사용하여 해당 상자를 인덱싱하는 것이다. 인덱싱(Indexing)은데이터를 효율적으로 검색하고 조회하기 위해 데이터의 위치나 상태를 체계적으로 정리하는 과정을 의미한다.예시) 도서관에서 책을 쉽게 찾기 위해 책의 위치를 정리하는 것 간단한 예시를 들면값 9를 삽입하기 위해 인덱스가 9인 상자에 넣는다. 다만 이러한 자료 구조에는 존재할 수 있는 모든 키의 배열을 유지하기 위해 엄청난 비용이 들게 된다.예시로 16자리 신용카드 번호를 모두 저장하려면 10^16개의 상자가 필요하게 된다. (아주 큰 메모리가 필요)여기서 ..

우선순위 큐는 무엇이고힙은 무엇일까?      우선순위 큐(priority queue) --우선순위 큐는주어진 점수에 따라 항목을 정렬하여 탐색하는 자료 구조다. 기초적인 스택과 큐는데이터가 삽입된 순서만 고려했지만, 우선순위 큐는추가 정보, 즉 우선순위를 사용해서 탐색 순서를 결정한다. 그래서 자료 구조를 데이터에 더 적합하게 적용할 수 있으며,유용한 응용 분야 중 하나로, 긴급한 요청을 먼저 처리할 수도 있다.   우선순위 큐의 특징항목 집합을 저장하고, 가장 높은 우선순위를 가진 항목을 쉽게 탐색하게 해 준다.우선순위 큐는 동적이며, 삽입과 탐색을 혼용해도 잘 작동한다.우선순위가 지정된 작업 목록에서 항목을 추가하거나 제거 또한 가능해야 한다.  기본적인 우선순위 큐의 주요 연산 기능항목과 그 항목..

트라이란 무엇이고적응형 자료 구조는 무엇인가?      트라이 (Trie) --트라이는문자열을 저장하고 검색하기 위한 트리 형태의 자료 구조로문자열을 접두사 기준으로 다른 하위 트리로 분할하는 트리 기반 자료 구조다. 각 노드는 하나의 문자와 관련되어 있으며루트에서부터 리프 노드까지의 경로가 하나의 문자열을 나타낸다.  트라이는이진 탐색 트리와 마찬가지로, 루트 노드에서 시작하고루트 노드는 빈 접두사를 나타낸다. 루트 노드의 자식 노드는 각 문자열의 다음 문자를 정의한다.이로 인해 각 노드는 둘 이상의 자식을 가질 수 있다. 최소 하나 이상의 자식 노드가 있는 노드를 '내부 노드',자식이 없는 노드를 '리프 노드'라고 부른다.  트라이 자료 구조의 각 노드 객체 구조 [JAVA]class TrieNode..

이진 탐색 트리란 무엇인가?      이진 탐색 트리 (binary search tree) --이진 탐색 트리는이진 탐색 알고리즘을 기반으로 동적 자료 구조를 생성하는 것으로 정렬된 배열과 달리효율적인 원소 추가 및 제거뿐 아니라 탐색도 추가로 지원한다. 트리(tree)는노드의 분기 사슬로 구성된 계층적인 자료 구조다.트리 노드는하부 리스트를 가리키는 2가지 next 노드를 허용한다는 점에서 연결 리스트와 차이가 있다.  이진 탐색 트리 예시 구조 위 그림처럼노드는 값을 포함하며,트리의 하위 노드를 가리키는 포인터를 최대 2개 가진다. 여기서 자식이 하나 이상 있는 노드를 '내부(internal, 또는 비단말/비말단/비종단) 노드' 라고 부르며자식이 없는 노드를 '단말(terminal, 또는 말단/종단)..

스택은 무엇이고큐는 무엇인가?      스택 (Stack) --스택은후입선출 (LIFO, Last In First Out) 자료 구조로마지막으로 들어간 데이터가 맨 처음으로 나가는 구조다. 이때 데이터를 담는 연산(데이터 추가)을 'push', 담긴 데이터를 꺼내는 연산(데이터 삭제 후 반환)을 'pop'이라고 부른다. 스택의 주요 연산푸시(push)  :  스택의 맨 위에 새로운 데이터 삽입팝(pop)  :  스택의 맨 위에 있는 데이터 삭제 후 반환피크(peek) 또는 탑(top)  :  스택의 맨 위에 있는 데이터를 삭제하지 않고 반환isEmpty  :  스택이 비어 있는지 확인  배열이나 연결 리스트 중 어느 쪽이든 스택을 구현할 수 있다.  배열로 스택 표현하기  리스트로 스택 표현하기 리스트에..

동적 자료 구조란 무엇인가?      배열의 한계 --배열은 메모리 접근 속도가 빠르고, 구조가 단순하여기본적인 데이터 저장 용도로 유용하지만다방면으로 사용하기에는 한계가 존재한다. 여러 한계들이 존재하지만 그중에 중요한 것은배열을 처음 생성할 때 정해진 해당 배열의 크기와 메모리 레이아웃은 고정이 되어 변경이 불가능하다. 메모리 레이아웃이란메모리의 구조와 분포를 나타내는 것으로간단하게 메모리의 공간(영역)으로 생각하면 된다.  즉, 이미 생성한 배열의 크기보다 큰 데이터를 담으려면(저장) 해당 크기에 알맞은 배열을 새로 생성해서 할당해야 한다.배열의 크기가 '5'지만 총 6개의 데이터를 담아야 하는 경우 이러한 단점을 보안하기 위해 현대적인 프로그래밍 언어에서는원소를 추가하면 크기가 커지고 원소를 제거..