DEVNOTE

Red-Black Tree 정의 이진탐색트리를 기반으로 하는 트리형식의 자료 구조이며, 동일한 노드의 개수일 대, depth를 최소화하여 시간 복잡도를 줄여주는 구조임 각 노드는 Red or Black의 색깔을 가짐 Root node의 색깔은 Black임 각 Leaf node는 Black 어떤 노드의 색깔이 Red일 경우 두개의 자식 노드의 색깔은 모두 Black Red-Black Tree 특징 이진탐색트리이므로 이진탐색트리의 특징을 가짐 Root node 부터 Leaf node까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않음 이러한 상태를 balanced 상태 이진탐색트리의 삽입, 삭제 과정에서 발생하는 문제점을 해결함 노드의 child 가 없을 경우 child 를 가리키는..

트리 비선형 자료구조이며, 계층적 관계를 표현하는 자료구조 연결 리스트와 비슷하지만 노드 한개가 다른 여러 노드를 가리키는 자료구조 즉 노드로 이루어진 자료구조 트리는 하나의 루트 노드를 가지며, 루트 노드는 0개이상의 자식 노드를 가짐, 자식 노드 또한 0개이상을 자식 노드를 가지게 되며, 이는 반복적으로 정의 됨 트리 용어 노드 (Node) : 트리를 구성하고 있는 요소를 의미 루트 (Root) : 부모가 없는 노드, 즉 트리구조에서 최상위에 있는 노드를 의미함, 트리에는 최대 한개 루트만 존재 간선 (Edge) : 트리를 구성하기 위하여, 노드와 노드를 연결하는 선을 의미, 즉 부모에서 자식으로 이어지는 연결선 리프 (Leaf) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미, 즉 자식이 없..

정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것 정렬은 프로그램 작성시 빈번하게 필요 다양한 알고리즘이 고안되었으며, 알고리즘 학습의 필수 버블정렬 (Bubble sort) 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 선택정렬 (Selection sort) 주어진 데이터 중, 최소값을 찾은뒤 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함, 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복하는 정렬 알고리즘 삽입정렬 (Insertion sort) 두번째 인덱스부터 시작하여, 해당 인덱스 앞에 있는 데이터(B) 부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스를 복사함, 이를 key 값이 더 큰 데이터를 만날..

최단 경로 문제 두 노드를 잇는 가장 짧은 경로를 찾는 문제 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류 단일 출발 최단 경로 문제 : 그래프 내의 특정 노드 u에서 출발하여, 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 단일 도착 최단 경로 문제 : 모든 노드들로 부터 출발해서, 그래프 내의 특정 노드 u로 도착하는 가장 짧은 경로를 찾는 문제 단일 쌍 최단 경로 문제 : 주어진 노드 u와 v간의 최단경로를 찾는 문제 전체 쌍 최단 경로 : 그래프 내의 모든 노드 쌍 사이에 대한 최단 경로를 찾는 문제 다익스트라 알고리즘 (최단경로 알고리즘) 다익스트라 알고리즘은 단일 출발 최단 경로..

순차탐색 (Sequential Search) 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법 순차적으로 탐색하기 때문에 최악의 경우 리스트 길이가 n일 경우, n번 비교해야해서 시간복잡도가 O(n) 이진탐색 (Binary Search) 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 (대상 리스트가 정렬이 되어 있어야함) 이진탐색은 분할정복 알고리즘을 활용하여 사용 Divide : 리스트를 두개의 서브 리스트로 나눔 Conquer : 검색대상 > 중간값이면, 뒷 부분 서브리스트에서 검색대상 찾음, 검색대상 < 중간값이면, 앞 부분 서브리스트에서 찾음 n개의 리스트를 매번 2로 나누어 1이 ..

재귀 호출 함수 안에서 동일한 함수를 호출하는 방법 여러 알고리즘 작성시 사용됨 재귀 호출은 스택의 전형적인 예 (호출함수가 내부적으로 스택처럼 관리됨) 재귀 호출은 중단하기 위한 종료조건문이 필수 재귀 호출 특징 코드가 간결함 무한 재귀호출의 위험성 (종료조건 실수할 경우), 성능상의 문제 재귀 호출 대표적인 예시 (팩토리얼) public int factorial(int n) { if (n == 1) { return 1; } return n * factorial(n-1); } 규칙 : n! = n x (n - 1)!, f(1) = 1 factorial(n)은 n - 1 번의 factorial() 함수를 호출하여, 곱셉을 함 (n - 1번 반복문을 호출한 것과 동일한 형태) factorial() 함수를 ..

백트래킹 (Backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위하여, 후보군 제약조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 Backtrack(다시는 해당 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가, 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모둔 경우의 수를 상태공간트리(State Space Tree)를 통하여 표현 각 후보군은 DFS로 확인하며, 상태공간 트리를 탐색하면서, 제약이 맞지 않으면 후보가 될만한 곳으로 넘어가서 바로 탐색 상태공간트리 (State Space Tree) 문제 해결 과정의 중간 상태를 각각의 노드로 나타낸 트리 상태공간트리 탐색 기법 Promising : 해당 루..

캐시 정의 빠른 검색과 조회를 위해 자주 사용되는 데이터나 값을 미리 복사해 놓는 임시 장소 주로 데이터 접근시 오래걸리거나 값을 다시 계산해야할 때 절약해야 하는 경우 사용 LRU (Least Recently Used) 캐시 최근에 가장 오래 사용하지 않은 페이지를 교체하는 기법 캐시에 공간이 부족시 가장 최근에 사용하지 않은 데이터(가장 오래된 데이터)를 제거 메모리 상에서 가장 오래된 데이터를 새로운 데이터로 갱신함 자바 구현 예시 LinkedList로 구현 public class LRUCache { public int size; public LinkedList cache; public LRUCache(int size) { this.size = size; this.cache = new LinkedL..

복잡도 프로그램의 실행이 얼마나 오래 걸리는지, 얼마나 많은 메모리를 사용하는지 시간복잡도 알고리즘에 사용되는 연산횟수의 총 횟수 절대적인 수행시간이 아닌 연산횟수를 기준으로 측정함 연산횟수를 카운팅 할 때 3가지 경우가 있지만 보통 최악의 경우(빅오표기법)을 기준으로 함 공간복잡도 알고리즘의 메모리 사용량에 대한 분석 결과 프로그램을 실행 완료하는데 필요한 저장공간의 양 보통 가변공간(실행 중 동적으로 필요한 공간)에 따라서 복잡도가 좌우됨 빅오표기법 주어진 함수에서 엄밀한 점근적 상한을 나타내는 점근적 표기법 가장 증가율이 높은 수식만 남김 연산 횟수는 O(1) → O(logn) → O(n) → O(nlogn) → O(n²) → O(2^n) → O(n!) 갈수록 증가함 예시 /** * 인프런 더개발자..