본문 바로가기

CS 과목(CS科目）

ADT 관점에서의 Map 개념 && Map의 구현체인 HashTable의 동작 원리 key 중복 불가 위와 같이, 데이터의 연속이므로, 위와 같은 자료 구조를 연관 배열(Associative Array, Map, Dictionary)라 고부를 수가 있다.( 파이썬에서는 Dictionary라는 용어를 쓰는 것 같음) Map 구현체 1. Hash Table : [배열, 해쉬함수]를 사용하여 Map 구현! ( 일반적으로, 상수 시간으로 데이터에 접근하기에 데이터 접근 속도 빠름) 2. Tree - based : 트리 기반의 Map(대표적으로 [레드 블랙 트리].... 이번 시간에는 Hash Table에 대해 알아 보며, 트리 기반은 레드 블랙 트리 시간에 다시 살펴 볼 것이다) Map 구현체 - Hash Table 먼저 아래의 것을 까먹지 말고 숙지하고 가자! Hash Function은 In.. 더보기
Priority Queue와 Heap의 차이점 먼저 ADT(Abstract Data Type)에 대해서 모르고 있다면, ADT가 무엇인지를 먼저 공부하고 와야 한다. (급하신 분은, 걍 "ADT란 해당 자료 구조에서 구현되어야할 기능들의 모음"이라고 생각하면 된다. 실제로 구현돼 있는 것은 아니므로 오해 금지) Priory Queue는 ADT이다. JAVA로 치면, 인터페이스인 것이다. Heap(최대힙, 최소힙)는 Prioriry Queue ADT의 구현체이다. Prioriry Queue ADT의 구현체는 Heap 이외에도 여러 구현체가 있지만, Heap이 가장 성능이 좋기 때문에 Prioriry Queue == Heap 이라고 생각하기 쉽다. 그러나 엄밀히 말하면 Heap은 Priory Queue의 구현체 중 하나에 불과하다. 더보기
DB Index에서 사용되는 B-Tree (데이터 삭제) 데이터 삭제는 아래 2가지만을 신경쓰면 된다. 1. 항상 leaf 노드에서 삭제가 발생.( internal node의 삭제 시에도 항상 leaf 노드가 삭제된다. 한참 아래에 internal node 삭제에 대한 설명이 있음) 2. 삭제 후, 해당 노드의 key수가 최소 key 수 보다 적어졌으면 재조정한다. 2-a) 형제 노드들 중, key의 수가 최소 key 개수보다 많으면 그 key를 가져와서 재조정한다. 2-a-1) 왼쪽 형제가 더 여유가 있으면...(원래 일반적으로 왼쪽 형제의 지원을 우선적으로 받는다.) ->동생의 가장 큰 KEY를 부모 노드에게 올려 주고 -> 부모 노드에 있던 KEY를 나에게 내려 준다, 2-b) 형제 노드의 도움으로도 해결이 되지 않으면, 그 다음에는 부모 노드의 key값.. 더보기
DB Index에서 사용되는 B tree(데이터 삽입) 아래에 이진 탐색 트리에 대한 간단한 개요가 있다. 이진 탐색 트리는 최대 2 개의 자식 노드를 가질 수가 있다. 그러나 만약 자식 노드의 개수를 3개로 늘리면서, 이진 탐색 트리와 같은 동작 방식으로 데이터를 삽입,조희,삭제를 해주기 위해서는 어떻게 하면 될까??? 왼쪽의 BST의 왼쪽 서브 트리의 모든 노드는 50보다 작고, 오른쪽 서브 트리의 모든 노드는 50보다 크다. 오른쪽의 자녀 노드가 3개인 경우에도 이와 같은 규칙성을 가지게 해보자. 일단 자식 노드가 3개이므로, 각 노드의 부모 노드와의 대소관계는 BST가 2개였던 거와는 달리, 3개가 된다. 즉, 왼쪽 자식 노드부터 아래와 같이 정의가 된다. ( 참고로, 이때에는 부모 노드가 2개 있어야 한다 ) 1] SubTree < k1 : 왼쪽 서.. 더보기
28. NoSQL( MongoDB, Redis, etc ) RDBMS의 단점 1. Column을 추가할 때마다, 스키마를 변경해야 한다( 경직된 스키마 ) 2. 너무 많은 JOIN 연산을 하게 된다.( DB 서버의 CPU,메모리 과부하 ) 데이터가 중복으로 저장되는 것을 막기 위하여 3NF, BCNF를 통해 아래와 같이 원본 테이블을 분할을 하였다. 그런데 만약 원본 테이블의 tuple을 조회하고 싶을 때, 위 4개의 table들에 대해 JOIN 연산을 해야 한다. 이렇게 되면, DB 서버는 JOIN 연산을 실행하기 위하여, CPU와 메모리를 상당 부분 사용하게 될 것이다. 3번째 단점을 살펴보기에 앞서 , scale - up과 scale out에 대한 알고 가자. scale - up : 컴퓨터의 cpu, 메모리 등을 더 좋은 성능의 것으로 바꾸어서 퍼포먼스를 .. 더보기
27.DBCP(DB Connection Pool) 보통의 경우, Logic 서버와 DB 서버의 통신은 TCP 기반으로 이루어 진다. 이 2 개의 서버 사이에서 쿼리를 던지고 전, 그리고 쿼리에 대해 응답을 한 후에는 각각 Connection(3-way)을 미리 맺고 쿼리 수행이 다 끝나게 되면, 그 Connection을 닫아 준다(4-way). 이러한 과정은 높은 데이터 신뢰성을 보장하는 반면에, 시간 비용이 많이 든다는 단점이 존재한다. ( Logic 서버는 계속해서 쿼리를 요청하게 될 것이고, API 마다 한 번의 쿼리가 아니라, 여러 번의 쿼리를 날리게 되는 경우 가 있다. 이러한 경우 시간 비용은 매우 매우 큰 단점이다.) 위와 같은 단점을 해결하기 위해 나온 것이 DBCP이다. DBCP의 동작 방식 Logic 서버에서 API 요청을 하기 이전에.. 더보기
Holder 기법!!!! 동기화(Synchronization)을 위하여, 우리는 데이터를 매개변수로 일일이 넘겨 주곤 하였다. 그러나 이와 같은 방식은 코드를 번잡하게 만들며, 개발자들의 실수를 유도한다. 그래서, Holder 기법을 이용하는 것이 현명하다. 예를 들어, TraceId를 일일이 메서드에 매개변수로 전달시키는 것이 아니라 하나의 클래스에 TraceId traceHolder라는 필드를 선언을 해 주고, 이 필드에 TraceId 객체를 저장하여, 필요할 때마다 꺼내서 쓰게 하면 된다. ( advanced 파일의 FiledLog.java 코드 참고!! ) 더보기
Deque(덱) 1. Deque의 개념과 구조 Deque(데크)는 double-ended-queue의 줄임말로, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조이다. 아래 그림과 같이, 양방향에서 엘리먼트를 추가, 삭제할 수 있는 양방향 큐라고 생각하면 된다. 2. Deque에 존재하는 메서드 종류 Python에서 deque는 collections라는 모듈안에 deque클래스로 내장되어있다. 가장 기본적인 append() 메서드를 수행하면 다음과 같다. from collections import deque deq = deque(['a', 'b', 'c']) deq.append('d') print(deq) # deque(['a', 'b', 'c', 'd']) 기본 append()를 해주면 위의 예제와 같이 가장 .. 더보기

티스토리툴바