suyeonme

커밋 메세지를 여러줄로 작성하고 싶은 경우, 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는 패턴에 존재한다..

1. 브루트-포스법(Brute force method)이란? 선형 검색을 확장한 단순한 알고리즘이다. 효율이 좋지 않다. 2. 구현하기 public class BruteForceMethod { static int bruteForceMethod(String text, String pattern) { int textIdx = 0; int patternIdx = 0; while(textIdx != text.length() && patternIdx != pattern.length()) { if(text.charAt(textIdx) == pattern.charAt(patternIdx)) { textIdx++; patternIdx++; } else { textIdx = textIdx - patternIdx + 1;..

헤드 퍼스트 디자인 패턴을 읽고 정리한 내용입니다. 1. 간단한 팩토리(Simple Factory) 디자인 패턴이라기 보다는 프로그래밍에서 자주 쓰이는 관용구이다. 객체 생성 작업을 팩토리 클래스로 캡슐화해놓으면 구현을 변경할 때 팩토리 클래스 하나만 고치면 된다. 즉 코드에서 중복되는 내용을 제거할 수 있고, 관리할 때도 한군데만 관리하면 된다. 객체 인스턴스를 만들 때 인터페이스만 있으면 된다. 인터페이스를 바탕으로 하여 유연성과 확장성이 뛰어난 코드를 작성할 수 있다. 팩토리(factory): 객체 생성을 처리하는 클래스 1.1 문제 상황 당신은 피자가게를 운영한다. 따라서 아래의 코드를 작성하였다. 하지만 코드는 몇 가지 문제점이 있다. 피자 종류가 추가, 제거, 변경등이 일어날 때마다 코드를 계..

1. 도수 정렬(Counting Sort)이란? 요소의 대소 관계를 판단하지 않고 (다른 정렬 알고리즘들은 두 요소의 키 값을 비교해야 한다.) 단순하게 크기를 기준으로 세는 알고리즘이다. 데이터를 비교, 교환하는 작업이 없고 다중 for문이 아닌 단순 for문을 사용하고 재귀 호출과 중첩 for문이 없기 때문에 아주 효율적이다. 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우, 즉 범위 조건(e.g. 5이하 자연수를 오름차순 정렬)이 있는 경우에만 사용할 수 있다. 각 단계의 for문에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값의 순서가 바뀌는 일이 없다. 따라서 안정적인 정렬 알고리즘이다. 시간 복잡도는 O(n)으로 매우 빠르다. 2. 동작 방식 총 4단..

1. 힙 정렬(Heap Sort)이란? 힙(heap)을 사용하여 가장 큰 값이 루트에 위치 하는 특징을 이용하는 정렬 알고리즘이다. 선택 정렬(selection sort)을 응용한 알고리즘이다. (선택 정렬은 아직 정렬되지 않은 부분의 모든 요소를 대상으로 가장 큰 값을 선택한다.) 시간 복잡도는 O(n log n)이다. 1.1 힙(heap)이란? 부못값이 자식값보다 항상 크다(부못값 >= 자식값)라는 조건을 만족하는 완전 이진 트리이다. (완전: 부모는 자식을 왼쪽부터 추가하는 모양을 유지 + 이진: 부모가 가질 수 있는 자식의 개수는 최대 2개) 트리의 최상단 노드를 루트(root), 트리의 최하단 노드를 리프(leaf), 노드의 상하 관계를 부모(parent)와 자식(child), 자식간의 관계를 ..

1. 병합 정렬(Merge Sort)이란? 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘 배열 병합의 시간 복잡도는 O(n)이고, 전체 시간 복잡도는 O(n log n)이다. 서로 떨어져있는 요소를 교환하는 경우가 없으므로 안정적인 정렬 방법이다. 2. 동작 방식 int[] arr = { 5,6,4,8,3,7,9,0 }; // 1. 배열을 앞부분과 뒷부분으로 나눈다. 앞부분(a): { 5,6,4,8 } 뒷부분(b): { 3,7,9,0 } // 2. 앞부분과 뒷부분을 재귀를 사용하여 정렬한다. 앞부분(a): { 4,5,6,8 } 뒷부분(b): { 0,3,7,9 } 정렬된 배열(c): {} // 3. 각 배열의 작업에서 선택한 요소의 인덱스는 pa, pb, p..