전공 수업 CS

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

● 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'..

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

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

[알고리즘] ADL

#컴퓨터 공학부 3학년 과정인 알고리즘을 수강하면서, 교수님이 알고리즘을 구현할 때 언어로 파이썬을 사용하시는데, 파이썬으로 코드를 구현하기 전에 ADL을 이용하여 알고리즘을 기술한다. 그래서 ADL에 대해 정리해보고자 한다. ADL (Algorithm Description Language) 알고리즘 기술을 위해 정의한 언어 사람이 이해하기 쉽고, 프로그래밍 언어로의 변환이 용이 의사 코드 (pseudo-code) : ADL과 약간의 자연어로 기술한 것 ADL 데이터 : 숫자, 부울(Boolean) 값, 문자 ADL의 명령문 : 종류 : 지정문, 조건문, 반복문, 함수문, 입력문, 출력문 명령문 끝에는 세미콜론(;)을 사용 지정문 형식 : 변수 ← 식; 식 (expression) 산술식 부울식 – 결과 ..