나작코

레드 블랙 트리(Red-Black Tree)란 노드에 각 색을 부여하여 트리의 균형을 유지하며 탐색, 삽입, 삭제 연산의 수행 시간이 각각 O(logn)을 넘지 않는 매우 효율적인 자료구조입니다. 일반적으로 삽입이나 삭제를 수행할 때 트리의 균형을 유지하기 위해 상당히 많은 경우를 고려해야 한다는 단점이 있습니다. 그러나 좌편향 레드 블랙(Left-Leaning Red-Black; LLRB) 트리는 삽입이나 삭제 시 고려해야 하는 경우의 수가 적으며, AVL 트리, 2-3 트리, 2-3-4 트리, 일반 레드 블랙 트리보다 매우 우수한 성능을 보입니다. LLRB 트리는 다음의 조건을 만족합니다. 루트와 null은 블랙 루트로부터 각 null까지 2개의 연속된 레드 link는 없음 루트로부터 각 null까지..

유효성 검사(validation)란 입력 내용이 요건에 만족하는지 그 타당성을 확인하는 입력 체크를 말합니다. 크게 두 개로 나뉘는데, 단일 항목 검사와 상관 항목 검사가 있습니다. 단일 항목 검사란 입력 항목 하나에 대해 설정하는 입력 체크 기능입니다. Form 클래스 등의 필드에 어노테이션을 부여해서 사용합니다. 상관 항목 검사란 여러 필드에 대해 혼합해서 체크하는 것을 말합니다. 상관 항목 검사를 수행하는 방법에는 두 가지가 있습니다. Bean Validation을 사용하는 방법과 스프링 프레임워크에서 제공하는 Validator 인터페이스를 구현하는 방법입니다. Validator 인터페이스를 구현하기 위해서는 커스텀 유효성 검사기를 주입하고 WebDataBinder 인터페이스의 addValidato..

AVL 트리란 트리가 한쪽으로 치우쳐 자라나는 현상을 방지하여 트리 높이의 균형을 유지하는 이진 탐색 트리를 의미합니다. 트리에 노의 삽입이나 삭제로 인해 균형이 깨졌을 때, 회전 연산을 통하여 트리의 균형을 유지합니다. 왼쪽과 오른쪽 서브트리의 높이 차이가 2 이상일 때 불균형이 발생했다고 합니다. AVL 트리에서 삽입 또는 삭제 연산을 수행할 때 트리의 균형을 유지하기 위해 LL, RR, LR, RL 회전 연산이 사용됩니다. 각 회전 연산은 두 종류의 기본적인 연산으로 구현되는데, 오른쪽으로 회전하는 rotateRight와 왼쪽으로 회전하는 rotateLeft입니다. AVL 트리에서의 삽입과 삭제 구현 코드 class Node { int key; int height; Node left; Node ri..

이진 탐색 트리(Binary Search Tree; BST)란 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조입니다. 이진 탐색을 수행하기 위해 단순 연결 리스트를 변형시킨 것입니다. 이진 탐색은 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법입니다. 각 노드 n에 저장된 키가 n의 왼쪽 서브트리에 있는 노드에 저장된 키보다 크고 n의 오른쪽 서브트리에 있는 노드의 키보다 작은 것이 이진 탐색 트리의 조건입니다. 각각의 서브 트리도 이진 탐색 트리를 유지하면서 중복된 키를 허용하지 않습니다. 특징 중 하나는 트리를 중위 순회(Inorder Traversal)하면 오름차순으로 정렬된 출력을 얻을 수 있다는 점입니다. 또 균형이 유지된 이진..

이진 트리(Binary Tree)는 각 노드의 자식 수가 2 이하인 트리를 의미합니다. 데이터의 구조적인 관계를 잘 반영하고, 효율적인 삽입과 탐색을 가능하게 하며, 이진 트리의 서브트리를 다른 이진 트리의 서브트리와 교환하기가 쉽습니다. 이진 트리에는 두 종류의 특별한 형태를 가진 트리가 존재합니다. 모든 이파리의 깊이가 같고 각 내부의 노드가 2개의 자식을 가지는 포화 이진 트리(Perfect Binary Tree)와 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 완전 이진 트리(Complete Binary Tree)입니다. 완전 이진 트리를 저장하기 위해 배열을 사용하는 경우, 레퍼런스를 저장할 메모리 공간이 필요 없으므로 매우 효율적입니다...

트리(Tree)란 실제 트리를 거꾸로 세워 놓은 형태의 자료구조입니다. 노드와 링크로 구성되어 있습니다. 하나의 노드에서 다른 노드로 이동하는 경로가 유일하며, 모든 노드는 서로 연결되어 있습니다. 배열이나 연결 리스트는 데이터를 일렬로 저장하기 때문에 일반적으로 탐색 연산이 순차적으로 수행되어야 한다는 단점을 가집니다. 트리는 이러한 문제점을 보완하여 다양한 형태로 광범위하게 응용됩니다. 일반적인 트리(General Tree)는 HTML과 XML의 문서 트리, 자바 클래스 계층구조, 운영체제의 파일 시스템, 탐색 트리, 이항 힙, 피보나치 힙과 같은 우선순위 큐에서도 사용됩니다. 이를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스를 저장해야 합니다. 따라서 트리 노드의 최대 차수가 k라면,..

요청 파라미터(request parameter)란 클라이언트에서 서버로 전송되는 값을 의미합니다. 요청 파라미터의 종류에는 요청 쿼리 스트링(GET) 또는 요청 본문(POST)으로 보내지는 값처럼 뷰에서 입력한 값이나 선택 값, 숨김 파라미터로 전송된 값 등이 있습니다. 또는 뷰에서 클릭한 버튼의 name의 속성 값, URL 경로의 일부로 보내지는 값 등이 있습니다. 이를 취득하는 방법은 다음과 같습니다. @RequestParam Form 클래스 내용 어노테이션을 이용하여 파라미터를 하나씩 취득 스프링 MVC가 Form 클래스 내의 필드에 대해 값을 저장 상황 하나의 뷰에 버튼이 여러 개 있을 때 어느 버튼이 클릭되어 요청이 보내졌는지 식별 요청 파라미터를 모아 하나의 객체로 받아들임 장점 간편하고, 각..

데크(Double-ended Queue; Deque)란 양쪽 끝에서 삽입과 삭제를 허용하는 자료구조입니다. 스택과 큐 자료구조를 혼합한 자료구조라고 할 수 있습니다. 예를 들어 스크롤, 문서 편집기 등의 undo 연산, 웹 브라우저의 방문 기록 등에 사용됩니다. 웹 브라우저 방문 기록의 경우, 최근 방문한 웹 페이지 주소는 앞에 삽입하고 일정 수의 새 주소들이 앞쪽에서 삽입되면 뒤에서 삭제가 수행됩니다. 데크를 배열이나 이중 연결 리스트로 구현한 경우, 스택과 큐의 연산 수행 시간과 같습니다. 하지만 양 끝에서 삽입과 삭제를 할 수 있으므로 프로그램이 복잡해집니다. 자바는 java.util 패키지에서 Deque 인터페이스를 제공하며 이는 Queue에서 상속됩니다. 주요 메소드 삽입 addFirst(): ..

큐(Queue)란 선입선출(FIrst In First Out; FIFO), 먼저 들어온 데이터가 먼저 나가는 구조입니다. 단방향에서의 삽입과 삭제가 가능한 스택과 달리, 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조입니다. 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기가 대표적인 큐의 예시입니다. 큐는 선형 자료구조이므로 1차원 배열 또는 단순 연결 리스트로 구현합니다. 그러나 배열로 구현하는 경우 삽입과 삭제를 거듭하면 큐의 항목이 배열의 오른쪽 부분으로 편중되는 문제가 발생합니다. 새 항목은 뒤에 삽입되고 삭제는 앞에서 일어나기 때문입니다. 이를 해결하는 방법 중 하나는 큐의 항목을 배열의 앞부분으로 이동시켜 배열의 마지막 원소가 첫 원소와 맞닿아 있도록 구현하는 것입니다. 연결 리스..

스택(Stack)이란 후입선출(Last In First Out; LIFO), 즉 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용합니다. 예를 들어 함수 콜 스택, 수식 계산, 인터럽트 처리 등이 있습니다. 데이터 추가, 꺼내기, 스택 공간 확인 동작으로 이루어집니다. 스택의 동작 예시 다음과 같습니다. ↓push() ↑pop() 3(3) 3(1) 2(2) 2(2) 1(1) 1(3) 일반 숫자는 원소, 괄호 안 숫자는 순서를 의미합니다. 예를 들어, push는 1, 2, 3 순서대로 원소가 삽입되었습니다. 그러나 pop으로 원소를 꺼내고자 할 때에는 3, 2, 1과 같이 삽입할 때의 역순으로 원소를 꺼내게 됩니다. 스택에서는 항목을 위에서 push하..