[알고리즘]

1.알고리즘

• 알고리즘 : 입력값을 출력값의 형태로 바꾸기 위해 어떤 명령들이 수행되어야 하는지에 대한 규칙들의 순서적 나열. 같은 출력값이라도 알고리즘적 순서 나열에 따라 출력값에 도달하는 시간은 서로 다를 수 있음.

• 정확한 알고리즘 (정확성) : 알고리즘은 우리의 일상생활 언어로도 표현(pseudocode)할 수 있습니다.

• 효율적인 알고리즘 (효율성) : 효율성은 작업을 완료하기까지 얼마나 시간과 노력을 덜 들일 수 있는지에 대한 척도입니다.

2.의사 코드

• 의사코드(슈도코드, pseudocode) : 프로그램을 작성할 때 각 모듈이 작동하는 논리를 표현하기 위한 언어이다. 특정 프로그래밍 언어의 문법에 따라 쓰인 것이 아니라, 일반적인 언어로 코드를 흉내 내어 알고리즘을 써놓은 코드. 의사 코드는 프로그래밍 언어보다 문법적 제약을 적게 받으므로 알고리즘 표현에 많이 사용. 의사 코드를 작성하는 올바른 방법이란 없습니다. 어떤 때에는 당신의 목적이 무엇인가에 따라 의사 코드가 더 자세할 수도있습니다. 프로그래밍 언어와는 다르게, 의사 코드를 어떻게 작성해야 하는지를 정의한 문법은 없습니다. 그러나 의사 코드에는 자주 사용되는 몇 가지 요소들이 있습니다. 의사 코드에는 값을 할당한다는 개념이 종종 사용됩니다. 의사 코드에는 반복문(어떤 조건 하에서 특정 명령문이 반복되어 실행되는 것)이나 조건문(특정 조건으로 명령이 실행되기도 하고 건너뛰기도 하는 것)을 포함하기도 합니다. 의사 코드에서 사용될 수 있는 이런 개념들은 프로그래밍 언어로 작성된 프로그램에서도 중요한 개념입니다. 프로그래밍 언어를 배운 후에도 의사 코드는 문법 걱정 없이 알고리즘을 단계별로 표현할 수 있는 유용한 방법이며 프로그램의 논리를 이해하는데 더 효과적인 방법입니다.

• 들여쓰기 : 코드는 어떤 코드 블록이 어떤 문장에 포함되는지 알 수 있도록 들여쓰기 사용.

3.선형 탐색

원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 탐색. 이렇게 하여 선형 탐색은 찾고자 하는 자료를 찾을 때까지 모든 자료를 확인해야함. 선형 탐색 알고리즘은 정확하지만 아주 효율적이지 못한 방법. 리스트의 길이가 n이라고 했을 때, 최악의 경우 리스트의 모든 원소를 확인해야 하므로 n번만큼 실행. (최악의 상황은 찾고자 하는 자료가 맨 마지막에 있거나 리스트 안에 없는 경우) 평균적으로 선형 탐색이 최악의 상황에서 종료되는 것에 가깝다고 가정. 선형 탐색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용. 이러한 경우 무작위로 탐색하는 것보다 순서대로 탐색하는 것이 더 효율적입니다. 탐색 이전에 정렬 필요. 정렬은 시간이 오래 걸리고 공간을 더 차지. 하지만 이 추가적인 과정을 진행하면 시간 단축 가능.

4. 버블 정렬

두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법. 정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적. 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중. 이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.

5. 선택 정렬

배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다. 버블 정렬과는 다르게 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없습니다. 하지만 이 과정은 우리가 해야 할 비교 횟수보다 훨씬 더 많은 비교가 필요하므로 비용이 많이 듭니다. 원래 배열의 순서와 상관없이, 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요. n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적습니다. 그러나 한 번의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가 이루어져야 하므로, n²번의 비교가 이루어 집니다. 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 합니다.

6. 삽입 정렬

자료를 여러 번 비교하거나 교환할 필요가 없는 방법. 삽입정렬은 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어집니다. 정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법. 삽입 정렬은 특정 실행 단계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없습니다. 다음 단계가 진행되면서 다른 자료에 의해 위치가 바뀔 수 있기 때문입니다. 따라서 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적 입니다. 삽입정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮음

7. 시간 복잡도

• 시간 복잡도 : 알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것입니다. 시간의 효율성이란 결국 알고리즘에서 비교와 교환 등이 일어날 때 연산자의 처리 횟수가 적다는 의미이며, 연산자의 처리 횟수가 적다는 건 시간의 복잡도가 낮다는 의미입니다. 따라서 시간 복잡도가 낮을수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 됩니다.

• Big-O 표기법 : 컴퓨터 과학에서 대략을 나타내는 공식적인 개념으로 최악의 경우에 대한 시간 복잡도를 나타내는 표현.

• Big Ω 표기법 : 최선의 경우

[알고리즘의 Big-O 표기]

• 선형 탐색 O(n): 찾는 값이 배열의 맨 끝에 있는 최악의 상황의 경우 이 값을 찾는데 n번의 단계를 거침.

• 버블 정렬 O(n²) : 인접해 있는 자료와 쌍을 이루어 비교하기 때문에, n개의 자료를 갖는 배열은 n-1쌍을 비교합니다. n개의 자료가 있을때 n-1번 비교해주면, n번째의 자료가 정렬되어있습니다. 그 이후로 n-1개의 자료를 다시 비교하게 됩니다.

• 선택 정렬 O(n²) : 가장 작은 값(혹은 가장 큰 값)을 찾아 제 자리를 찾아줍니다. n개의 자료가 있다면 첫 번째 자료와 나머지 n-1개의 자료 중 가장 작은 값의 자리를 교환해주어야 합니다. n-1개의 자료 중에서 가장 작은 값을 찾기 위해서는 n-1번의 비교가 필요합니다.

• 삽입 정렬 O(n²) : n개의 자료가 있다면 첫 번째 자료는 정렬이 되었다고 생각하고, n-1개의 자료 중 첫 번째 자료와 정렬된 자료를 비교합니다. 이때 정렬된 자료는 1개이기 때문에 비교 횟수는 1입니다. 정렬되지 않은 부분에 1개의 자료가 남게 되면, 정렬된 자료의 수 n-1개 만큼의 비교가 필요합니다.

[알고리즘의 Big Ω 표기]

• 선형 탐색 : 배열의 크기와 상관없이 Ω(1)

• 버블 정렬 : 최선의 경우(이미 정렬된 배열)를 생각해보면 버블 정렬은 교환이 이루어지지 않더라도 배열이 정렬된 사실을 모르기 때문에 여전히 n-1번의 비교를 해줘야 합니다. 그래서 최선의 경우는 Ω(n)

• 선택 정렬 : 배열이 정렬되었다는 것을 알 수 없어, 최소값을 계속 찾아주어야 하므로 Ω(n²)로 표기

• 삽입 정렬 : 정렬되지 않은 부분에서 정렬된 부분으로 옮겨갈 때, 정렬된 부분의 가장 큰 수와 비교하기만 하면 되기 때문에 Ω(n)로 표기

8. 합병 정렬

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다. 그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽습니다. 나누어지고 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때 까지 기억하고 있어야 하기 때문에, 메모리의 필요한 공간이 늘어납니다. 필요 시간은 적게듭니다.

9. 이진 탐색

선형 탐색보다 더 빠른 알고리즘으로 이진 탐색이 있습니다. 이진 탐색은 자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색의 범위를 반으로 줄여나가는 탐색 알고리즘입니다. 배열을 정렬하는 데는 버블 정렬, 삽입 정렬, 선택 정렬 등 다양한 방법이 있습니다. 이 정렬 방법은 사실 이진 탐색을 구현하는 데 유용합니다. 이진 탐색은 일반적으로 선형탐색보다 탐색 속도가 짧지만, 배열을 정리하는 시간이 추가됩니다. 하지만 배열을 여러 번 탐색할 계획하고 있다면 이진 탐색이 유용하게 사용됩니다. 찾고자 하는 값이 배열에 없는 경우 선형 탐색은 배열의 길이가 얼마든 상관없이 배열 전체를 훑어보아야 배열 안에 찾고자 하는 값이 없다는 것을 알 수 있습니다. 이에 반해 이진 탐색에서는 더 효율적으로 사용할 수 있습니다. 의사 코드를 수행해보면, 찾고자 하는 값이 최소값보다 작거나 최대값보다 크다면 해당 원소가 배열 안에 없다는 것을 알 수 있습니다.