개인기록부 개인기록부

Set 실무에서 자주 쓰이는 자료구조는 대표적으로 List와 Set이 존재한다. 그 중 Set은 데이터를 저장하는 추상 자료형(ADT)로 순서를 보장하지 않고 데이터 중복을 허용하지 않는다는 특징이 있다. 데이터 조회(search)에 있어서 List 보다 더 빠른 속도를 가지는데 Set 자료형은 O(1)의 시간 복잡도를 갖는다. 중복된 데이터를 제거해야 할 때 Set을 사용하기 좋으며 데이터의 존재 여부를 확인할 필요가 있을때 역시 Set 사용을 고려할 수 있다. (이 경우 필터링이 필요한 상황을 떠올려보자) Set의 구현체 set을 구현한 구현체는 크게 세 가지로 Hash Set, Linked Hash Set, Tree Set이 존재하는데 그 중 Hash Set에 대해 다뤄보자 Hash Set은 해시 ..

배열과 0번 인덱스 Array란 같은 타입의 데이터들을 저장하는 자료 구조로 연속된 메모리 공간에 데이터를 저장한다는 특징이 있다. 필드에 데이터를 저장하는것과 달리 연속된 데이터의 각각엔 이름이 없지만 인덱스를 통해 해당 데이터에 접근할 수 있다. 이 때 인덱스 번호는 0부터 시작하게 되는데 이는 배열에서 인덱스가 offset 개념으로 사용 되기 때문이다. C와 같은 프로그래밍 언어에서 특정 영역의 메모리 주소는 기준 주소와 offset으로 계산되는데 기준 주소가 a이고 각 프레임의 크기가 s라고 할 때, i 번째 프레임의 주소값은 다음과 같은 등차수열의 일반항을 통해 계산할 수 있다. a + s * (i - 1) # 1-based a + s * i # 0-based 여기서 0-based 방식은 런타임..

개요 리프 노드의 수는 BST와 B-Tree를 구별하는 주요 차이점 중 하나로 BST는 두 개로 고정이되는 반면, B-Tree는 차 수에 따라 말단 노드의 개 수가 결정된다. 만약 데이터를 삽입하는 과정을 갖는다면 항상 리프 노드에서 발생하게 되는데 이는 삭제하는 과정 역시 동일하지만 삽입을 통해 자녀 노드의 수가 기준 값 보다 커졌을 경우 승진을 통한 재조정이 발생하지만 삭제의 경우 key의 개수가 최소 key의 수보다 적어졌다면 재조정이 이루어지게된다. B-Tree에 저장되는 데이터가 있다면 이 데이터 각각은 Key를 통해 동작하지만 여기선 데이터가 Key의 역할까지 수행하기 때문에 두 단어를 혼용해서 사용한다. 데이터 삭제 과정 다음과 같은 3차 B-Tree가 존재한다고 했을때, 데이터 삭제 과정에..

이진 탐색 트리 BST 이진 탐색 트리가 가지는 특징 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고, 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가질 수 있고 자녀 노드는 최대 두 개까지 가질 수 있다. 트리 형태의 자료 구조의 특성상 깊이가 깊어질수록 소모되는 자원이 커질 수 밖에 없기 때문에 최대한 작은 depth를 통해 많은 자녀 노드를 확보할 필요가 있다. 이 생각을 바탕으로 기존 BST를 확장해 값의 범위를 세분화하게 되면 아래와 같이 범위를 갖는 트리 구조를 얻게 된다. 이 방식을 적용하면 이진 탐색 트리와 동일한 방식으로 동작 하면서도 하나의 노드가 자녀 노드의 개 수를 두 개 이상도 가질 수 있도록 만들 수 있는것이다. 범위를 갖게된 노드를 서브 ..

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)이 중요한 개념이지만, 트리에서는 연결성이 보장된다. 즉, 트리는 모든 노드가 연결되어 있어서 어떤..