수학과의 개발자 도전기

공부한 날짜: 2021. 11. 07

-알고리즘 성능 분석 요소 5가지 

(1) 정확성: 정확하게 작동하는가?

(2) 작업량: 얼마나 적은 연산을 수행하는가?

(3) 메모리 사용량: 얼마나 적은 메모리를 사용하는가?

(4) 단순성: 얼마나 단순한가?

(5) 최적성: 더 이상 개선할 여지가 없을 만큼 최적화되어 있는가? 

-알고리즘 수행 시간의 분석

적절한 알고리즘 수행시간: 컴퓨터의 성능에 관계 없이 명확하게 정의될 수 있어야하며, 이미 알려진 수행 시간을 바탕으로 입력데이터의 크기의 변화에 대한 수행시간의 변화를 예측할 수 있어야함 

(1) 최악의 경우: 최대 걸리는 시간(상한선)-> 어떤 환경에서도 실행되었을 때 기본으로 걸리는 시간 

(2) 평균의 경우: 일반적인 상황에서 소요되는 알고리즘 수행시간

(3) 최선의 경우: 최적의 상황에서 소요되는 알고리즘 수행시간(적절하지 않음, 매번 최적의 상황으로 동작하는게 아니므로)

1. 점근 표기법

: 알고리즘의 수행 시간을 대략적으로 나타내는 방법(수행시간 식의 최고차 항으로만 성능 대략적으로 표시)

장점: 알고리즘의 성능을 단순화해서 표현 -> 알고리즘 간의 성능 비교가 용이 

종류: O(Big O)표기법, Ω(Big Omega)표기법 , Θ(BigTheta)표기법 

(1) O(Big O)표기법 : 수행시간 상한을 나타낼 때 사용함 

(2) Ω(Big Omega)표기법 : 수행시간의 하한을 나타낼 때 사용함 

(3) Θ(BigTheta)표기법 : 알고리즘 수행시간의 상한과 하한을 동시에 나타냄 

2. 재귀 알고리즘의 성능 분석 

-재귀 방정식: 자기 자신을 항으로 갖는 방정식

재귀 알고리즘의 수행시간(성능)을 나타내는 또 하나의 표현방법이다 

공부한 날짜: 2021. 11. 07

-(보이어-무어) 알고리즘: 문자열을 오른쪽에서 왼쪽으로 비교해 나가는 알고리즘, 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우 패턴의 길이가 이동거리가 된다 

-종류 : 나쁜 문자 이동(Bad Character Shift), 착한 접미부 이동(Good Suffix Shift)

목적: 불일치가 발생할 때 최대의 효율로 이동하는 방법 정의(더 많이 움직일 수 있는 걸로 선택)

1. 나쁜문자 이동 (Bad Character Shift)

: 본문과 패턴 사이를 불일치 시키는 본문의 문자(나쁜 문자)를 이동시킨다 

-과정

(1) 패턴에서 나쁜 문자를 찾는다

(2) 찾아낸 패턴의 나쁜 문자의 위치가 본문의 나쁜 문자 위치와 일치하게 패턴을 이동시킨다 

(나쁜문자와 같은 문자가 패턴 내에서 두 개 이상 나오는 경우, 그 중에 가장 오른쪽에 있는 것을 본문의 나쁜문자에 맞추면된다)

2. 착한 접미부 이동 (Good Suffix Shift)

-착한 접미부: 패턴의 접미부와 일치하는 본문의 단어. 착한 접미부 이동을 하는 상황은 두 가지로 나뉜다

Case 1.

: 불일치가 일어났을 때 착한 접미부와 동일한 문자열이 패턴의 착한 접미부 왼쪽에 존재하는 경우 

Case 2.

: 착한 접미부가 패턴 안에 존재하지 않고 (착한 접미부의 접미부)가 (패턴의 접두부)와 일치하는 경우

-> 이런 이동을 하려면 사전에 가공된 정보(테이블)가 필요함 

패턴을 왼쪽에서 오른쪽으로 읽어나가면서 패턴에 있는 각 문자의 위치를 이 테이블에 기록해두면됨 

(1) 나쁜문자 이동 테이블 : 패턴에서 겹치는 문자 중 가장 오른쪽에 있는 문자의 인덱스를 테이블의 해당 문자 인덱스에 입력 

(A의 가장 오른쪽 위치 인덱스 3이면 테이블의 A 위치에 3입력)

패턴에 없는 문자는 -1 입력 

(2) 착한 접미부 이동 테이블: 이 테이블은 착한 접미부의 이동거리를 보관한다 

- 불일치가 일어났을 때 착한 접미부가 패턴안에 존재할 때

-

이해가 안가서 못하겠음 

공부한 날짜: 2021. 11. 04

1. 고지식한 검색(naive search, brute force search)

:  하나하나 비교해서 본문에서의 입력값을 찾는 알고리즘 

2. 카프 -라빈 알고리즘

: 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시 값을 비교해서 문자열을 찾는 알고리즘 

최초의 해시 값(H0)과 해당 문자열의 값(S[i])만 가지고 해당 문자열에 대한  해시 값을 구하고, 패턴의 해시값과 비교해서 단어를 찾는다 

(1) 해시 값 같은거 확인 (2) 각 문자 일일이 확인((해시 값이 같은 다른 문자열이 있을 수 있으므로)

3. KMP 알고리즘

: 비교가 필요한 부분만 비교를 수행하는 알고리즘 

-접두부/접미부/경계

접두부: 문자열의 머리 부분, 접미부: 문자열의 꼬리 부분, 경계: 문자열에서 일치하는 접두부와 접미부 쌍(하나의 문자열의 접두부와 접무부의 단어가 같은 경우)

-동작 원리

본문의 접미부와 패턴의 접두부가 동일하면 패턴이 그 단어의 접미부로 이동해서 비교해 나간다(?)

-경계의 정보를 갖는 테이블 만들기(경계를 효율적으로 찾기 위해서)

**원리 설명 부분 아직 이해 못함

공부한 날짜: 2021. 11. 04

-최단경로 탐색: 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최소값이 되게 만드는 경로를 찾는 알고리즘

-다익스트라 알고리즘 

: '경로의 길이'를 감안해서 간선을 연결한다는 점이 '간선의 길이'를 이용해 어떤 간선을 먼저 연결할지 결정하는 프림 알고리즘과 다름 

-동작 순서(아직까지는 ㄷ.이 무슨말인지 모르겠음,,)

ㄱ. 각 정점 위에 있는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 모든 정점 위에 있는 경로의 길이를 무한대로 초기화 

ㄴ. 시작 정점의 경로 길이를 0으로 초기화 하고 최단 경로에 추가

ㄷ. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 

만약 추가하는 인접 정점이 이미 최단 경로 안에 존재한다면/ 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해, 다른 선행 정점을 지나던 기존의 경로를 현재 정점을 경유하도록 수정한다. 

ㄹ. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 ㄷ. 과정을 반복한다 

-다익스트라 구현