The Big Picture

해싱(Hashing) - key-value를 해시 함수를 이용하여 매핑하는 것 - 빠르게 요소에 접근할 수 있다. 해시 테이블(Hash Table) - 해시 함수를 이용하여 변환한 값들을 index 삼아 key-value 쌍으로 저장한 자료 구조 - 저장/검색을 하는 데 있어 복잡도가 평균적으로 O(1)로, 가장 낮다. - 매우 빠른 응답 - 파이썬의 Dictionary, 루비의 Hash, 자바의 Map이 이에 해당한다. - IP와 이에 해당하는 컴퓨터 이름, 주민등록 시스템 등 다양한 방식으로 응용 가능하다. - 최소 원소를 찾는 등의 작업은 지원 X Load factor ⍺ - 해시 테이블의 검색 효율과 밀접한 관련 - 해시 테이블 전체에서 얼마나 원소가 차 있는지를 나타내는 수치 - n개의 원소가 ..

- 자가 균형 이진 트리(self-balancing binary tree) 연관 배열이나 집합(set)을 내부적으로 구현할 수 있다. Red-Black Tree의 특성(Properties) 1. 노드는 레드 혹은 블랙 중의 하나이다. 2. 루트 노드는 블랙이다. 3. 모든 리프 노드들(NIL)은 블랙이다. 4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다) 5. 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. 4번 특성에 의하면 - 블랙 노드는 연속해서 나타나도 된다. - 루트 노드부터 가장 먼 리프노드 경로까지의..

이진 힙(Binary Heap) = heap - 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리(complete binary tree)를 기본으로 한 자료구조 - 시간 복잡도는 O(log n) 이다. 이진 힙 특징 - 완전하다 : 트리가 왼쪽에서 오른쪽으로 다 채워짐 = 완전 이진 트리(Complete Binary Tree) https://garysummers.tistory.com/124 Tree - 비선형 자료구조 - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조 - 가지를 늘려가며 표현하게 된다. Tree의 구조 - 노드(node) : 2, 7, 5, 2, 6, 5, 11, 4, 9와 같은 요소들 - 간선(edge) : 노.. garysum..

- 비선형 자료구조 - 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조 - 가지를 늘려가며 표현하게 된다. Tree의 구조 - 노드(node) : 2, 7, 5, 2, 6, 5, 11, 4, 9와 같은 요소들 - 간선(edge) : 노드와 노드를 연결하는 연결선 - 루트 노드(root) : 트리 구조에서 최상위에 존재하는 노드. 2와 같음 - 단말 노드, 잎사귀 노드(terminal node, leaf node) : 아래로 또 다른 노드가 연결되어 있지 않은 5, 11, 4와 같은 노드 - 내부 노드(internal node) : 단말 노드를 제외한 모든 노드 - 레벨(level) : 각 층별 위치 - 높이(height) : 트리의 최고 레벨, 이 트리의 높이는 3이다. ..

Array - 메모리 위치가 연속적이다 - 위치 계산이 쉽고 인덱스값으로 쉽게 요소에 접근 가능하다. 장점 - 같은 이름으로 비슷한 타입의 데이터를 여러개 저장할 수 있다. - 요소에 랜덤하게 엑세스 가능하다. = 원소의 인덱스 값을 알고 있으면 바로 접근 가능 => O(1) - 사이즈가 고정되어있고 메모리에 연속적으로 저장되기 때문에 메모리 오버플로우가 발생하지 않는다. - 어떤 데이터든 고정된 사이즈로 저장하기 좋다 - 연속된 메모리 위치에 저장되기 때문에 반복적인 작업을 하기 쉽고 인덱스를 알고 있다면 접근하는데 유닛 타임만 필요하다(연속적으로 접근할 필요가 없다는 의미) 단점 - static하기 때문에 한번 사이즈가 정해지면 고칠 수 없다. - 연속적인 메모리 위치에 저장되기 때문에 삽입/삭제가 ..

Stack- LIFO 방식(Last-In, First-Out)- 후입선출방식- 나중에 들어온 것이 먼저 나오게 된다. Stack ADT void Init(Stack * stack);- 스택의 초기화- 스택 생성 후 제일 먼저 호출되어야 하는 함수 void IsEmpty(Stack * stack);- 스택이 빈 경우 True(1), 그렇지 않은 경우 False(0)을 반환 void Push(Stack * stack, Data data);- 스택에 데이터를 저장- 매개변수 data로 전달된 값 저장 Data Pop(Stack * stack)- 마지막에 지정된 요소를 삭제- 삭제된 데이터는 반환됨- 본 함수의 호출을 위해서는 데이터가 하나 이상이 존재함을 보장해야 함 Data Top(Stack * stack)..

Git 무료의 분산 버전 컨트롤 시스템 오픈 소스 분산 버전 컨트롤 시스템(Distributed Version Control System)이란? 클라이언트가 저장소를 통째로 미러링 할 수 있고, 한 서버가 죽더라도 백업할 수 있다. Git, Mercurial, Bazzar 등이 있다. Git에서의 Commit 커밋을 할 때마다 깃은 내 모든 파일들의 스냅샷을 저장한다. 파일 여러개를 수정할 수도 있다. Git은 한마디로 스냅샷의 흐름이라고 볼 수 있다. 파일이 변경되지 않았다면, 깃은 이를 또다시 저장하지 않는다. * Git은 pull을 제외한 모든 동작이 locally 가능하다. 파일의 세 가지 상태 Committed 데이터가 안전하게 로컬 데이터베이스에 저장된 상태 Modified 파일이 변경되었지만..

MVC(모델-뷰-컨트롤러) 디자인 패턴사용자 인터페이스, 데이터 및 논리 제어를 구현하는데 널리 사용되는 소프트웨어 디자인 패턴애플리케이션을 세가지의 역할로 구분한 개발 방법론이외에는 MVVM (모델-뷰-뷰모델), MVP (모델-뷰-프리젠터), MVW (모델-뷰-왓에버)가 있다.소프트웨어의 비즈니스 로직과 화면을 구분하는데 중점을 두고 있다.모델데이터와 비즈니스 로직을 관리상태에 변화가 있을 때 컨트롤러와 뷰에 이를 통보한다. 이와 같은 통보를 통해서 뷰는 최신의 결과를 보여줄 수 있고, 컨트롤러는 모델의 변화에 따른 적용 가능한 명령을 추가·제거·수정할 수 있다. 뷰레이아웃과 화면을 처리사용자가 볼 결과물을 생성하기 위해 모델로부터 정보를 얻어 온다.컨트롤러명령을 모델과 뷰 부분으로 라우팅합니다.모델에..

함수 프로그래밍 수학 함수와 같은 원리의 함수들로 프로그램을 구성하는 기법 코드를 간결하게 작성할 수 있어 개발 시간이 단축된다. 함수는 부작용(Side Effects)을 발생시키지 않고 단지 입력을 받아들여 출력을 구한다. 함수형 프로그래밍 언어의 특징 불변성(Immutability) 변경 가능한 상태를 최대한 제거하려고 한다. 순수 함수를 지향하는 프로그래밍 언어이다. 즉, 부작용이 없는 함수이다. * 순수 함수 : 내부 상태를 갖지 않아, 같은 입력에 대해 항상 같은 출력이 보장되는 함수이다. - 프로그램의 검증이 쉽다 오직 입력 값의 영향만 받기 때문에 테스트 코드를 작성하기 쉽고, 개발자가 예측하지 못하는 시점에 변경될 수 있는 내부 상태가 없기 때문에 프로그램이 예측 가능해진다. - 최적화가 ..

TDD ; Test-Driven Development = 테스트 먼저 짠다 매우 짧은 개발 사이클을 반복하는 것에 기반한 소프트웨어 개발 프로세스 - 요구사항(Requirements)이 매우 구체적인 테스트 케이스가 된다. - 그래서 코드가 개선되면 테스트를 pass하게 된다. TDD 사이클 1. 테스트를 추가한다. 2. 모든 테스트를 Run하고 새 test가 fail하는지 본다. 3. 코드를 작성한다. 4. 모든 테스트를 Run한다. 5. 코드를 Refactoring 한다. - 함수마다 테스트코드를 작성하게 된다. - 테스트가 하나 추가될 때마다 전체 코드를 한번 더 테스트해야 한다. * Test Coverage : 내 코드에 테스트를 Run했을 때 성공한 퍼센트(%) * Test Lag : 테스트 코..