이진 탐색 트리 (Binary Search Tree , BST) 이진 탐색 트리는 다음과 같은 규칙을 가진 이진 트리를 의미합니다. 모든 노드의 크기(or 값)가 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드의 형태를 유지 이로 인해, 각각의 서브트리는 이진 탐색 트리를 유지 중복된 값을 허용하지 않음 이진 탐색 트리 특징 데이터가 정렬되어 저장되어 이진 트리에 비해 탐색이 빠릅니다. 탐색의 시간복잡도는 균형 상태에서 O(logN) , 불균형 상태에서는 O(N)입니다. 빠른 탐색 속도를 위해, 이진 탐색 트리의 균형을 항상 유지하는 것이 중요합니다. 이진 탐색 트리의 구조 탐색 (Search) 찾고자 하는 데이터를 root 노드부터 대소 비교 데이터가 작으면 왼쪽 이동 데이터가 크면 오른쪽 이동 찾..

트리(Tree) 노드와 간선(Edge)으로 이루어진 자료구조로 순환(Cycle)이 없는 그래프의 일종입니다. 보통 계층 구조를 나타낼 때 사용합니다. 트리의 구조 노드(Node) : 트리 구조의 단위 루트 노드(Root Node) : 부모가 없는 최상위 노드 리프 노드(Leaf Node) : 자식이 없는 최하위 노드 (= 단말 노드) 부모 노드(Parent Node) 자식 노드(Child Node) 형제 노드(Sibling Node) : 같은 부모를 가지는 노드들 내부 노드(Internal Node) : Leaf를 제외한 모든 노드 간선(Edge) : 노드 간의 연결선 (= link, branch) 깊이(Depth) : Root 에서 어떤 노드까지의 간선 수 레벨(Level) : 트리의 특정 깊이를 가지..

해시 테이블 (Hash Table) 해시 테이블이란 키(Key)와 값(Value)을 1:1로 대응시켜 저장하는 데이터 구조입니다. 키를 통해서 원하는 데이터에 빠르게 접근이 가능합니다. 해시 테이블 구조 키(Key) : 해시 테이블에 접근하기 위한 값 해시 함수(Hash Function) : 키를 해시 값으로 매핑하는 연산 해시 값(Hash Value) : 해시 테이블의 인덱스 해시 테이블(Hash Table) : 키-값을 저장하는 데이터 구조 해시 테이블은 입력받은 키 값을 해시 함수를 이용해 변환합니다. 여기서 나오는 값을 해시 테이블의 인덱스 삼아서 데이터를 저장하게 됩니다. 해시 충돌 해시 테이블을 올바르게 이용하기 위해선 적절한 해시 함수를 통해 테이블에 값들이 골고루 분포되도록 해야하며, 그러..

데크 (Deque, Doubly-ended Queue) 데크는 양쪽 끝에서 삽입과 삭제가 모두 가능한, 큐와 스택을 합친 형태의 자료구조입니다. 데크의 구조 데크의 구조는 위와 같으며, 양쪽 끝에서 삽입 및 삭제가 이루어집니다. 양쪽 끝은 Head(Front)와 Tail(Rear)라고 부르며, 보통 이중 연결 리스트로 구현을 하게 됩니다. 데크의 종류 데크는 기본적인 데크 외에도 입력 제한 데크(Scroll)과 출력 제한 데크(Shelf)가 있습니다. 입력 제한 데크 : 한 쪽의 입력을 제한한 데크 출력 제한 데크 : 한 쪽의 출력을 제한한 데크 프로그래밍 언어에서의 구현 Java 자바에서는 Deque를 인터페이스로 제공하고 있습니다. 데크는 ArrayDeque, LinkedList 등으로 구현되어 있습..

큐 (Queue) 큐란 선입선출(First In, First Out) 의 특징을 가진 자료구조를 의미합니다. 선입선출이란 먼저 들어온 데이터가 먼저 나가는 구조를 뜻합니다. 보통, 입력한 순서대로 데이터를 처리할 필요가 있을 경우 사용합니다. 큐의 구조 큐에선 데이터가 한쪽으로 들어와서 한쪽으로 나가게 됩니다. 데이터가 들어오는 위치를 Rear or Back , 데이터가 나가는 위치를 Front라고 합니다. 큐에 데이터를 넣는 연산을 Enqueue, 큐에서 데이터를 꺼내는 연산을 Dequeue라고 합니다. 큐의 종류 큐에는 특수한 형태의 큐들이 존재하는데, 원형 큐, 우선순위 큐, 데크 등이 이에 해당합니다. 원형 큐 선형 큐의 경우, Dequeue 연산을 하게되면 빈 부분이 생기게 되는데, 공백을 없애..

스택 (Stack) 스택이란 후입선출(Last In, First Out)의 형태를 가지고 있는 자료구조입니다. 후입선출이란 나중에 들어온 것이 먼저 나간다는 의미입니다. 보통 함수 콜 스택이나 인터럽트 처리 등 데이터를 입력된 순서의 역순으로 처리할 때 사용합니다. 스택의 연산 스택의 연산은 Push와 Pop, Peek으로 이루어져 있습니다. Push : 데이터를 스택의 가장 마지막 위치에 추가합니다. Pop : 스택의 가장 마지막 위치에서 데이터를 꺼냅니다. Peek : 가장 마지막 데이터를 꺼내지 않고 읽어오기만 합니다. 스택의 시간복잡도 삽입 : O(1) 삭제 : O(1) 탐색 : O(N) 프로그래밍 언어로 구현 직접 배열이나 리스트로 구현도 가능하지만, 언어들에서 제공해주는 라이브러리가 존재합니다..

연결 리스트 (Linked List) 연결 리스트는 데이터를 링크로 연결해서 관리하는 자료구조입니다. 연결 리스트는 노드(Node)라는 저장 단위로 구성되며, 노드는 값과 포인터를 가지고 있습니다. 값은 저장하려는 값, 포인터는 다음/이전 노드의 연결 정보를 뜻합니다. 자료의 순서는 정해져있지만, 배열과는 다르게 메모리에 연속적으로 저장되지는 않습니다. 장점 배열과는 다르게 데이터 공간을 미리 할당할 필요가 없어서 데이터의 추가와 삭제가 용이합니다. 배열 같은 경우, 사용하지 않는 만큼 공간 낭비가 생기는데, 그러한 공간낭비가 줄어듭니다. 단점 데이터 뿐만 아니라 다음 데이터의 위치정보까지 같이 저장하다보니 링크를 위한 별도 데이터 공간이 필요합니다. 더불어, 다음 데이터와의 연결정보를 통해 접근하다보니..

배열 (Array) 배열이란 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조를 의미합니다. 원소들에게 붙은 번호를 인덱스(Index)라고 하며, 데이터들은 메모리 상에 연속적으로 저장됩니다. 장점 배열은 인덱스를 이용하여 데이터에 빠르게 접근할 수 있다는 장점이 있습니다. 배열의 데이터들이 물리적으로 메모리 상에 연속적으로 저장되어 있기 때문에, 첫 번째의 주소만 안다면 배열의 모든 값에 바로 접근할 수 있습니다. 이러한 특성으로 인해 배열의 원소를 검색하는 시간은 O(1) 으로 임의접근이 가능하여 굉장히 빠릅니다. 임의 접근(Random Access) 집합 내의 요소의 수에 관계없이 주소 할당이 가능한 요소들로부터 임의의 시점에 임의의 데이터에 접근하는 기능 다만, 인덱스를 사용하는 것이 아..

자료구조 (Data Structure) 자료구조란 자료(Data)를 효율적으로 관리하기 위한 자료 보관 방법 및 자료에 관한 연산을 의미합니다. 상황에 맞춰 적절한 자료구조를 선택하는 것은 프로그램의 성능을 향상시킬 수 있으므로, 프로그래밍에 있어 중요한 요소 중 하나입니다. 자료구조의 분류 자료구조는 다음과 같이 나눌 수 있습니다. 선형 자료구조 데이터의 요소가 순차적으로 연결(선형)되어있는 구조를 선형 자료구조라고 합니다. 데이터들간의 앞 뒤 관계가 1:1로 되어있는 것이 특징입니다. 선형 자료구조에는 다음과 같은 자료구조들이 있습니다. 배열 연결리스트 스택 ,큐, 데크 해시 테이블 비선형 자료구조 선형 자료구조와는 다르게 비순차적으로 연결되어있는 것을 비선형 자료구조라고 합니다. 데이터들간의 관계가..

알고리즘 복잡도 알고리즘 복잡도란 알고리즘의 성능을 나타내는 척도로 시간 복잡도와 공간 복잡도로 나눌 수 있습니다. 시간 복잡도 시간 복잡도란 프로그램의 입력값과 연산 수행 시간과의 상관관계를 나타내는 척도입니다. 쉽게 설명하면, 문제를 해결하기 위한 알고리즘의 필요 연산 횟수로 생각해 볼 수 있습니다. 시간복잡도는 보통 빅오 표기법을 이용해 나타냅니다. 빅오(Big-O) 표기법 빅오 표기법은 알고리즘이 수행될 때 걸릴 수 있는 최악의 실행 시간을 나타냅니다. 빅오 표기법을 사용하는 이유로는 최악의 실행 시간을 나타내야 알고리즘이 최소한으로 보장하는 성능을 알 수 있기 때문입니다. 빅오 표기법은 다음과 같이 나타냅니다. N은 가장 큰 수만 빅오 표기법에 표기됩니다. 예시 O(N) : 5N + 3, 2N ..

지수 어떤 수 a를 x번 거듭 곱했을 때 a^x 으로 표현하게 되는데, 여기서 a는 밑, x는 지수라고 표현합니다. 지수 법칙 지수는 다음과 같은 법칙이 성립합니다. 로그 로그는 다음과 같습니다. 쉽게 말해, a가 N이 되기 위해 제곱해야하는 수를 의미합니다. 로그의 기본 성질 로그는 다음과 같은 성질을 지니고 있습니다. 참고자료 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=junhyuk7272&logNo=221261015532

점화식 (Recurrence) 어떤 수열의 각각의 항들이 어떤 관계를 가지고 있는지를 나타낸 식을 의미합니다. 보통 점화식은 n번째의 항을 이전의 항들을 이용하여 정의하게 됩니다. 피보나치 수열이 대표적인 예입니다. 재귀함수 (Recursion) 어떤 함수가 자기 자신을 다시 호출하여 작업을 수행하는 방식을 뜻합니다. 재귀함수는 자기 자신을 호출하기 때문에 영원히 반복될 수 있습니다. 그렇기 때문에 재귀함수를 설계할 때는 입력값이 종료 조건으로 수렴하는지 검증해야 합니다. 재귀 함수 예시 Java // 최대 공약수 구하기 static int gcd(int a, int b) { if (a % b == 0) { return b; } return gcd(b, a % b); } // 피보나치 수열 static ..