본문 바로가기

전체보기101

CS 자료구조 Trie(트라이) 트라이는 주로 문자열 검색에 사용되는 특수한 형태의 자료구조다. 많은 문자열이 공통된 접두사를 가질 때 효율적인 탐색을 제공하도록 설계되어 있다. 트라이는 사전(Dictionary)처럼 동작하며, 문자열의 삽입, 검색, 삭제 등의 연산을 빠르게 수행할 수 있다. ㅇ 트라이의 특징노드 구조트라이의 각 노드는 하나의 문자(Character)를 나타내며, 자식 노드들로 연결된다.각 경로는 특정 문자열의 접두사를 나타낸다.루트 노드트라이의 시작점으로, 빈 문자열을 표현하거나 의미 없는 노드로 시작한다. 모든 문자열의 경로가 이 루트에서부터 시작 된다.삽입 연산문자열을 삽입할 때는 문자열의 각 문자를 노드로 변환하여 차례대로 삽입한다. 공통된 접두사를 가진 문자열은 동일한 경로를 공유하며, 공통 접두사 이후부터 .. 2024. 10. 9.
[자료구조] Hash(해시), Hash Table, HashMap ㅇ Hash개념해시는 임의 길이의 입력 데이터를 고정 길이의 해시 값 또는 해시 코드로 매핑하는 과정 혹은 그 결과물을 의미한다해시 함수를 사용하여 매핑하고, 이 함수는 입력 값(Key)을 특정 규칙에 따라 연산해 일정한 길이의 정수로 변환한다 특징고속성키를 즉시 특정 값으로 매핑할 수 있으므로 연산 속도가 매우 빠르다결정론적 성질같은 입력은 항상 같은 해시 값을 반환한다해시충돌서로 다른 입력에 대해 서로 다른 해시 값을 주는 것이 이상적이나, 해시충돌이 발생할 수 있다균등 분포성우수한 해시 함수는 가능한 한 해시 값을 균등하게 분포시켜 충돌을 최소화한다 ㅇ Hash Table개념해시 테이블은 (키, 값) 쌍을 저장하는 자료구조로 키를 해시 함수에 통가시켜 해시 값을 얻고 이를 배열의 인덱스로 사용하여 .. 2024. 10. 8.
CS 자료구조 Priority Queue(우선순위 큐) 우선순위 큐는 일반적인 큐와 다르게 데이터를 우선순위에 따라 처리하는 자료구조다. 큐에 들어오는 데이터가 삽입된 순서가 아닌 각 데이터에 지정된 우선순위에 따라 먼저 처리된다. ㅇ 우선순위 큐의 특징우선순위에 따라 처리일반적인 큐에서는 선입선출(FIFO) 방식으로 데이터를 처리하지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 처리된다. 우선순위가 높은 데이터가 먼저 빠져나오고, 낮은 데이터는 나중에 처리된다.우선순위의 종류최대 우선순위 큐(Max Priority Queue)가장 큰 우선순위를 가진 요소가 먼저 처리된다.최소 우선순위 큐(Min Priority Queue)가장 작은 우선순위를 가진 요소가 먼저 처리된다.구현 방법우선순위 큐는 일반적으로 힙(Heap) 자료 구조를 사용하여 구현된다. .. 2024. 10. 8.
CS 자료구조 Heap(힙) 힙은 완전 이진 트리 형태를 따르는 자료구조다. 주로 우선순위 큐를 구현하는데 사용된다.  ㅇ 힙의 특성완전 이진 트리(Complete Binary Tree) 힙은 모든 레벨이 꽉 차 있어야 하며(마지막 레벨은 제외), 마지막 레벨은 왼쪽에서부터 차례대로 채워져야 한다.항상 가장 왼쪽부터 빈 자리를 채워나가는 트리구조다. 힙 속성(Heap Property)최대 힙(Max Heap)부모 노드가 자식 노드보다 항상 크거나 같아야한다. 루트에 가장 큰 값이 위치한다.최대값을 빠르게 추출할 수 있다.최소 힙(Min Heap)부모 노드가 자식 노드보다 항상 작거나 같아야한다. 루트에 가장 작은 값이 위치한다.최소값을 빠르게 추출할 수 있다. ㅇ 힙의 주요 연산삽입(Insertion)새로운 값을 삽입할 때는 트리의.. 2024. 10. 8.
CS 자료구조 Binary Search Tree(이진 탐색 트리) 이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식을 가지는 이진 트리의 특수한 형태로, 데이터의 정렬과 효율적인 검색을 목적으로 설계된 자료 구조다. 노드에 저장된 데이터를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 특정 조건을 만족하도록 설계되어 있다. ㅇ  이진 탐색 트리의 특징왼쪽 서브트리의 모든 노드는 부모 노드보다 작은 값을 가진다.오른쪽 서브트리의 모든 노드는 부모 노드보다 큰 값을 가진다. ㅇ 이진 탐색 트리의 주요 연산탐색(Search)이진 탐색 트리에서 특정 값을 찾을 때 트리의 루트에서부터 시작한다.찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 트리로 이동한다.크면 오른쪽 트리로 이동한다.원하는 값을 찾거나 탐색할 노드가 없으면 종료한다.시간복잡도: 평균적으로 O(log n).. 2024. 10. 8.
CS 자료구조 Tree(트리) 트리는 계층적인 데이터를 표현하는 비선형 데이터 구조다. 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 트리는 트리 내에 다른 하위 트리가 있고, 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조다. 컴퓨터의 디렉토리 구조가 트리의 대표적인 예가 될 수 있다. ㅇ 트리의 기본 용어 노드(Node)트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음A, B, C, D, E, F, G, H, I, J 간선(Edge)노드와 노드 간의 연결 선 루트 노드(Root Node)트리 구조에서 부모가 없는 최상위 노드A 부모 노드(Parent Node)자식 노드를 가진 노드H, I의 부모 노드 D 자식 노드(Child Node)부모 노드의 하위 노드D의 자식 노드 H, I.. 2024. 10. 8.
CS 알고리즘 시간복잡도 시간 복잡도(Time Complexity)는 알고리즘이 처리하는 작업의 양이 입력 데이터의 크기에 따라 어떻게 변화하는지를 분석한 것이다. 입력 크기가 커짐에 따라 알고리즘이 얼마나 많은 시간을 소요하는지를 나타내는 척도라고할 수 있다. 주로 사용되는 빅오 표기법(Big-O Notation)에 대해 간단히 알아본다. ㅇ 빅오 표기법(Big-O Notation)O(1) - 상수 시간(Constant Time) (오-원)입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우예 : 배열에서 특정 인덱스의 요소에 접근할 때 O(log n) - 로그 시간(Logarithmic Time) (오-로그-엔)입력 크기가 증가할 때, 시간이 로그 단위로 증가하는 경우예 : 이진 탐색(Binary Search)  O(n) -.. 2024. 10. 7.
DB Key 데이터베이스에서 key는 테이블에서 데이터를 식별하거나 관계를 정의하는 데 사용되는 필드다. 데이터를 구분하고 무결성을 유지하는데 중요한 역할을 하며 다양한 종류의 키가 존재한다. 각 키는 고유한 목적을 가지고 있으며 데이터의 효울적인 저장과 검색을 돕는다. ㅇ Key의 종류Primary Key(기본 키)테이블에서 각 행을 고유하게 식별할 수 있는 하나의 열 또는 열들의 집합이다. 중복을 허용하지 않고 NULL 값을 가질 수 없다. 테이블 당 하나의 기본 키만 설정할 수 있고 이는 각 행(row)를 유일하게 식별한다. Unique Key(고유 키)기본 키 처럼 테이블 내에서 고유한 값을 유지하지만, 하나의 테이블에서 여러 개의 고유 키를 설정할 수 있다.NULL 값을 가질 수 있다.(같은 컬럼에서는 단 .. 2024. 10. 4.
DB SQL Injection SQL 인젝션은 웹 애플리케이션의 보안 취약점을 이용해 악의적인 사용자가 SQL 쿼리를 조작하고, 이를 통해 데이터베이스에 부정한 액세스를 시도하는 공격 기법이다. 웹 애플리케이션에서 사용자 입력을 적절하게 검증하지 않거나 필터링하지 않을 때 발생할 수 있다. ㅇ SQL 인젝션의 결과 및 피해데이터 유출공격자는 데이터베이스에 저장된 민감한 정보를 쉽게 조회할 수 있다.데이터 조작공격자는 데이터를 삽입, 수정 또는 삭제할 수 있다.데이터베이스 구조 손상테이블을 삭제하거나 구조를 변경하여 시스템에 심각한 손상을 줄 수 있다.시스템 장악심각한 경우 운영체제 명령을 실행하거나 서버에 대한 접근 권한을 획득할 수 있다. ㅇ SQL 인젝션 방지 방법Prepared Statements 및 파라미터화 된 쿼리사용자의 .. 2024. 10. 4.

티스토리툴바