개인기록부 개인기록부

DBMS 개요 데이터 베이스를 ‘데이터의 집합’이라고 정의한다면 DBMS(DataBase Management System)는 이 데이터 베이스를 관리, 운영하는 역할을 한다. 또한 데이터 베이스는 여러 명의 사용자나 응용 프로그램이 공유하고 동시에 접근 할 수 있어야 한다. DBMS는 데이터 베이스를 관리하는 역할을 하는 소프트웨어의 개념으로 접근 해야하고 다음과 같은 몇 가지 중요한 특징을 가지고 있다. 데이터의 무결성 데이터베이스 안의 데이터는 어떤 경로를 통해 들어 왔던 데이터의 오류가 있어서는 안된다. 무결성( Integrity)를 위해 데이터베이스는 제약 조건(Constraint)이라는 특성을 가진다. 💡 예를 들어 학생의 학번은 반드시 있어야 하며 학번은 서로 중복되면 안되는 제약 조건이 있다..

Longest Increasing Subsequence 나무위키 최장 증가 부분 수열 - 나무위키 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. namu.wiki 최장 증가 부분 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. `3 5 7 9 2 1 4 8` 위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다. 3 7 9 1 4 8 (5, 2 제거..

트리(Tree)는 계층적인 구조를 표현하는 비선형 자료구조로 노드(Node)와 간선(Edge)으로 이루어져 있으며, 루트(Root) 노드에서부터 여러 개의 자식 노드들이 분기(Branch)되어 나가는 형태로 구성된다. 대표적인 트리의 종류는 다음과 같다. 삼항 트리(Ternary Tree) : 각 노드가 최대 세 개의 자식 노드를 갖는 구조 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 갖는 구조 이진 검색 트리(Binary Serach Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 자신의 값 이하이며,오른쪽 자식의 값은 자신의 값 이상이다. 이진 검색 트리의 장점 가운데 하나로 룩업 연산(특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수..

출처 엔지니어 대한민국 문제 1. Graph에서 두지점의 경로찾기 그래프에서 두 개의 노드가 서로 찾아갈 수 있는 경로가 있는지 확인하는 함수를 구현해보자 그래프에서 특정 노드 A와 B를 잇는 간선의 존재 여부를 판단하는 메서드이다. DFS와 BFS 두 가지 방법 모두 경로를 찾을수 있지만 이런 문제의 경우 시작점을 기준으로 영역을 점차 넓히며 접근하는게 조금 더 빠른 방법일 수 있기 때문에 BFS, 넓이 우선 탐색을 사용해 접근한다. 구현 import java.util.LinkedList; import java.util.Iterator; import java.util.NoSuchElementException; class Queue{ } class Graph{ class Node{ int data; //..

그래프(Graph)와 트리(Tree)는 모두 노드(Node)와 노드를 연결하는 간선(Edge)으로 구성된 자료 구조이지만 몇 가지 차이점이 존재한다. 순환(cycle)의 존재 여부 그래프는 순환을 가질 수 있지만, 트리는 순환을 가질 수 없다. 트리는(DAG, Directed Acyclic Graph)라고도 부른다. 루트(Root)의 존재 여부 - 트리는 하나의 루트 노드를 가지며, 모든 노드는 루트 노드로부터 유일한 경로로 연결된다. - 그래프에는 루트 노드가 없다. 간선의 방향성 그래프의 간선은 양방향일수도 있고, 단방향일수도 있지만 트리는 단방향이다. 연결성 그래프에서는 연결성(Connectivity)이 중요한 개념이지만, 트리에서는 연결성이 보장된다. 즉, 트리는 모든 노드가 연결되어 있어서 어떤..

그래프를 검색하는 방법은 대표적으로 깊이 우선 검색(Depth-First Search, DFS), 넓이 우선 검색(Breadth-First Search, BFS)가 있다. DFS DFS는 이진 트리를 순회할 때 사용했던 inorder, preorder, postorder 순회 방법이 깊이 우선 검색에 속하는데 시작 노드에서 자식 노드로 탐색을 진행하다 더 이상 탐색할 자식 노드가 없으면 부모 노드로 돌아가 다음 자식 노드를 탐색하고 이 과정을 반복해 그래프를 끝까지 탐색하게된다. DFS는 모든 노드를 탐색하며, 각 노드를 한 번씩 방문한다. DFS는 그래프에서 연결된 모든 노드를 방문할 수 있으며, 이를 통해 그래프의 구조를 파악하는데 도움이 된다. 또한, 그래프에서 경로를 찾거나 사이클을 검사하는데 사..

Big-O Big-O는 알고리즘의 성능을 수학적으로 표기해주는 표기법으로 시간과 공간 복잡도를 표현할 수 있다. Big-O 표기법은 알고리즘의 실제 러닝 타임을 표시하기보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는게 목표이기 때문에 상수와 같은 숫자는 모두 1이 된다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있다. 빅오(O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다. 시간 복잡도(Time Comp..

빅오, 자료형 컴퓨터 과학에서 빅오(Big-O)는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용 되며, 알고리즘의 효율성을 분석하는 데에도 매우 유용하게 활용된다. 💡 빅오(O, big-O)란 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법이다 먼저, 빅오는 점근적 실행 시간(Asymptotic Running Time)을 표기할 때 가장 널리 쓰이는 수학적 표기 방법 중 하나로 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 lim 함수의 실행 시간의 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입..