본문 바로가기

전체 글81

시간 복잡도 시간복잡도란 n개의 입력 데이터에 대하여 알고리즘이 문제를 해결하는 데에 얼만큼의 시간이 걸리는지를 나타내는 것을 말한다. 일반적으로 점근적 표기법(asymptotic notation)을 사용하여 복잡도를 계산한다. 점근적 표기법 점근적 표기법이란 중요하지 않은 상수와 계수들을 제거하여 알고리즘의 실행시간에서 중요한 성장률에 집중하는 방법을 의미. 즉 가장 큰 영향을 주는 항만 계산하는 것이다. 오메가 표기법 (Big-Ω Notation) [ 최선의 경우 ] 세타 표기법 (Big-θ Notation) [ 평균의 경우 ] 빅오 표기법 (Big-O Notation) [ 최악의 경우 ] 점근적 표기법은 위와 같이 세 가지 방법이 존재한다. 그러나 시간 복잡도는 최악의 경우에서 해당 알고리즘이 어떤 성능을 낼 .. 2023. 3. 31.
자료구조 - Tree, Binary Tree Tree 트리는 자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로, 부모 - 자식 관계로 표현된다. 스택, 큐와는 달리 2차원의 자료 구조로, 정점(node)와 간선(edge)를 이용해 데이터의 배치 형태를 추상화시킨다. 트리의 기본 특징 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다. 트리내에 또 다른 트리가 있는 재귀적 자료구조이다. 단순 순환(Loop)을 갖지 않고, 연결된 무방향 그래프 구조이다. 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다. 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다, 트리의 구성 요소 정점(node): 데이터를 직접적으로 담고 있는 요소 간선(edge): 노드를 잇는 연결선 뿌리.. 2023. 3. 31.
자료구조 - 선형 자료구조 자료구조(Data Structure)란 자료에 효율적으로 접근하고 수정할 수 있도록 데이터를 구성하고 저장하는 방법이다. 자료구조는 저장되는 데이터의 형태에 따라 선형 자료구조와 비선형 자료구조로 구분되며, 선형 자료구조는 데이터가 일렬로 나열되어 있고 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다. 선형 자료구조의 종류에는 array, linked list, stack, queue 등이 있으며 비선형 자료구조로는 tree, graph 등이 있다. 이번 포스팅에서는 선형구조를 가지고 있는 자료구조를 개념 위주로 살펴보고, 비슷한 것들끼리 묶어 비교해보려고 한다. 배열 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 미리 크기를 정해놓고 생성하며, 해당 크기만큼의 연속된 메모.. 2023. 3. 31.
자바 컬렉션 프레임워크 - List, Set, Map java에서 Collection이란 데이터의 집합, 그룹을 의미한다. JCF(Java Collection Framework)는 다수의 데이터를 쉽고 효과적으로 처리할수 있는 표준화 된 방법을 제공하는 클래스의 집합이다. 기존에는 배열을 이용하여 데이터를 처리하였지만, 크기가 고정되어 있고 삽입/삭제 연산이 오래걸리는 불편한 점을 개선하기 위해 JCF가 등장했다. Collection의 주요 인터페이스로는 List, Set, Map이 있다. List 입력 순서를 유지하며, 데이터의 중복을 허용한다. 인덱스가 존재하여 이를 통해 저장된 데이터에 접근이 가능하다. ArrayList : 단방향 포인터 구조. 데이터의 순차적 접근(조회)가 빠르다. LinkedList : 양방향 포인터 구조. 데이터의 삽입, 삭제가.. 2023. 3. 30.
관계형 데이터베이스 설계 - 1:1, 1:N, 1:M 관계형 데이터베이스 먼저 관계형 모델은 여러 데이터 모델(데이터를 표현하는 개념의 집합) 중 하나로, 다음과 같은 특징을 만족하도록 고안되었다. 데이터베이스를 단순한 자료구조에 저장 high-level language로 데이터에 접근 물리적 저장소는 구현에 맡겨짐 관계형 모델에서는 데이터를 저장할 때 2차원 테이블 형태의 릴레이션(Relation)이라는 구조가 사용되는데, 이 릴레이션끼의 관계를 정의한 것이 관계형 모델이라고 할 수 있다. 관계를 가진다는 것은 두 릴레이션이 서로 관련이 있을 때를 말하는 것으로, 릴레이션끼리는 1:1, 1:n, n:m 관계를 맺을 수 있다. 1:1 관계 1:1 관계란 상대 엔티티와 반드시 하나의 관계를 가지는 것을 말한다. 예를 들어 우리나라의 결혼제도 상으로, 한 남자.. 2023. 3. 27.
트랜잭션의 개념과 고립 수준 트랜잭션의 개념 트랜잭션은 데이터베이스 시스템에서 하나의 논리적 기능을 정상적으로 수행하기 위한 작업의 기본 단위이다. 하나의 작업을 수행하기 위해 필요한 데이터베이스 연산 기능들을 모아놓은 것이며 분리되지 않도록 하여 작업의 완전성을 보장한다. 트랜잭션을 통해서 데이터베이스의 회복과 병행 제어가 가능하다. 즉, 데이터베이스에서 오류가 발생하는 경우의 빠른 회복이나, 여러 사용자가 동시에 데이터베이스를 사용할 수 있도록 제어해주는 중요한 역할을 한다. 트랜잭션의 특징 트랜잭션이 성공적으로 처리되기 위해서는 ACID라는 네 가지 성질을 만족해야 한다. 원자성 (Atomicity) 트랜잭션을 구성하는 연산 전체가 모두 정상적으로 실행되거나, 모두 취소되어야 하는 성질 하나의 트랜잭션에서 일부 연산만 실행될 .. 2023. 3. 26.

티스토리툴바