세상을 바꾸는 개발자

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다. 원하는 원소를 찾기 위해 자주 이용되는 이진 검색 트리 (STL set, map) 등에서는 원소를 찾는데 **O(logN)**의 시간이 걸리게 된다. 하지만, 문자열의 경우 두 문자열을 비교하기 위해서는 문자열의 길이만큼의 시간이 걸리기 때문에 원하는 문자열을 찾기 위해서는 O(MlogN)의 시간이 걸리게 된다. 따라서 여러 번 이 작업을 수행한다면 시간이 오래 걸릴 것이다. 이 단점을 해결하기 위한 문자열 특화 자료구조가 트라이(Trie)이다. 쉽게 말해, "문자열을 빠르게 탐색할 수 있는 자료구조"이다. 트라이(Trie) 자료구조의 장/단점 트라이의 장점은 앞에서도 언급했듯이 당연히 문자열을 빠르게 찾을 수 있다는 점이다. 더불어, ..

Map은 Key와 Value 한쌍으로 이루어진 자료형이다. Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해 Value를 얻는다. 값(Value)은 중복될 수 있지만, **Key는 고유한 값(Unique)**을 가져야 한다. Map은 저장 순서를 유지할 필요가 없고, Key를 통해 Value를 얻어내기 때문에 Key는 중복을 허용하지 않는다. 구조도 HashMap, HashTable 키와 값(key, value)이 하나의 쌍을 이루는 데이터 구조이다. 즉, 키와 배열의 인덱스를 이용하여 키를 저장하는 자료구조이다. HashTable은 키를 해시함수(Hash Function)로 계산하여 그 값을 배열의 인덱스로 사용한다. 이때, 해시 함수에 의해 반환된 데이터의 고유 숫자값을..

배열 (Array) 장점 바로 만들어서 활용하기가 쉽다 더 복잡한 자료 구조의 기초가 될 수 있다 원하는 데이터를 효율적으로 탐색/가져올 수 있다 정렬에 용이하다 단점 데이터를 저장 할 수 있는 메모리 크기가 고정되어 있다 데이터 추가 / 삭제 방법이 비효율적이다 구조 재구성 시 정렬하는 방식이 비효율적이다 사용 엑셀의 스프레드시트 처럼 직사각형 테이블, 수학적 벡터 (vector) 및 행렬 (matrix)를 구현하는 데 사용된다 다른 데이터 구조에서 사용된다 스택 (Stack) 장점 동적인 메모리 크기 데이터를 받는 순서대로 정렬된다 빠른 런타임 (runtime) 단점 가장 최신 요소만 가져온다 한번에 하나의 데이터만 처리 가능하다 사용 가장 마지막으로 입력된 것을 순차적으로 바로 처리하고 싶을 때 브..

array나 list 처럼 순열 자료구조 (collection) 이지만 set은 순서라는 개념이 존재하지 않는다. Set은 집합이라는 의미를 가진다. Set의 특징 데이터를 비순차적(unordered)으로 저장할 수 있는 순열 자료구조 (collection). 집합의 개념과 같다고 생각하면 된다.(집합 역시 {1, 9, 6, 4}처럼 중복과 순서가 없다.) 삽입(insertion) 순서대로 저장되지 않는다. 즉 특정한 순서를 기대할 수 없는 자료구조. 수정 가능하다(mutable). 동일한 값을 여러번 삽입 불가능하다. 동일한 값이 여러번 삽입 되면 하나의 값만 저장된다. Fast Lookup이 필요할때 주로 쓰인다. Set이라는 인터페이스를 통해 자바에서는 3가지의 Set이 있다. Hash 알고리즘을 ..

자료구조의 인터페이스 Iterable 함수 hasNext List 란 ArrayList, LinkedList 의 구현체이다. 물론 Vector, Stack은 지금은 사용하지않고 호환성을 위해 남아있는 Class 이다. 리스트는 순서가 있는 엘리먼트의 모임으로 배열과는 다르게 빈 엘리먼트는 절대 허용하지 않는다. 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취함 리스트에서 인덱스는 몇 번째 데이터인가 정도(순서)의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자) 빈 엘리먼트는 허용하지 않는다. => java에서는 허용하는 경우가 있음 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash h..

배열은 메모리 상에 데이터(원소)를 연속하게 배치한 자료구조 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 배열은 선언할 때 크기를 정하면, 그 크기로 고정이 된다. 선언된 값은 다시 배열을 선언하지 않으면 변경할 수 없다. 배열의 주소를 살펴보면, 한 칸마다 배열의 자료형의 크기를 가지고 있따. 배열의 자료형이 int라면, 배열 한 칸의 크기는 int(4byte)가 되는 것이다. 배열은 인덱스를 통해서 배열에 있는 요소에 접근할 수 있다. 배열의 특징 추가적으로 소모되는 메모리 양(=overhead)가 거의 없다 Cache hit rate가 높다. cache hit ratio: 적중률 = (캐시히트 횟수)/(전체 참조횟수) cache hit: 참조하려는 데이터가 캐시에 존재할 떄 캐시 히트 ..

비관리 의존성에만 목을 사용 시스템의 끝에서 비관리 의존성과 상호 작용을 검증 목을 스파이로 대체하라(스파이: 직접 작성한 목) 시스템 끝에 있는 클래스의 경우 스파이가 목보다 낫다 통합테스트에서만 목을 사용, 단위테스트에서는 사용x 목은 통합테스트를 위한 것(비즈니스 로직과 오케스트레이션의 분리) 도메인 모델에 대한 테스트는 단위테스트 범주, 컨트롤러 테스트는 통합테스트 통합테스트에서 컨트롤러를 테스트 할때만 목을 적용 테스트당 목이 하나일 필요x 항상 목의 호출 수 확인하기 예상하지 못한 호출 확인 혼자 단위테스트라는 책을 읽으면서 생각에 흐름대로 적은 글입니다. 기록용입니다! 참고한 책은 단위 테스트라는 책입니다. ( http://www.yes24.com/Product/Goods/104084175 )

통합테스트란? 단위테스트의 3가지 요구사항 단일 동작단위 검증 빠르게 수행 다른 테스트와 별도로 처리 → 이 세가지 중에 하나도 충족을 못할 시 통합테스트(단위테스트가 아닌 모든테스트가 통합테스트) 단위테스트와 통합테스트 단위테스트와 통합테스트간에 균형을 유지하는 것이 중요 단위테스트로 가능한 한 많이 비즈니스 시나리오의 예외 상황을 확인하고 통합테스트는 주요 흐름과 단위테스트가 다루지 못하는 기타 예외사항을 다뤄야한다.(모든 프로세스의 외부의존성을 거치는 것) 빠른 실패원칙 : 예기치 않은 오류가 발생하자마자 현재 연산을 중단 프로세스 외부 의존성의 2가지 유형 관리의존성 : 애플리케이션을 통해서만 접근가능 ex) 데이터베이스 등 비관리 의존성 : 외부에서 상호작용을 볼 수 있음 ex) SMTP, 메세..