24.11.17 CS

CS

RDBMS VS NoSQL

데이터 모델

• RDBMS
  • 데이터를 표 형태(테이블)로 저장한다.
  • 테이블 간에는 명확한 관계(키와 외래 키등)가 있으며, 구조화된 스키마를 따라야 한다.
  • SQL을 사용하여 데이터를 관리한다.
• NoSQL
  • 데이터 모델링에 유연성을 제공한다. 관계형 데이터베이스처럼 고정된 스키마가 없고, 여러 가지 데이터 저장 방식을 지원한다.

스키마

• RDBMS
  • 고정된 스키마를 가지고 있다.
  • 데이터가 정규화되어 있다.
  • 스키마를 미리 정의해야 한다.
  • 데이터는 테이블의 각 열에 맞춰 엄격하게 구조화되어야 한다.
• NoSQL
  • 동적 스키마 또는 스키마가 없을 수 있다.
  • 데이터 구조가 각 레코드마다 다를 수 있어, 유연하게 데이터 형태를 변경할 수 있다.

확장성

• RDBMS
  • 수직 확장에 더 적합하다.더 큰 서버로 교체하거나 하드웨어 성능을 높여 처리 능력을 향상시키는 방식이다.
• NoSQL
  • 수평 확장에 더 유리하다. 서버를 추가함으로써 시스템의 용량과 성능을 증가시킬 수 있다.

데이터 일관성

• RDBMS
  • ACID 특성을 보장한다. 트랜잭션의 일관성을 유지하고 중요한 금융, 회계와 같은 시스템에서 사용된다.
• NoSQL
  • CAP 이론에 따라 설계되었다. 대부분 BASE 접근 방식을 따른다. 일관성보다는 가용성이나 파티셔닝에 초점을 맞춘다.

연결리스트 VS 리스트

기본 개념

• 연결 리스트
  • 노드의 연결로 이루어진 선형 자료 구조이다. 각 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
  • 연결 리스트에는 주로 단일 연결 리스트, 이중 연결 리스트 등이 있다.
• 리스트
  • 연속적인 메모리 공간에 데이터를 저장하는 자료 구조이다. 정해진 크기만큼의 메모리를 한 번에 할당하여 데이터를 효율적으로 접근할 수 있기 설계되어 있다.

메모리 구조

• 연결 리스트
  • 비연속적인 메모리 공간에 노드를 저장한다. 각 노드는 다음 노드의 주소를 가지고 있어 메모리가 불연속적으로 할당될 수 있다. 크기가 유동적이며, 삽입/삭제가 편하다.
• 리스트
  • 연속적인 메모리 공간에 데이터를 저장한다. 각 요소는 인덱스를 통해 쉽게 접근 가능하다.

시간 복잡도 비교

• 접근
  • 연결 리스트 : 특정 인덱스로의 접근이 불가능하다. 원하는 요소를 찾기 위해 처음 노드부터 순차적으로 접근해야 하므로 시간 복잡도는 O(n)이다.
  • 리스트 : 인덱스를 통한 직접 접근이 가능하므로 시간 복잡도는 O(1)이다.
• 탐색
  • 둘 다 특정 값을 찾기 위해 모든 요소를 확인해야 하므로 일반적으로 시간 복잡도는 O(n)이다.
• 삽입
  • 연결 리스트 : 삽입할 위치를 알고 있다면 O(1) 시간 안에 삽입할 수 있다. 노드 참조만 필요하기 때문에 빠르다.
  • 리스트 : 중간에 삽입할 경우 뒤의 요소들을 한 칸씩 밀어야 하므로 평균적으로 O(n)의 시간 복잡도가 필요하다.
• 삭제
  • 연결 리스트 : 삭제할 노드를 알고 있다면 O(1) 시간에 삭제할 수 있다. 삭제할 노드의 이전 노드가 삭제 후 다음 노드를 가리키도록 하면 된다.
  • 리스트 : 중간에 요소를 삭제할 경우 뒤의 요소들을 한 칸씩 당겨야 하므로 평균적으로 O(n)의 시간 복잡도가 필요하다.

장단점 비교

• 연결 리스트
  • 장점
    • 삽입 및 삭제가 빠르다. 특히 데이터의 중간에서 삽입/삭제가 자주 발생하는 경우에 유리하다.
    • 메모리 크기를 유연하게 조절할 수 있다.
  • 단점
    • 인덱스를 통한 직접 접근이 불가능해 탐색 속도가 느리다.
    • 각 노드가 포인터를 저장하기 때문에 추가적인 메모리가 필요하다.
• 리스트
  • 장점
    • 인덱스를 통한 빠른 접근이 가능해 읽기 연산이 매우 효율적이다.
    • 캐시 효율성이 좋아서 cpu의 캐시 메모리를 효과적으로 사용할 수 있다.
  • 단점
    • 중간에 삽입 및 삭제가 비효율적이다.
    • 배율의 크기를 미리 할당해야 하며, 크기를 조절하는 작업이 비싸게 작용할 수 있다.

객체지향

캡슐화

• 캡슐화는 객체의 속성과 행동을 하나의 단위로 묶고, 외부에서 객체의 내부를 직접적으로 접근하지 못하게 제한하는 원칙이다. 객체의 데이터는 private또는 protected로 선언하고, 이를 제어하는 메서드는 public으로 제공한다.
• 데이터의 무결성을 보호하고, 객체 내부 구현을 외부에 감추어 쉽게 수정할 수 있게 한다.

상속

• 상속은 기존 클래스의 속성과 행동을 다른 클래스가 물려받아 재사용할 수 있도록 하는 기능이다. 기본 클래스로 부터 파생 클래스가 상속을 받는다. 코드의 재사용성을 높이고, 중복을 줄일 수 있다.

다형성

• 다형성은 동일한 인터페이스를 통해 서로 다른 동작을 수행할 수 있게 하는 것이다. 다형성에는 컴파일 시간 다형성(정적 다형성)과 런타임 다형성(동적 다형성)이 있다.
  • 정적 다형성 : 함수 오버로딩, 연산자 오버로딩 등 컴파일 시 결정되는 다형성
  • 동적 다형성 : 가상 함수와 다형성 포인터를 사용하여 런타임에 결정되는 다형성

추상화

• 추상화는 불필요한 세부 사항을 감추고 중요한 정보만을 보여주는 것을 의미합니다. 추상화를 통해 객체의 복잡성을 줄이고, 중요한 기능에만 집중할 수 있게 한다.

장점

• 재사용성
  • 상속을 통해 기존 코드를 재사용하고, 유지보수가 용이하다.
• 유연성과 확장성
  • 다형성을 통해 새로운 클래스나 메서드를 쉽게 추가할 수 있다.
• 캡슐화를 통한 데이터 보호
  • 데이터 무결성을 유지하고 보안성을 높인다.
• 현실 세계의 모델링
  • 객체지향은 현실 세계의 사물과 개념을 객체로 모델링하기 때문에 코드의 이해도와 유지보수가 용이하다.

단점

• 복잡성 증가
  • 클래스와 객체의 관계가 많아질수록 프로그램이 복잡해질 수 있다.
• 성능 문제
  • 다형성의 사용, 특히 가상 함수 호출은 일반 함수 호출보다 성능이 떨어질 수 있다.
• 학습 곡선
  • 객체지향 개념을 이해하는 데 시간이 필요하고, 설계가 복잡할 수 있다.

이분 탐색(Binary Search)

기본 개념

• 정렬된 데이터를 대상으로 특정 값을 찾는 알고리즘이다. 배열의 중간 요소를 확인하여 티켓 값이 중간 요소와 같으면 탐색을 종료하고, 타겟 값이 더 작으면 왼쪽 절반을 더 크면 오른쪽 절반을 다시 탐색한다.
• 이 과정을 반복하면서 탐색 범위를 좁혀나가, 원하는 값을 찾는 알고리즘이다.

  시간 복잡도

• 매번 탐색의 범위를 반으로 줄이기 때문에, 시간 복잡도는 O(log n)이다. 이는 탐색 알고리즘 중 매우 효율적인 방식에 속한다.

그래프와 트리

그래프

• 구성 요소
  • 정점
    • 그래프에서 데이터의 개별 항목을 의미하며, 일반적으로 노드라고 부른다.
  • 간선
    • 두 정점 간의 연결을 의미하며, 정점 간의 관계를 나타낸다. 방향이 있을 수도 있고 없을 수도 있다.
• 그래프의 종류
  • 방향 그래프
    • 간선이 특정한 방향을 가지는 그래프이다. 간선의 방향에 따라 연결이 일방향적으로 정의된다.
• 주요 특징
  • 사이클을 가질 수 있다.
  • 정점과 간선이 임의의 방식으로 연결될 수 있어 매우 유연한 구조를 가진다.
  • 순환 구조나 네트워크 모델링, 경로 탐색등에 사용된다.

트리

• 구성 요소
  • 루트 노드
  • 자식 노드
  • 부모 노드
  • 잎
  • 간선
  • 높이
• 트리의 종류
  • 이진 트리
  • 힙
  • 트라이
• 주요 특징
  • 사이클이 없는 방향 그래프의 한 종류이다. 즉, 사이클이 존재하지 않으며, 모든 노드는 하나의 부모를 가진다.
  • 트리는 계층 구조를 가지며, 계층적 관계를 나타내는 데 사용된다.

해시테이블

기본 개념

• 데이터의 키를 해시 함수에 전달하여 해시 값을 생성하고, 이 해시 값을 사용하여 데이터를 해시 버켓에 저장하는 방식으로 작동한다.
• 데이터의 키는 일반적으로 문자열이나 숫자일 수 있으며, 해시 함수는 이 키를 고유한 인덱스로 변환해 배열의 특정 위치에 저장한다. 이를 통해 해시 테이블은 매우 빠른 접근 시간을 제공한다.

해시 함수

• 해시 함수는 주어진 키를 입력으로 받아서 고정된 길이의 해시 코드로 변환하는 함수이다. 이 해시 코드는 일반적으로 배열 인덱스로 사용된다. 이 해시 코드는 일반적으로 배열 인덱스로 사용된다.
• 해시 함수는 다음과 같은 특성을 가져야 한다.
  • 1. 효율성 : 계산이 빠르며, 키를 적절히 분산시킬 수 있어야 한다.
  • 2. 균일 분포 : 해시 값이 고르게 분포되어야 충돌을 줄일 수 있다.

충돌과 해결 방법

• 해시 테이블에서 충돌이란 서로 다른 두 개 이상의 키가 같은 해시 값을 가지는 경우를 의미한다. 충돌은 해시 함수의 특성과 해시 버킷의 크기로 인해 발생한다. 이를 해결하기 위해 여러 기법들이 사용된다.
• 체이닝
  • 동일한 해시 값을 가지는 모든 요소를 연결 리스트로 저장하는 방식이다. 충돌이 발생하면 해당 인덱스에 있는 기존 데이터에 연결하여 추가한다.
  • 장점 : 간단하게 구현이 가능하며, 해시 버킷의 크기 제한에 덜 민감하다.
  • 단점 : 연결 리스트의 크기가 커질 경우 탐색 시간이 O(n)으로 증가할 수 있다.
• 오픈 어드레싱
  • 충돌이 발생하면 빈 버킷을 찾을 때까지 해시 테이블 내에서 다른 위치를 탐색하는 방식이다. 대표적인 탐색 방법으로는 선형 탐사, 제곱 탐사, 이중 해싱 등이 있다.
  • 장점 : 체이닝과 달리 추가적인 자료 구조가 필요하지 않다.
  • 단점 : 클러스터링 문제로 충돌이 많이질 수 있다.

해시 테이블의 장단점

• 장점
  • 빠른 데이터 접근 : 해시 함수의 계산을 통해 데이터에 O(1) 시간으로 접근할 수 있어, 검색, 삽입, 삭제 모두 빠르다.
  • 다양한 응용 : 데이터베이스의 인덱스, 캐시 시스템, 딕셔너리, 집합 등 다양한 분야에서 사용된다.
• 단점
  • 해시 함수 품질에 의존 : 해시 함수가 키를 고르게 분산시키지 못하면 충돌이 많이 발생해 성능이 저하될 수 있다. 최악의 경우 모든 키가 같은 해시 값을 가지면 O(n) 시간 복잡도를 가질 수 있다.
  • 메모리 사용 비효율성 : 해시 테이블은 충돌을 줄이기 위해 일정한 양의 빈 공간을 확보해야 하므로, 메모리 사용량이 비효율적일 수 있다. 데이터가 많이 들어오면 테이블 크기를 늘려야 하며, 리해싱 작업이 필요할 수 있다.
  • 순서 보장 불가 : 해시 테이블은 데이터의 순서를 보장하지 않는다. 따라서 키를 삽입한 순서나 크기 순으로 데이터를 정렬하여 접근할 수 없다.