리얼 개발

0. 이진 탐색 트리이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. 1. BST 기본 연산별 시간복잡도연산 평균 시간복잡도 최악 시간복잡도 (Skewed Tree)탐색 (Search)O(log N)O(N)삽입 (Insert)O(log N)O(N)삭제 (Delete)O(log N)O(N) 2. 시간 복잡도 분석1) 평균적인 경우 (Balanced BST) → O(log N)트리가 균형 잡힌 경우 (Balanced Tree), 즉 거의 완전 이진 트리라면:트리의 높이(h)는 O(log N)탐색, 삽입, 삭제 연산 모두 최대 log N 번만 비교하..

📌 해시 테이블(Hash Table) 개념해시 테이블(Hash Table) 은 키(Key)와 값(Value)을 매핑하여 저장하는 자료구조.즉, 특정 데이터를 빠르게 찾고, 삽입하고, 삭제하는 데 최적화된 구조.✅ 1. 해시 테이블의 개념1) 키(Key)와 값(Value)Key(키): 데이터를 찾기 위한 고유한 식별자 (예: 이름, ID, 해시값)Value(값): 키에 대응하는 저장된 데이터 📌 예시: 학생 성적 저장cpp복사편집hash_table["Alice"] = 95;hash_table["Bob"] = 88;hash_table["Charlie"] = 72; Key ValueAlice95Bob88Charlie722) 해시 함수(Hash Function)해시 함수는 Key를 특정한 인덱스(Index)..

리스트란?data의 명단으로서 배열 또는 linked list에 저장하는 것이다. 배열은 저번 포스팅에서 다뤘으니 이번엔 Linked List에 대해 알아보겠다. Linked List의 종류는 다음 두가지로 나눌 수 있다.Singly Linked List (SLL)Doubly Linked List (DLL)이 둘은 다음 노드를 포인터로 연결해 데이터를 관리한다. C++ 은 STL에 list가 구현되어 있어 직접 구현하지 않고 간편하게 사용할 수 있다.#include using namespace std;int main(){ list List1; //비어있는 int형 List list List2; //비어있는 double형 List} Linked List의 구성요소는 다음과 같다.노드 : Linked Lis..

배열(Array)배열이란 같은 타입의 변수들을 묶어놓은 자료구조이다.//자료형 배열이름 [배열요소의 개수]//자료형 포인터 = new 자료형int b[50], d[5][10], *p, **q;C++ 코드로는 배열을 다음과 같이 나타낼 수 있다. 배열의 크기는 배열이 가질 수 있는 최대 변수 개수를 나타낸다.인덱스(Index)는 배열 내 변수들의 위치를 의미한다. 배열은 배열이름[Index]로 배열 내 데이터에 접근할 수 있으며 이때 Index의 범위는 0 ~ 배열의 크기 - 1 이다. 또한 배열의 자료형은 단순 묶여있는 데이터의 타입을 나타낼 뿐이다. 다음 코드를 통해 데이터의 타입에 따른 메모리 할당 크기를 확인할 수 있다.#include void main(){ char C_Array[100]; int..

알고리즘이란 컴퓨터로 문제를 해결하는 유한하고 단계적인 해법이다. 알고리즘의 조건으로는 다음 3개가 있다.유한성 (finite)명확한 답 (correct answer)input ≥ 0, output ≥ 1이러한 알고리즘들은 문제를 해결한 것에 그치지 않고 성능 분석이 필요하다. 알고리즘의 성능컴퓨터에서 성능은 복잡도로 표현할 수 있고, 복잡도는 시간과 공간으로 나눌 수 있다. 시간 복잡도는 시간 효율성을 의미하고, 공간 복잡도는 알고리즘의 메모리 효율성을 의미한다. 이러한 효율성은 데이터 개수(n)가 주어졌을 때 덧셈, 뺄셈, 곱셈같은 연산 횟수로 정해지며 성능함수로 나타낼 수 있다. ex)성능 함수의 특징으로는 상수는 무시하며 차수는 중시한다.위의 예시는 빅오(big-O) 표기법이며 추가로 빅오메가(b..

어떤 자료든 깔끔하게 정리되어 있으면 보기도 좋고 찾을 때도 편하다. 물건을 찾을 때 우리가 찾으면 안나오지만 어머니가 찾으면 나오지 않나! 어머니는 물건의 위치, 종류를 머릿속으로 항상 정리해놓으시는 것이다. 이렇게 물건과 같은 자료를 자신의 상황에 맞게 정리할 수 있도록 하는 것을 자료구조라고 하며, 컴퓨터 관련 분야에서 기본적이고도 필수적인 개념이다. 프로그래머는 문제를 더 효율적이고 효과적으로 해결하기 위해 자료구조에 대한 개념을 이해하고 활용하는 능력이 필요하다. 자료구조의 분류는 다음과 같이 정리할 수 있다.단순 구조자료값을 사용하기 위한 기본 형태로서 프로그래밍 언어에서 제공하는 정수, 실수, 문자, 문자열 등의 데이터 타입에 해당한다.선형 구조자료 사이의 관계가 1:1 관계인 순차 리스트,..