Knowledge/자료구조

이진탐색(Binary Search)이진탐색이란 `정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘`이다. 탐색 범위를 절반씩 줄이며 찾는 값이 포함된 범위를 좁혀간다. 선형탐색보다 빠른 속도를 보장하지만 배열이 정렬되어 있어야지만 한다. 1. 이진탐색 과정이진 탐색은 중간값이 타겟값보다 크면 왼쪽, 작으면 오른쪽을 탐색한다. 1. 배열의 **중간값(mid)**을 기준으로 타겟값과 비교한다.2. 중간값이 타겟값보다 크면, 탐색 범위를 왼쪽 절반으로 줄인다.3. 중간값이 타겟값보다 작으면, 탐색 범위를 오른쪽 절반으로 줄인다.4. 이 과정을 반복하며 탐색 범위를 좁혀 나간다.  이진 탐색이 선형 탐색의 차이점이진 탐색에 대한 코딩테스트 문제의 예제를 보면 선형 탐색이 더 나아보이는 예제들이 있다. 그래서 ..

트리트리는 노드와 에지로 연결된 그래프의 특수한 형태로 다음과 같은 특징을 갖는다. 순환 구조(Cycle)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트노드를 제외한 나머지 노드는 단 1개의 부모노드를 가진다.트리의 서브 트리 역시 트리의 모든 특징을 따른다.비선형 자료구조로 계층적 관계를 표현한다. Ex) 디렉터리 구조, 조직도노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다.즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다. 트리의 구성요소기본적인 트리의 구성요소를 정리해 보자.정점(Vertex): A, B, C와 같은 값으로 나타내며, 트리 구조에서 노드(node)로 표현된다.간선(Edge): 정점 간에 연결된 선이다.자식노드(Child), 부모 노드(Parent)형제노드..

그래프그래프는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조이다. 정점은 데이터를 나타내고, 간선은 데이터 간의 관계를 의미한다. 정점(Vertex): 데이터 자체를 의미간선(Edge): 정점 간의 관계를 나타내며, 방향성이 있을 수 있다.  대표적인 그래프의 종류들이다. 무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프방향 그래프(Directed Graph): 간선에 방향이 있는 그래프가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프 그래프의 구현은 인접행렬과 인접그래프가 있으며, 각각 알아보자. 인접 행렬인접 행렬은 2차원 배열을 사용하여 그래프의 정점들 간의 연결 관계를 표현한 것이다. 행렬의 `(i, j)` 위치에 간선의 유무를 나타낸다...

스택 스택(stack)은 먼저 넣은 데이터가 나중에 나오는 자료구조이다. 데이터를 넣는 작업은 푸시(push) , 꺼내는 작업은 팝(pop) 이라고 한다. 스택에서 데이터를 관리할 때, 가장 최근에 추가된 데이터를 먼저 꺼내는 구조를 따른다. 데이터를 삽입하거나 삭제할 수 있는 위치는 한쪽 끝인 top 이다. 스택의 맨 아래쪽은 bottom 이라고 하며, 여기에 직접 접근할 수는 없다. 예를 들어, 접시를 쌓는 과정과 유사하다. 접시를 추가할 때는 위에서 쌓고, 꺼낼 때도 맨 위에서부터 꺼낸다. 이처럼 스택은 제한된 입출력 방식으로 후입선출(LIFO: Last In, First Out)의 성질을 갖는다.스택의 장단점장점구조가 단순해서 구현이 쉽다.데이터 저장/읽기 속도가 빠르다. 단점(배열 기반)데이터 ..

큐큐는 데이터를 일시적으로 쌓아 두는 기본 자료구조이다. 아래 그림과 같이 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO : First In First Out) 구조로 되어있다. 큐에 데이터를 넣는 과정을 인큐(en-queue)라 하고, 데이터를 꺼내는 작업을 디큐(de-queue)라 한다.  또 데이터가 나오는 쪽을 프런트(front, 맨 앞)이라고 하고, 데이터를 넣는 쪽을 리어(rear, 맨 뒤)라고 한다. 원형 큐/순환 큐(Circular Queue)자바에선 기본적으로 큐에 대한 인터페이스를 제공한다. 큐 인터페이스를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다.  보통 우선순위큐를 제외하면 다음과 같이 사용했을 것이다. Qu..

배열(Array)많은 수의 데이터를 다룰 때 사용되는 자료구조이며, 같은 타입의 데이터를 나열한 선형 자료구조이다. 데이터를 연속된 메모리 공간에 순차적으로 저장한다.  선언 시 배열의 크기를 정하기 때문에 배열의 크기는 고정되어 있으며 변경할 수 없다.각 데이터와 인덱스는 1:1 대응하도록 구성되어 있다.데이터`a``b``c``d``e`인덱스0 1234 배열의 장점인덱스를 이용하여 데이터에 빠르게 접근 가능하기 때문에 검색 성능이 좋다.연속적인 공간 할당이 되므로 관리하기가 편하다.데이터 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리 속도 면에서 좋다.  arr 배열 `a``b``c`arr[0] = aarr[1] = barr[2] = c위 예시와 같이 인덱스를 이용하여 데이터에 바로 접근이 가..