데이터베이스 ORM

자주 쓰는 자료구조와 알고리즘

자료구조와 알고리즘은 각각 상황에 맞는 문제를 해결하기 위한 데이터 

자주쓰는 자료구조

해시테이블

• 해시함수를 사용하여 변환한 값을 색인으로 삼아 key와 value로 저장하느 자료구조, 조회, 삽입 ,삭제가 있음
• 낮은 확률로 같은 해시값이 나오는 경우가 있는데 이때 해시 충돌 발생
• 빠른 검색속도로 조회시 시간복잡도는 O(1)를 가짐 키와 값을 연관시키기 때문에 빠른 검색속도
• 검색이 많이 필요한 경우 효율적인 자료구조

배열

• 속성이 비슷한 데이터들을 연속된 메모리 구조에 할당하는 자료구조
• 인덱스에 대한 조회 시간 복잡도는 O(1)이고 값에 대한 조회 시간복잡도는 O(n)이다
• 삽입, 수정, 삭제에 대한 시간복잡도는 O(n)이다 배열 중간에 데이터를 삽입,수정,삭제할때마다 각 데이터들의 위치를 옮겨야 하기 때문에 데이터를 옮길때 오버헤드가 발생함
• 데이터 조회에 가장 효율적인 자료구조

연결 리스트

• 데이터의 삽입,삭제가 배열보다 효율적임 배열은 연속된 메모리 주소를 사용하기 때문에 삽입,삭제시 데이터의 메모리 주소가 옮겨질때 오버헤드가 발생하는데 연결 리스트는 삽입, 삭제시, 연속된 메모리 주소가 아닌 서로 떨어진 메모리 주소를 가지고 다음 노드의 주소를 가리키는 포인터를 가지고 있기 때문에 삽입,삭제시 오버헤드가 발생하지 않음
• 노드 : 연결리스트의 기본 단위로써 데이터 필드, 포인트로 구성됨
• 동적으로 크기를 조절할 수 있음 , 필요에 따라 노드를 동적으로 생성하거나 제거하여 메모리를 효율적으로 관리할 수 있음, 삽입과 삭제 모두 O(1)의 시간복잡도를 가짐
• 특정 인덱스의 데이터에 바로 접근하는 것이 불가능하고 순차적느로 노드를 탐색하면서 찾고있는 값이 있는지 확인해야함 => 데이터 조회시 O(n)의 시간복잡도 를가짐
• 각 노드마다 데이터 필드, 포인터로 구성되기 때문에 배열과 비교 했을때 정확히는 O(3n)의 시간복잡도를 가짐
• 데이터의 삽입과 삭제를 처리할떄 효율적인 자료구조

스택

• LIFO형태의 자료구조로써, 끝이 막혀있는 통 형식의 자료구조, 늦게 삽입된 데이터가 먼저 나가는 형식
• 3가지 메소드로 구성됨 peek(), 스택의 맨위에 있는 데이터의 값을 가져옴(삭제는 x) , pop(), 맨위에 있는 데이터를 빼냄, push(), 데이터를 삽입
• 브라우저의 방문기록 , 자바스크립트 콜 스택 등에 사용됨

큐

• FIFO형태의 자료구조, 먼저들어온 데이터가 먼저 나가는 형식의 자료구조, 양쪽이 뚫려있는 파이프 형태
• 3가지 메소드로 구성됨 peek(), 큐의 맨 앞에있는 데이터의 값을 가져옴, shift() 큐 맨앞에 있는 데이터를 빼냄, push() 큐의 맨 뒤에 데이터를 삽입함
• cpu의 스케줄링, 티켓팅 대기열 등에 사용됨

트리

• 나뭇가지 형태의 자료구조, 루트 노드를 가지고 그 아래에 자식노드들을 두어 가지 처럼 퍼져나가는 자료구조
• 각 노드는 하나의 부모 노드와 0개 이상의 자식 노드를 가질 수 있음
• 자식 노드가 없는 노드는 리프(leaf)노드라고 부름
• 트리 자료구조는 자유도가 높아 여러가지 상황에 맞게 부가적인 트리 구조를 선택하여 데이터를 관리해야함
• 데이터의 조직화와 검색에 효과적인 자료구조
• 트리의 종류 : 이진 트리, 이진 탐색 트리, 균형 트리, 힙, 

자주쓰는 알고리즘

이진 탐색 (Binary Search)

• 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘
• 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 x와 비교함, x가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, x가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색
• ex) 업다운 게임=> 0부터 100중에 45를 찾으려고 할때 50을 기준으로 0부터 50은 배열의 왼쪽값, 51부터 100까지 배열의 오른쪽 값으로 설정하여 값을 찾는 범위를 점차 줄여나가는 알고리즘
• 이진 탐색의 시간 복잡도는 O(logN)을 가짐

정렬 알고리즘 (Sorting Alogrithms)

• 정렬 알고리즘은 n개의 숫자가 입력으로 주어 졌을 떄, 이를 사용자가 지정한 기준에 맞게 정렬하여 출력하는 알고리즘
• ex) n개의 숫자가 저장되어 있는 배열을 , 오름차순의 조건으로 작성하여 입력하면 오름차순으로 정렬된 배열을 출력으로 구할 수 있다.
• 정렬 알고리즘의 종류 : 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬

깊이 우선 탐색 (DFS , Depth-First Search)

• 그래프 탐색에 사용되는 알고리즘, DFS는 깊이를 우선으로 탐색하여 더 이상 탐색할 노드가 없을떄 까지 깊게 들어가는 알고리즘

너비 우선 탐색 (BFS, BreadTh-First Search)

• 너비를 우선을 ㅗ탐색하여 같은 레벨에 있는 노드들을 모두 탐색한 후에 다음 레벨로 넘어가는 알고리즘

다이나믹 프로그래밍 (Dynamic Programming)

• 큰 문제를 작은 부분 문제로 나누어 푸는 최적화 알고리즘
• 중복되는 문제를 효율적으로 해결하여 전체 문제를 해결하는 방식으로 사용
• 시간복잡도를 줄이고 효율적인 해결 책 강구

최단 경로 알고리즘 (Shortest Path Algorithms)

• 노드 간 가장 짧은 경로를 찾는 알고리즘으로, 다익스트라 알고리즘, 벨만-포드 알고리즘이 대표적

그리디 알고리즘 (탐욕법 , Greddy Algorithm)

• 각 단계에서 최적의 선택을 하며, 전체적으로 최적의 해를 구하는 알고리즘
• 매순간 이익이 가장 큰 선택을 하지만 최적의 결과를 보장하지는 않음

이항 계수 (Binomial Coefficient )

• 조합론에서 많이 사용되는 계수로, 주어진 크기의 집합에서 특정 개수의 원소를 선택하는 경우의 수를 나타냄
• 동적 프로그래밍이나 파스칼의 삼각형을 이용한 알고리즘에서 사용

데이터 베이스와 ORM

데이터 베이스 와 ORM

• Object Relational Mapping 의 약자로 객체와 데이터베이스의 관계를 매핑해주는 도구
• 객체와 데이터베이스의 관계를 매핑해주는 도구
• 프로그래밍 언어의 객체와 관계형 데이터베이스의 데이터를 자동으로 매핑해주는 도구
• 프로그래밍 언어의 객체와 관계형 데이터베이스 사이의 중계자 역할
• 객체 지향 프로그래밍은 클래스를 이용하고 괸계형 데이터베이스는 테이블을 이용하는데 객체 모델과 관계형 모델간의 불일치를 해소하기 위해 사용
• ORM을 사용해 데이터베이스 접근을 프로그래밍 언어의 관점에서 맞출 수 있음
• SQL이 아닌 메서드로 데이터를 조작할 수 있음
• 프로그래머가 객체 모델로 프로그래밍 하는것에 더 집중할 수 있게 도와줌
• SQL의 절차적이고 순차적인 접근이 아닌 객체 지향적인 접근으로 생산성 증가
• 대표적인 ORM : sequelize, Type ORM, Prima등이 있음

예제

SQL

INSERT INTO users (id, name, age) VALUES (1, 'John', 30);

Sequelize

await User.create({ id: 1, name: 'John', age: 30 });

Type ORM

  const user = new User();
  user.id = 1;
  user.name = 'John';
  user.age = 30;

  await connection.manager.save(user);

Prisma

(async () => {
  await prisma.user.create({
    data: {
      id: 1,
      name: 'John',
      age: 30
    }
  });
})();