S E P H ' S

Red Black Tree RBT(Red-Black Tree)는 BST를 기반으로 하는 트리 형식의 자료구조이다. 결론부터 말하자면 Red-Black Tree에 데이터를 저장하게 되면 Search, Insert, Delete에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth가 최소가 되는 경우는 tree가 완전 이진 트리인 경우이다. Red-Black Tree 정의 Red-Black Tree는 다음의 성질들을 만족하는 BST이다. 1. 각 노드는 Red or Black이라는 색을 가짐 2. 루트 노드는 Black이다. 3. 각 단말 노드는 Black이다. 4. 어떤 노드의 색이..

배열(Array) 가장 기본적인 자료구조인 Array 자료구조는, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 따라서 인덱스(index)로 해당 원소(element)에 접근할 수 있다. 그렇기 때문에 찾고자 하는 원소의 인덱스 값을 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. 즉 random access가 가능하다는 장점이 있다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤 (O(1)), 또 한 가지의 작업을 추가적으로 해줘야 하기 때문에, 시간이 더 걸린다. 만약 배열의 원소 중 어느 원소를 삭제했다고 했을 때, 배열의 연속적인 특징이 깨지게 된다. 즉, 빈 공간이 생기는 것이다. 따라서 삭제한 원소보다 큰 인덱스를 갖는 원소들을 shift 해줘야 하..

좋은 코드란 무엇인가? 정의 컴퓨터 뿐만 아니라 함께 일하는 혹은 정보를 공유하는 개발자 간에 잘 익히도록 짜여진 코드 개발자 간에 소통하기 쉽도록 가독성이 좋아야 하는데, 가독성을 높이는 방법에는 여러가지가 있다. - 주석 & 문서화 - 일관된 들여쓰기 - 뻔한 주석은 달지 않기 - 코드를 그룹으로 묶기 - 일관된 네이밍 규칙 - DRY 원칙 (Don't Repeat Yourself) 같은 코드 반복하지 않기 - 코드가 깊어지는 것을 피하기 (Avoid Deep Nesting) - 줄길이 제한하기 - 파일과 폴더를 조직화하기 객체지향 프로그래밍이란 무엇인가? 정의 객체지향 프로그래밍(Object Oriented Programming)은 문제를 여러 개의 객체 단위로 나눠 작업하는 방식을 말한다. 이 방..