전체 글 (115) 썸네일형 리스트형 해시 테이블(Hash Table) - 해시 테이블 (Hash Table) Key 값을 해시 함수를 통해 변환한 값(해시 값)을 index로 삼아 Value 데이터를 저장하는 자료 구조이다. 내부적으로 배열을 사용하여 데이터를 저장하고, 고유의 index로 접근하기 때문에 빠른 검색 속도(충돌이 일어나지 않는 경우에 O(1))를 갖는다. 대표적인 해시 함수로는 Key 값을 테이블 크기로 나누어 계산(ex. 해시 값 = Key % 테이블 크기)하는 Division Method과 문자열을 키로 사용하는 해시 테이블에 잘 어울리는 알고리즘으로 Key 값을 ASCII 코드로 바꾸고 값을 합한 데이터를 이용하는 Digit Folding 등이 있다. 하지만 문제는 아무리 좋은 해시 함수를 이용한다해도 비둘기집의 원리에 의해 충돌이 발생할 확률이 있다.. 스택(Stack), 큐(Queue) 스택(Stack)과 큐(Queue) 모두 선형 자료 구조이며, 추상 데이터 타입(ADT)이다. - ADT : 자료 구조의 방법이 코드로 정의 된 것이 아닌 그 구조의 행동 양식만 정의된 것 (일종의 규칙) - 스택 (Stack) LIFO (Last In First Out) 즉, 나중에 들어간 원소가 먼저 나온다. - 사용 사례 재귀 알고리즘, DFS, 실행 취소, 웹 브라우저 뒤로가기 등 - 큐 (Queue) FIFO (First In First Out) 즉, 먼저 들어간 원소가 먼저 나온다. - 사용 사례 어떠한 작업 및 데이터를 순서대로 실행 및 대시킬 때 사용 서로 다른 쓰레드 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용함. 배열(Array), 연결 리스트(Linked List) - 배열 (Array) 물리적 순서와 논리적 순서가 같은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음 따라서 Index로 해당 원소에 접근할 수 있다. 그렇기 때문에 원소의 Index를 알고 있으면 시간복잡도 O(1)에 해당 원소로 접근할 수 있다. 하지만 삭제 또는 삽입의 과정에서는 해당 원소에 접근하여 작업을 완료한 뒤, Shift를 해줘야 하는 상황이 발생할 수 있기 때문에 Shift하는 비용이 발생하고 이 경우의 시간 복잡도는 O(n)이 된다. 배열의 크기가 대부분 정적으로 결정된다. 배열은 순차적인 데이터를 저장하며 값보다는 순서가 중요하거나 다차원 데이터를 다룰 때, 어떤 특정 요소를 빠르게 읽어야할 때, 데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때 사용.. JavaScript - 정의 : 웹페이지에 생동감을 불어 넣기 위해 만들어진 프로그래밍 언어. 객체 기반의 스크립트 언어. - 특징 1. 인터프리터 언어지만, 실행하는 플랫폼에 따라 인터프리팅과 컴파일이 혼합되어 사용하여 성능을 크게 향상 시킴 자바스크립트 엔진 내부에서 실행 중 컴파일이 필요한 경우 내부에서 컴파일을 한다. 2. 동적 타입 언어 : 변수 타입이 없으며, 프로그램 실행 도중에도 변수 타입이 변경될 수 있음 3. 프로토타입 기반의 객체 지향 언어 : 클래스 기반(상속, 캡슐화 등)의 언어가 아닌 프로토타입 기반의 객체지향 언어 - 프로토타입 : 어떤 객체의 원본 / 원형이 되는 객체 4. 일급 객체 함수 : 고차 함수를 구현할 수 있어 함수형 프로그래밍이 가능 - 일급 객체 조건 1. 무명의 리터럴로 생성할 .. Flux 패턴 - Flux 패턴이란? MVC 패턴의 단점을 보완하기 위해 페이스북에서 만든 단방향 데이터 흐름을 위한 패턴 - 왜 사용할까? MVC 패턴에는 Model과 View가 양방향 패턴에서 나오는 의존성을 가진다는 특성이 있다. 이는 복잡한 Application을 서비스하게 된다면 새로운 기능이 추가 될 때마다 시스템의 복잡도가 높아지고, 예측 불가능한 코드를 만들게 되며, 그렇게 된다면 예측 못할 버그들이 쏟아질 가능성이 높아진다. * 실제로 페이스북이 가졌던 문제점 중 하나가 알림 버그였다. 페이스북에 로그인 했을 때 새로운 메시지 아이콘 알림이 떠 있지만, 실제로는 아무런 메시지가 없었다. 이를 단방향 데이터 흐름인 Flux 패턴으로 해결 하였다고 한다. - 용어 정리 1. Action : 정확히 말하면 .. 레드 블랙 트리(Red-Black Tree) Red-Black Tree : 기존 이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 즉 , 트리의 높이에 비례한 만큼의 시간이 걸린다. 원소들이 트리에 잘 분산 되어 있다면 별 문제가 없지만, 한 쪽으로 치우친 트리 (skewed tree)의 경우에는 높이가 n이 되어 시간 복잡도가 O(n)이 된다. 이러한 이진 탐색 트리에 색(Red, Black)이라는 속성을 추가하여 최악의 상황이라도 시간 복잡도 O(log n)을 유지한다. - 조건 1. 모든 node는 Red 혹은 Black의 색을 갖는다. 2. root node는 항상 Black이다. 3. NIL node(= leaf node)는 Black이다. 4. Red node의 자식 node는 항상 Black node이다. (= Re.. TCP / IP 4계층(4 Layer Internet Model) 계층 모형 : TCP / IP 모형은 현재 인터넷에서 정보를 주고 받는데 쓰이는 프로토콜의 모음으로 각 계층은 담당하는 위치마다 처리 역할을 구분하여 진행함으로써 서로의 간섭을 최소화하여 사용을 높이고, 유지 보수가 편리하다. 호환성 보장으로 비용 절감, 계층 별로 문제 확인이 가능하여 쉽게 문제 해결이 가능, 다른 계층끼리의 전달 과정을 알 필요가 없어 Data의 캡슐화와 은닉이 가능. L4 응용 계층 0. Data 단위 : Data / Message 1. 사용자와 가장 가까운 계층으로 사용자가 Application과 소통할 수 있게 해줌. 2. 응용프로그램들이 Data를 교환하기 위해 사용되는 프로토콜 3. 사용자 응용프로그램 인터페이스를 담당 Ex) FTP, HTTP, SSH, DNS, SMTP 등.. 뮤텍스(Mutex)와 세마포어(Semaphore)의 정의 - 임계 구역 (Critical Section) : 여러 Process or Thread가 공유 자원에 접근하는 부분. 그렇기 때문에 이 임계 구역에 여러 Process나 Thread가 한번에 접근할 수 없도록 관리를 해줘야 한다. - 뮤텍스 (Mutex) : 공유 자원에 대한 접근을 동기화하기 위해 사용되는 상호배제 기술. Locking 메커니즘으로 오직 하나의 Thread만이 동일한 시점에 Lock을 얻어 임계 영역에 들어올 수 있다. 그리고 오직 그 Thread만이 Lock을 반환하여 임계 영역에서 나갈 때(Unlock) 다른 Thread가 접근할 수 있다. 뮤텍스는 오직 1개의 Thread만 접근할 수 있기 때문에 이진 세마포어와 같은 개념이다. - 세마포어 (Semaphore) : 공유 자원에 .. 이전 1 ··· 10 11 12 13 14 15 다음
