[Algorithm] Bubble Sort (거품 정렬) 1. 정의 서로 인접한 두 원소의 대소를 비교하고, 더 큰 원소를 뒤로 보내서 정렬하는 알고리즘 시간 복잡도 최선 : $O(n^2)$ 평균 : $O(n^2)$ 최악 : $O(n^2)$ 2. 동작 과정 첫 번째 원소와 두 번째 원소의 대소를 비교하여 첫 번째 원소가 더 크다면 두 원소의 위치를 바꾼다. 두 번째 원소와 세 번째 원소의 대소를 비교하여 두 번째 원소가 더 크다면 두 원소의 위치를 바꾼다. ... n - 1. (n - 1) 번째 원소와 n 번째 원소의 대소를 비교하여 (n - 1) 번째 원소가 더 크다면 두원소의 위치를 바꾼다. → 이런식으로 탐색 시작 범위를 하나씩 증가시키며 정렬을 진행한다. 3. 장단점 장점 구현이 매우 간단, ..
CS
[데이터베이스] 인덱스 1. 인덱스란? 데이터베이스의 저장 성능을 희생(약 10%)하고, 읽기 속도를 높이는 기능 책의 목차와 비슷함. 2. 장단점 장점 읽기 성능↑ 시스템 부하↓ 단점 데이터 추가, 삭제 시 성능 감소 INSERT, UPDATE, DELETE 시 추가 연산이 필요하기 때문 INSERT : 새로운 인덱스 추가 UPDATE : 기존 인덱스를 사용하지 않음 처리 및 갱신된 데이터의 인덱스 추가 DELETE : 삭제하는 데이터의 인덱스를 사용하지 않음으로 변경 데이터 베이스의 용량을 추가적으로 차지 3. 사용하는 곳 규모가 작지 않은 테이블 변경이 자주 발생하지 않는 컬럼 JOIN, WHERE, ORDER BY에 자주 사용되는 컬럼 카디널리티(기수성)이 높은 컬럼 카디널리티 : 한 컬럼이 갖고..
쿠키와 세션 1. 쿠키와 세션을 사용하는 이유 HTTP 프로토콜의 특성 때문 → 서버가 클라이언트가 누구인지 매 요청 마다 확인을 해야 함. 무상태 프로토콜 : 통신의 상태를 유지하지 않음 비연결성 : 클라이언트가 응답을 받으면 연결을 끊음 2. 쿠키 클라이언트 로컬에 저장되는 키와 값이 들어있는 데이터 HTTP의 일종 특징 이름, 값, 만료일(저장기간), 경로 정보로 구성 클라이언트에 총 300개의 쿠키를 저장 가능 하나의 도메인 당 20개의 쿠키를 가질 수 있음 하나의 쿠키는 4KB까지 저장 가능 Response Header에 Set-Cookie 속성으로 만들 수 있음 사용자가 요청하지 않아도 브라우저가 Request를 할 때 Request Header를 넣어서 자동으로 서버에 전송 동작 방식 클라이..
[자료구조] Red Black Tree 1. 정의 BST를 기반으로하는 트리 형식의 자료구조 검색, 삽입, 삭제의 시간이 $O(logN)$이 소요 됨 2. 규칙 모든 노드는 빨간색이나 검은색 루트는 항상 검은색 새로 추가되는 노드는 빨간색 루트에서 잎 노드로 가는 모든 경로에는 같은 수의 검은색 노드가 있어야 함 어떤 경로에서도 빨간색 노드가 연속으로 2개가 있으면 안됨 모든 빈 노드(null)는 검은색이라고 가정 2.1 균형을 맞추는 방법 이모 노드가 검은색인 경우 회전을 시킴 회전 후에, 부모 노드는 검은색, 두 자식 노드는 빨간색이어야 함 이모 노드가 빨간색인 경우 색깔을 전환 전환 후에, 부모 노드는 빨간색, 두 자식 노드는 검은색이어야 함 3. 구현 public class RedBlackTree..
[자료구조] AVL트리 1. 정의 스스로 균형을 잡는 이진 탐색 트리 왼쪽과 오른쪽의 높이 차가 1이하여야 함. 항상 O(logN)의 시간복잡도를 보장 2. 구현 //AVL트리의 생성자 public AVLTree() { root = null; currentSize = 0; } //기본 노드 class Node { T data; Node left; Node right; Node parent; public Node(T obj) { data = obj; parent = null; left = null; right = null; } } //추가 메서드 public void add(E obj) { Node node = new Node(obj); if (root == null) { root = node; curre..
[자료구조] 힙 1. 정의 이진 트리 구조로 이루어져 있다. 최대값과 최소값을 빨리 찾아낼 수 있다. 최대 힙 항상, 자식 노드 부모 노드 관계를 만족해야 한다. 노드의 개수를 n이라고 하면 트리의 높이는 $log_2(n+1) - 1$로 구할 수 있다. 2. 추가 제거 이제부터 최대 힙 기준으로 설명하겠습니다. 추가 비어있는 공간에 노드를 추가한다. 부모 노드보다 자식 노드가 더 크면 두 노드의 자리를 바꾼다. public void add(E obj) { array[++lastposition] = obj; // 1. 노드 추가 trickleUp(lastposition); // 2. trickle up - 부모 노드와 자식 노드를 바꿀지 ..
[자료구조] 트리 1. 정의 트리는 각각의 노드들을 간선(edge)로 연결한 자료구조로써, 각각의 노드들은 부모-자식 관계를 가진다. 뿌리(root): 트리의 시작 잎(leaf): 자식이 없는 노드 간선의 수에 따라 level을 나눈다. 1.1 완전 트리(Complete Tree) 잎이 아닌 모든 노드가 2개의 자식 노드를 가지고 있고, 마지막 줄은 왼쪽에서 오른쪽 순서로 채워져 있는 트리 1.2 정 트리(Full tree) 잎이 아닌 모든 노드가 2개의 자식 노드를 가지고 있고, 모든 잎이 같은 레벨에 있는 트리 2. 순회 전위 순회(Pre order traversal / Depth first traversal) : 루트 노드에서 시작하여, 왼쪽 자식 노드로 갔다가 오른쪽 자식 노드로 가는 순회 방법 ..
[자료구조] 해시 1. 해시 데이터를 빠르게 추가하거나 제거하도록 하는 데이터 구조 키(key)와 값(value)를 가지고 있음 → 키가 주어지면 평균 O(1)의 속도로 값을 찾을 수 있음 2. 해시함수 속도가 빠름 데이터의 속성 두개가 같으면 같은 값을 반환해야 함 동일한 상황일 때 항상 같은 값을 반환해야 함 새로 실행하면 객체가 같아도 다른 값이 나올 수 있음 → 객체들은 실행할 때마다 다른 주소에 저장되기 때문 충돌(collison)이 발생하지 않도록 만들어야 함 충돌: 서로 다른 값을 가진 키가 일치하는 경우 해시의 크기를 홀수로 설정(% 연산으로 다양한 값이 나오게 함) 해시의 크기를 소수로 설정 해시 함수의 반환 값을 hashcode라고 함 → 해시 테이블의 인덱스를 결정 해시코드는 최대한 ..
