SOLID BASIC

[알고리즘] 스트링 처리 알고리즘 | 암호화 알고리즘

텍스트를 관련 없는 사람들이 읽을 수 없도록 하는 것이 암호화이며, 컴퓨터를 사용하여 암호화를 수행할 때 사용되는 알고리즘이 암호화 알고리즘이다. 이 분야는 암호 작성과 암호 해독으로 나눌 수 있다. 암호화 시스템은 다음과 같은 구성요소로 이루어져 있다. 송신자: 메세지를 암호화 함 수신자: 메세지를 복호화 함 암호화 기법 복호화 기법 키 매개변수 암호화 시스템에서 암호화 및 복호화 기법은 알고 있으면서 키 매개변수를 모르는 상태에서 암호문으로부터 평문을 복원해내는 사람을 암호 해독자라고 한다. 1) 단순한 기법 1. 카이사르 암호화: 평문에 있는 문자가 알파벳의 N번째 문자라면, 이것을 N+K번째 문자로 교체하는 것이다. 카이사르는 K 값으로 3을 사용했다. 2. 비즈네르 암호화: 평문의 각 문자에 대..

[알고리즘] 스트링 처리 알고리즘 | 허프만 코드, 허프만 알고리즘

압축이란 파일의 크기를 줄이는 방법을 의미한다. 즉, 시간 보다는 공간을 절약하는 방법에 대해 연구한다. 대부분의 컴퓨터 화일에서는 데이터가 중복되어 있다고 착안하고 있다. 압축을 하게되면 한정된 컴퓨터자원을 효율적으로 사용할 수 있다. 1) 런-길이 인코딩 화일에서 기본적인 중복은 같은 문자가 연속적으로 나타나는 것이다. 하나 예시를 들어보자면, AAAABBCCCCC = 4A2B5C 와 같이 표현할 수 있다. 위와 같이 동일한 문자가 여러개 나올 경우 숫자와 문자 쌍으로 화일을 압축하는 기법을 '런-길이 인코딩'이라고 한다. 그러나 실제 문서에서는 같은 문자가 여러번 연속해서 나오는 경우가 많지 않기에 런-길이 인코딩은 주로 이진수로 표현되는 비트맵 이미지를 압축하는데 사용된다. 예를들어 이진수 000..

[알고리즘] 스트링 처리 알고리즘 | 화일 압축 알고리즘 | 허프만 인코딩

파일 압축 1. Huffman Encoding 1) 특징 1. 무손실 압축 허프만 인코딩은 무손실 압축이라는 점에 있어서 매우 큰 장점을 가진다. 즉, 압축을 할 때, 원본의 정보가 전혀 손상되지 않고 압축이 가능하다는 것이다. 2. 가변 길이 인코딩 가변 길이 인코딩이란? 자주 나타나는 문자에는 길이가 작은 비트를 사용하고 적게 나타나는 문자에는 길이가 긴 비트를 사용해 encoding하는 압축 기법이다. 즉, 해당 파일의 형태에 따라 압축 방법이 달라진다는 것이다. 3. 가변 길이 인코딩의 주의점 가변 길이 인코딩을 사용할 때, 정말 아무생각 없이 시도한다면 다음과 같이 코드를 할당할 수 있다. 여기에는 큰 문제점이 존재한다. 예를들어 BAC라는 문자를 Encoding한다고 하면 1010이 될 것이다..

[알고리즘] 스트링 처리 알고리즘 | 패턴 매칭 알고리즘

패턴 매칭 알고리즘 이 알고리즘은 정해진 문자를 찾는것이 아니라 특정 패턴의 문자를 찾는 알고리즘이다. 1) 정규 표현식 (아래의 표현식 이외에도 수많은 식들이 있는데 이는 구글링을 통해 참고하자.) AB : AB를 찾는다. A+B : A또는 B를 찾는다. ()* : ()안의 문자들이 0번 이상 나타나는 경우를 찾는다. ? : 해당 자리에 어떤 문자라도 들어올 수 있다. (0개 또는 1개) (예시) ?*(ie+ei)?* : ie 또는 ei를 갖고 있는 모든 단어 (1+01)*(0+1) : 두개의 0이 연속적으로 나오지 않는 0과 1로 이루어진 문자열 2) 패턴 매칭 장치 그리기 패턴 매칭 장치는 위에서 보았던 KMP의 유한 상태 장치처럼 현재 상태에 따라 다음에 어떤 것을 해야할 지 그림으로 표현한 장치..

[알고리즘] 스트링 처리 알고리즘 | 보이어 무어 알고리즘

● 1. 보이어-무어 알고리즘(Boyer-Moore algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 것으로, 이전 포스팅에서 살펴본 KMP 알고리즘의 목적과 유사합니다. 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것이 주 목표입니다. 보이어-무어 알고리즘은 보통 상황에서 문자열은 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용합니다. 그래서 오른쪽 끝부터 비교하게 됩니다. ○ 1-1. 보이어-무어 알고리즘의 예 패턴의 오른쪽 끝에 있는 문자(e)와 본문(z)을 비교하여 일치 여부를 판단합니다. 불일치하고, 이 문자(z)가 패턴(apple)에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킵니다. 만일 패턴의 오른쪽 끝에 있는 문자(e)가 본문(p)와 비교해서 불일..

[알고리즘] 스트링 처리 알고리즘 | KMP 알고리즘

문자열을 검색하려면? : 패턴 매칭 문자열을 검색하는 상황은 많은 상황에서 쓰입니다. 포털 사이트 키워드 검색에서도 사용될 수 있고, 웹 페이지에서 ctrl+F 를 눌러서 검색하는 데에도 사용될 수 있습니다. 이렇듯 본문이 되는 String에서 찾고자 하는 특정한 String을 패턴이라고도 하는데, 이 패턴을 찾는 방법을 패턴 매칭이라고 합니다. 달리 말해서 패턴 매칭이지, 그냥 문자열 검색이라고 생각하면 됩니다. SW Expert Academy를 통해 문자열 검색에도 다양한 알고리즘이 있음을 다시 한번 알게 되었습니다. 특정 문자열에서 어떤 키워드를 검색하려면 어떻게 해야 할까요? 1. 고지식한 알고리즘(Brute Force) 말 그대로 고지식하게, 본문이 되는 문자열의 맨 앞에서부터 끝까지, 찾고자 ..

[컴퓨터 구조] 카르노맵

식 간소화 (Simplification) 예를 들어 f=a+ad'+abc+ac'ef+ahj라는 식이 있다고 해봅시다. 이걸 그대로 회로로 만들려면 너무 힘들겠죠? 정리하면 간단하게 f=a로 만들 수 있으니, 식을 간소화하자는 것입니다. 식을 간소화하는 방법에는 여러 가지가 있습니다. 항을 줄이는 방법, 상수를 없애는 방법, 항을 추가하는 방법 등 다양합니다. 이때에는 불 대수가 활용되는데, 주로 흡수 법칙, 합의의 정리 등을 활용하면 쉽게 식을 간소화할 수 있습니다. 항을 추가하는 방법이 식 간소화 방법이라는 것에 놀라실 수도 있는데, 이 역시 합의의 정리를 응용한 것입니다. f=ab+b'd'+ac'd'이라는 식이 있다면, ab+b'd'=ab+b'd'+ad'이므로 +ad'를 추가할 수 있고 ad'+ac'..

[알고리즘] 퀵 정렬 알고리즘

퀵 정렬은 피벗(pivot)이라는 기준 데이터를 설정하고 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방식입니다. 퀵 정렬은 데이터 간의 비교만으로 정렬을 수행하는 비교 정렬 중 하나로서 이름에서 알 수 있듯이 정렬이 빠르다는 특징이 있습니다. 퀵 정렬의 방식은 피벗을 설정하고 데이터를 분할하는 방법에 따라 여러 가지로 구분할 수 있습니다. 2. 퀵 정렬의 동작 과정 이제 퀵 정렬의 구체적인 동작 과정을 알아보도록 하겠습니다. "리스트 가장 오른쪽 데이터를 피벗으로 설정한다"와 같은 규칙에 따라 피벗을 선정하겠습니다. 피벗 선정 후 아래와 같은 순서로 데이터를 정렬합니다. 1️⃣ 리스트 좌측에서 우측 방향으로 피벗보다 큰 데이터를 찾고, 리스트 우측에서 좌측 방향으로 피벗보다 작은..

[알고리즘] 쉘 정렬 알고리즘

쉘 정렬 알고리즘은 삽입정렬을 간단하게 변형한 것입니다. 원소의 비교 연산과 먼 거리로의 원소 이동을 줄이려는 목적을 가진 알고리즘입니다. 인덱스 간격은 쉽게 계산 가능해야하고, 홀수와 짝수가 번갈아 나오면서 순차되는 것이 좋습니다. ADL shellSort(a[], n) for(h

[알고리즘] 삽입 정렬 알고리즘

삽입 정렬 알고리즘은 카드놀이를 할 때 손에 들고 있는 카드를 정렬하는 것과 유사합니다. 삽입 정렬은 한마디로 표현하면 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다. 예를 들어, 다음과 같이 1부터 5까지 총 5개의 숫자가 들어있는 배열에 있다고 가정해보겠습니다. [2, 1, 5, 4, 3] 맨 처음에는 첫번째 2개의 값만 정렬 범위에 포함시키고 생각해보겠습니다. 앞에 있는 값 2는 뒤에 있는 값 1보다 작기 때문에 서로 자리를 바꿔줍니다. [2, 1]: 2 > 1 => swap ^ ^ [1, 2] * * 그 다음에는 기존의 정렬 범위에 한칸 확장하여 세번째 값을 추가시키고 생각해보겠습니다. 기존 정렬 범위에서 가장 큰 값인..