[CS 1-2 | 이산수학] 알고리즘 9주차

알고리즘이란

알고리즘은 어떤 문제가 주어졌다면, 가장 먼저 문제를 수학적인 문맥으로 변환을 시킨다.

즉, 문제를 일반화 한 이후 모델을 이용하여 풀어야 한다.

 

알고리즘은 계산을 하거나, 문제를 해결할 정확한 명령을 유한이 나열한 것이다.

 

의사코드란

프로그래밍 언어를 사용해서 알고리즘을 표현한다.

의사 코드는 인간의 언어와 실제 프로그래밍 언어의 중간 단계로 알고리즘을 설명한다.

 

탐색 알고리즘 - 선형 탐색이란

정렬된 리스트에서 원소를 찾는 문제를 탐색 문제라고 한다.

이러한 탐색 문제에서 데이터를 선형적으로 찾을 때를 선형 탐색이라고 한다. 

 

ex) a1, a2, a3, a4, a5 ... a105... an 으로된 리스트가 있다고 가정하고,/

a105 데이터를 찾아야한다.

선형 탐색 알고리즘을 이용해 a1부터 하나씩 탐색해 데이터를 찾는다.

 

그럼, 선형 탐색 알고리즘은 데이터 리스트에 대한 정렬이 필요 없이,
데이터가 저장된 공간상의 구조를 통해 탐색을 하므로
데이터 정렬과정이 필요하지 않다~~!

 

탐색 알고리즘 - 이진 탐색이란

탐색 문제에서 데이터를 순차적으로 정렬해두고, 탐색하려고 하는 원소와 비교해

크면, 오른쪽으로 데이터 탐색을 진행하고,

작으면, 왼쪽으로 데이터를 탐색을 진행한다.

그렇기에, 원하는 탐색 데이터를 찾을 때까지 위의 과정을 반복한다.

 

이 부분에 대해선, 정확하게 어떤 전개를 가지는지는 아직까지 잘 모르겠다..ㅎ
그치만, 이제 많이 접해보면서 익힐 에정이다 ~~

 

 

 

정렬 - 버블 정렬이란

정렬은 집합의 원소를 나열한 리스트가 있을 때, 이 원소를 점점 커지는 순서로 나열한다.

 

버블 정렬은 인접한 원소를 "차례대로" 비교하고 둘의 순서가 잘못되어 있다면

원소의 자리를 서로 교환한다.

ex) 7 2 3 5 6 -> 2 7 3 5 6 -> 2 3 7 5 6 -> 2 3 5 7 6 -> 2 3 5 6 7 (첫번재 원소인 7 자리 지정 완료)

이와 같이 차례대로 비교해 나열된 리스트에서의 정렬된 자리로 옮겨준다.

 

정렬 알고리즘 중에서, 가장 간단하지만
비효율적인 알고리즘이라고 한다~
가장 큰 원소가 맨 앞에 위치해있으면, 리스트의 원소 갯수 만큼 비교해야되는
연산 횟수가 많아진다 ㅎㅎ...

 

 

이산수학은..

행렬, 정수론 부분이 어렵게 나올 것..

그리고, 증명 문제는 반드시 나올것

증명 전략들 시험 전에 한번씩 사용해보는 것 권장!

 

정렬 - 삽입 정렬이란

n개의 원소가 있는 리스트가 있을 때, 두 번째 원소를 첫 번째 원소와 비교한다.

첫 번째 원소보다 작으면 첫 번째 원소 앞에, 크면 첫 번째 원소 뒤에 놓는다. (이것으로 둘의 순서는 완벽해진다.)

세 번째 원소를 첫 번째 원소와 비교한다.

첫 번째 원소보다 작으면 첫 번째 원소 앞에, 크면 두 번째 원소와 비교한다.

두 번째 원소보다 작으면 두 번째 원소 앞에, 크면 두 번째 원소 뒤에 놓는다.

다음과 같이 모든 원소를 삽입하듯이 데이터를 비교해 올바르면 삽입해서 데이터 리스트를 재구성한다.

 

 

문자열 매칭 알고리즘

 

 

욕심쟁이 알고리즘 - 그리드 알고리즘

최적화 문제를 푸는 알고리즘 중 하나이고,

각 단계마다 가장 "좋은" 선택을 하는 알고리즘이다.

 

다음은, 이러한 알고리즘이 있다고만 알아놔도 될 듯하다..

 

 

 

 

Big - O 표기법

 

 

# Big - O 중요 함수

 

Big - O 표기를 추정할 때는

최악의 경우를 Big - O 표기로 나타낸다.

 

Big - O 표기는 결합의 예제에 대해서 문제를 많이 접해보며
익숙해지면 된다.