전공 수업 CS/algorithms

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

파일 압축 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) 말 그대로 고지식하게, 본문이 되는 문자열의 맨 앞에서부터 끝까지, 찾고자 ..

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

쉘 정렬 알고리즘은 삽입정렬을 간단하게 변형한 것입니다. 원소의 비교 연산과 먼 거리로의 원소 이동을 줄이려는 목적을 가진 알고리즘입니다. 인덱스 간격은 쉽게 계산 가능해야하고, 홀수와 짝수가 번갈아 나오면서 순차되는 것이 좋습니다. 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] * * 그 다음에는 기존의 정렬 범위에 한칸 확장하여 세번째 값을 추가시키고 생각해보겠습니다. 기존 정렬 범위에서 가장 큰 값인..

[알고리즘] 버블정렬

버블정렬은 리스트를 검사하여 두 인접한 원소가 오름차순 정렬에 맞지 않으면 이들을 서로 교환하는 알고리즘 입니다. a[1], a[2] 비교 및 교환 a[2], a[3] 비교 및 교환 a[3], a[4] 비교 및 교환 . . . a[n-1], a[n] 비교 및 교환 이 과정을 반복하면 가장 큰 원소가 배열의 n 위치로 끓어 오르게 되는데, 이것이 첫 번째 패스 입니다. 두 번째 패스에서는 다시 배열의 처음부터 인접한 원소를 비교하여 순서가 맞지 않을 경우 교환하면서 검사합니다. 이 때는 마지막 비교가 a[n-2] 와 a[n-1]이 됩니다. // 이미 가장 큰 원소는 가장 오른쪽에 들어가 있기 때문입니다. 이 패스는 배열에서 두 번째로 큰 원소를 n-1의 위치로 끓어 오르게 합니다. 이 정렬은 가장 큰 원소..

[알고리즘] 선택 정렬 알고리즘

선택정렬 선택 정렬은 여러 개의 데이터가 무작위로 있을 때 전체 데이터에서 매번 가장 작은(또는 가장 큰) 데이터를 선택하여 데이터 간의 위치를 변경하는 과정을 반복하여 데이터를 오름차순(또는 내림차순)으로 정렬할 때 사용합니다. 선택 정렬의 종류는 2가지로 나눌 수 있습니다. 최소 선택 정렬(Min-selection sort): 매번 가장 작은 데이터를 선택하고 데이터 간의 배치를 변경하며 오름차순으로 정렬 최대 선택 정렬(Max-selection sort): 매번 가장 큰 데이터를 선택하고 데이터 간의 배치를 변경하며 내림차순으로 정렬 선택정렬은 어떻게 동작하는가? 최소 선택 정렬의 경우 구체적인 동작 과정은 다음과 같습니다. 1. 전체 데이터에서 가장 작은 데이터를 선택하고 맨 앞에 있는 데이터와 ..

[알고리즘] 정렬 알고리즘 정리 | 버블 정렬, 삽입 정렬, 선택 정렬, 합병 정렬, 퀵 정렬

컴퓨터 공학부 3학년 전공필수 과정인 알고리즘을 공부하면서, 추가적인 이해가 필요하다 판단하여 포스탕을 찾아보던중 필자의 정렬에 대한 이해를 도와준 블로그 포스팅이 있어서 내 블로그에 올려놓고 계속 볼 생각이다! 출처는 다음과 같다. https://evan-moon.github.io/2018/10/13/sort-algorithm/ 정렬 알고리즘 정리 (Bubble, Selection, Insertion, Merge, Quick) 이번 포스팅에서는 대표적인 정렬알고리즘 5가지와 대략적인 에 대해서 정리하려고 한다. 먼저, 그 5가지 정렬알고리즘은 다음과 같다. evan-moon.github.io ==============================================================..

[알고리즘] 알고리즘의 성능 평가 | 점근식 표기법 | 순환

성능 분석 : 프로그램을 실행하는데 필요한 시간과 공간의 추정 성능 측정 : 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정 ============================================================================================ 성능 분석 공간 복잡도 : 알고리즘을 실행시켜 완료하는데 필요한 총 저장 공간(고정 공간 + 가변 공간) 시간 복잡도 : 알고리즘을 실행시켜 완료하는데 걸리는 시간(컴파일 시간 + 실행 시간) 점근식 표기법(Asymptotic notation) Big-Oh (O) : f, g가 양의 정수를 갖는 함수일 때, 두 양의 상수 a, b가 존재하고, 모든 n >= b에 대해 f(n) ≤ a · g(n) 이면, f(n)..