suyeonme

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 커맨드패턴(Command Pattern)이란? 요청 내역을 객체로 캡슐화해서 객체를 서로 다른 요청 내역에 따라 매개변수화할 수 있다. 이러한 요청을 큐에 저장하거나 로그로 기록하거나 작업 취소 기능을 사용할 수 있다. 커맨드 패턴 활용 예시 1. 스케줄러, 스레드 풀, 작업 큐와 같은 작업에 사용할 수 있다. 작업 큐를 예시로 들면, 큐 한쪽 끝은 커맨드를 추가할 수 있고, 다른 쪽 끝에는 커맨드를 처리하는 스레드들이 대기하고 있다. 각 스레드는 우선 execute()를 호출하고 호출이 완료되면 커맨드 객체를 버리고 새로운 커맨드 객체를 가져온다. 작업 큐 클래스는 계산 작업을 하는 객체들과 완전히 분리돠어 있다. 큐에 커맨드 패턴을 구현하는 객..

해시법(Hashing)이란? 데이터를 저장할 위치(index)를 간단한 연산으로 구하여 검색, 추가, 삭제를 효율적으로 수행한다. 해시 함수(Hash Function) 키값을 해시값(hash value)로 변환하는 과정을 해시 함수라고 한다. 충돌을 피하려면 해시 함수는 해시 테이블 크기 이하의 정수를 한쪽으로 치우치치 않도록 고르게 만들어야한다. 해시 테이블 크기는 소수(prime number)가 좋다고 알려져있다. 해시 테이블을 만드는데 사용되는 대표적인 해시 함수 목록이다. 키값이 정수(integer)인지에 따라서 해시 함수가 달라진다. Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터로 해시를 생성하는 방법 Multiplication Method: 숫자로 ..

트리(Tree)란? 데이터 사이의 계층 관계를 나타내는 자료구조이다. 트리를 구성하는 요소는 노드(node)와 가지(edge)이다. 각각의 노드는 가지로 연결되어있다. 그래프(Graph)의 여러 구조 중 무방향 그래프의 한 구조이다. 하나의 데이터 뒤에 여러개의 데이터가 존재할 수 있는 비선형 구조이다. (선형 구조: 데이터를 순차적으로 나열) 트리 구조는 계층적으로 표현이 되고, 아래로만 뻗어나가기 때문에 사이클(cycle)이 없다. 트리를 사용한 대표적인 예시로, 파일 시스템(File System)이 있다. 파일 시스템에서 폴더는 루트 폴더에서 시작되어 가지를 뻗어나가는 모양을 한다. 트리 관련 용어 용어 설명 루트(root) 트리의 가장 윗부분에 위치하는 노드로, 하나의 트리에는 하나의 루트가 존재..

리스트(List)란? 데이터를 순서대로 나열한 자료구조이다. 선형 구조를 갖는 리스트에는 선형 리스트(linear list)와 연결 리스트(linked list)가 있다. 리스트에 있는 개별 요소를 노드(node)라고 한다. 노드의 구성 요소는 데이터와 다음 노드를 가리키는 포인터이다. 선형 리스트(Linear List) 데이터가 배열처럼 연속하는 메모리 공간에 저장되어 순서를 갖는다. 연결 리스트(Linked List) 데이터가 메모리 공간에 연속적으로 저장되어있지 않더라도 각각의 데이터안에 다음 데이터에 대한 정보를 갖고 있어 서로 연결(linked)된다. 연결 리스트의 구성 요소 머리 노드(head node): 리스트의 처음에 있는 노드 꼬리 노드(tail node): 리스트의 끝에 있는 노드 앞쪽..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 싱글톤 패턴(Singleton Pattern)이란? 클래스 인스턴스를 하나만 만들고, 그 인스턴스로의 전역 접근을 제공하는 디자인 패턴이다. 스레드 풀, 캐시, 대화상자, 사용자 설정, 레지스트리 설정을 처리하는 객체, 로그 기록용 객체, 디바이스 드라이버등에 주로 사용된다. 1.1 전역 변수 vs 싱글톤 전역 변수에 객체를 대입하면, 애플리케이션이 시작될 때 객체가 생성된다. 만약 객체가 자원을 많이 사용할 경우, 그리고 해당 객체가 사용되지 않으면 불필요하게 자원을 낭비할 수 있다. 2. 멀티스레딩을 고려하지 않은 싱글톤 간단하지만, 멀티스레드 환경에서는 문제가 발생할 수 있다. 생성자를 private으로 선언했으므로 Singleton에서만 클..

커밋 메세지를 여러줄로 작성하고 싶은 경우, 1. “를 열고 메세지를 작성 git commit -m "title body footer" 결과) title body footer 2. 여러개의 -m 태그 사용 -m 태그마다 paragraphs를 생성하므로 blank line이 생긴다. git commit -m "title" -m "body" -m "footer" 결과) title body footer

1. KMP(Knuth–Morris–Pratt) 알고리즘이란? 텍스트와 패턴 사이에 겹치는 부분을 찾아내 검사를 다시 시작할 위치를 구하여 패턴을 한번에 많이 옮기는 알고리즘이다. "몇번째 문자부터 다시 검색할지"에 대한 값을 미리 표로 만들어 검사를 시작할 위치를 구한다. 즉 패턴과 텍스트가 불일치할 경우, 그 전에 검사했던 텍스트의 문자를 표에 작성하여 불필요한 검사는 생략한다. 시간 복잡도는 O(n)이다. 2. 동작 방식 skip[]은 패턴에서 접두사(prefix)와 접미사(suffix)가 일치하는 최대 길이를 저장하는 배열이다. 접두사와 접미사가 일치하지 않으면, 접미사를 가리키는 인덱스를 1 증가한다. 접두사와 접미사가 일치하면, 접두사를 가리키는 인덱스와 접미사를 가리키는 인덱스를 1 증가한다..

1. 보이어-무어(Boyer-Moore) 알고리즘이란? 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 알고리즘이다. 시간 복잡도는 O(n/m)으로 매우 빠르다.(n은 텍스트의 길이, m은 패턴의 길이) 2. 동작 방식 문자열 탐색은 패턴의 맨 마지막 글자부터 시작한다. 2.1 Bad Character 패턴의 현재 문자와 일치하지 않는 텍스트의 문자 (패턴: 찾을 문자열, 텍스트: 탐색을 수행할 문자열) Bad Character가 패턴에 존재하는 경우와 패턴에 존재하지 않는 경우를 나누어 접근한다. Bad Character가 패턴에 존재하는 경우 인덱스 2에서 불일치 발생 (C는 bad character) C는 패턴에 존재한다..